2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 C++
Сообщение25.11.2011, 00:57 
Здравствуйте!
Я не очень знаю С++ и прошу помочь как новичку.

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

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

Используется синтаксис C++
std::sort (begin, end, std::less<my_struct>);


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

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

 
 
 
 Re: C++
Сообщение25.11.2011, 07:07 
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: Ещё можно определить/перегрузить оператор сравнения для вашего типа данных.

 
 
 
 Re: C++
Сообщение25.11.2011, 07:54 
max(Im) в сообщении #507592 писал(а):
Я не очень знаю С++
Тогда наверное имеет смысл начинать сразу новый стандарт изучать?
Используется синтаксис C++
std::sort(begin, end, [](my_struct a, my_struct b){ return a.value < b.value; });

 
 
 
 Re: C++
Сообщение26.11.2011, 20:21 
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 определен оператор <=. Почему ошибка при вызове?

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

 
 
 
 Re: C++
Сообщение27.11.2011, 00:01 
Вот например, все лишнее убрал:

код: [ скачать ] [ спрятать ]
Используется синтаксис 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'

 
 
 
 Re: C++
Сообщение27.11.2011, 03:50 
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.

 
 
 
 Re: C++
Сообщение27.11.2011, 05:28 
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: А, всё, понятно. :) Вечно я с шаблонами путаюсь. (Зато последний пример можно рассматривать как альтернативу явному указанию параметров при вызове.)

 
 
 
 Re: C++
Сообщение27.11.2011, 14:22 
venco в сообщении #508662 писал(а):
Вам надо либо в качестве параметра использовать итератор напрямую (как в STL),

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

 
 
 
 Re: C++
Сообщение27.11.2011, 16:53 
Используется синтаксис C++
template <class Iterator, class Comparer>
  void QSort(Iterator begin, Iterator end, Comparer comp) {

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group