C++

[max(Im)]

Здравствуйте!
Я не очень знаю С++ и прошу помочь как новичку.

Вот есть std::sort, у него есть параметр - предикат сравнения. То есть компаратор. Теперь пусть я написал этот компаратор в каком-то виде. Но теперь пишу функцию вида std::sort, пусть даже свой sort.
Как объявить эту функцию, как показать, что она принимает компаратор? Быть может где-то можно прочитать конкретный пример? Но будет куда лучше, если кто-нибудь приведет его здесь. Потому что все, что я нахожу про компараторы - это как их использовать.

И еще вопрос. Пусть у меня есть структура my_struct.
Я могу написать:

Используется синтаксис C++

std::sort (begin, end, std::less<my_struct>);

? и что это будет значить? Как мне этот less переопределить?

Извиняюсь, если вопросы очень глупы.

[Circiter]

2max(Im)

Цитата:

Как объявить эту функцию, как показать, что она принимает компаратор

Можно в стиле C использовать указатель на функцию. А можно использовать C++ шаблоны. Самый примитивный вариант:

Используется синтаксис C++

template <typename Cmp>
void MySort(int Arg, Cmp cmp)
{
    ...
    if(cmp(..., ...))
    ...
}
 

Теперь можете написать или функцию-"компаратор":

Используется синтаксис C++

bool MyCmpFunc(int a, int b)
{
    ...
}
 

или класс-функтор с перегруженным оператором вызова функции:

Используется синтаксис C++

struct MyCmpClass
{
    bool operator () (int a, int b)
    {
        ...
    }
} MyCmpObject; // Optional.
 

Теперь можно делать что-то такое:

Используется синтаксис C++

    MySort(1, MyCmpFunc);
    MySort(1, MyCmpClass());
    MySort(1, MyCmpObject);
 

Цитата:

что это будет значить?

Это означает, что сортировка будет происходить с использованием указанной вами функции сравнения, возвращающей логический результат сравнения объектов типа my_struct. А что вы ожидали? :)

Цитата:

Как мне этот less переопределить?

Создайте свой компаратор. Он может быть простой функцией вроде показанной выше MyCmpFunc или функтором. Есть ещё прием с переопределением, точнее говоря со специализацией самого std::less путем описания этой специализации в пространстве имен std, т.е. пишите что-то вроде namespace std {template ... struct less <...>: binary_function ... {...};}. Думаю, вам пока это не нужно...

Upd: Ещё можно определить/перегрузить оператор сравнения для вашего типа данных.

[nestoklon]

max(Im) в сообщении #507592 писал(а):

Я не очень знаю С++

Тогда наверное имеет смысл начинать сразу новый стандарт изучать?

Используется синтаксис C++

std::sort(begin, end, [](my_struct a, my_struct b){ return a.value < b.value; });

[max(Im)]

Circiter

Спасибо большое.
Я еще выяснил, что std::less тоже можно использовать, перегрузив своему типу оператор < (ну или подобное).

Что я делаю не так:

Используется синтаксис C++

class Sorter {
 public:
  template <class Type, class Comparer>
  void QuickSort(...,
      Comparer compare);
// .....
};

//....
sorter.QuickSort(...,
      std::less_equal<my_struct>());
 

Для my_struct определен оператор <=. Почему ошибка при вызове?

[Circiter]

Непонятно, что вы там делаете. Или весь пример в сжатой форме приведите (без всяких сокращений, с заголовочными файлами) или хотя-бы приведите диагностический вывод компилятора, процитируйте все сообщения об ошибке.

[max(Im)]

Вот например, все лишнее убрал:

Используется синтаксис C++

#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::vector;

struct my_struct {
  int first;
  int second;
  bool operator <=(const my_struct& other) const;
};

bool my_struct::operator <=(const my_struct & other) const {
  if (this->first == other.first && this->second <= other.second) {
    return true;
  } else {
    return false;
  }
}

class Sorter {
 public:
  template <class Type, class Comparer> 
  void QSort(typename vector<Type>::iterator begin,
      typename vector<Type>::iterator end, Comparer comp) {
        std::sort(begin, end, comp);
  }
};

int main() {

  vector<my_struct> my_vector;
  Sorter sorter;
  sorter.QSort(my_vector.begin(), my_vector.end(), std::less_equal<my_struct>());
  
  return 0;
}
 

Ошибка в строке вызова:

Цитата:

error C2783: 'void Sorter::QSort(vector<Type>::iterator,vector<Type>::iterator,Comparer)' : could not deduce template argument for 'Type'

[venco]

C++ компилятор не умеет определять параметры шаблона по внутренним классам или типам. Они могут совпадать в нескольких кандидатах на темплейтный параметр, и, вообще говоря, могут не иметь никакого отношения к этому параметру, кроме упоминания в виде typedef внутри.
Вам надо либо в качестве параметра использовать итератор напрямую (как в STL), либо явно указать параметры шаблона при вызове:

    sorter.QSort<my_struct, std::less_equal<my_struct> >(my_vector.begin(), my_vector.end(), std::less_equal<my_struct>());

Кстати, использовать less_equal<> в качестве компаратора при вызове std::sort<> нельзя, т.к. ему требуестя компаратор со Strict Weak Ordering, в том числе возвращать false для равных объектов. Если у вас это правило нарушено, то алгоритм sort с большой вероятностью выйдет за пределы массива, и скорее всего упадёт по segfault.

[Circiter]

2venco

Цитата:

C++ компилятор не умеет определять параметры шаблона по внутренним классам или типам.

Извините, но мне вот не совсем понятна эта фраза. Скажем в примере max(Im)'а можно сделать такие изменения и всё скомпилируется:

Используется синтаксис C++

...
   void QSort(vector<Type> &array, Comparer comp) {
         std::sort(array.begin(), array.end(), comp);
   }
...
   sorter.QSort(my_vector, std::less_equal<my_struct>());

Поясните, пожалуйста.


Upd: А, всё, понятно. :) Вечно я с шаблонами путаюсь. (Зато последний пример можно рассматривать как альтернативу явному указанию параметров при вызове.)

[max(Im)]

venco в сообщении #508662 писал(а):

Вам надо либо в качестве параметра использовать итератор напрямую (как в STL),

Что вы имеете в виду?

[venco]

Используется синтаксис C++

template <class Iterator, class Comparer>
  void QSort(Iterator begin, Iterator end, Comparer comp) {