Сортировка вектора пользовательских объектов

Как можно сортировать вектор, содержащий пользовательские (то есть определенные пользователем) объекты.
Возможно, следует использовать стандартный алгоритм STL-алгоритма наряду с предикатом (функцией или функциональным объектом), который будет работать на одном из полей (в качестве ключа для сортировки) в пользовательском объекте.
Я на правильном пути?

Простой пример с использованием std::sort

 struct MyStruct { int key; std::string stringValue; MyStruct(int k, const std::string& s) : key(k), stringValue(s) {} }; struct less_than_key { inline bool operator() (const MyStruct& struct1, const MyStruct& struct2) { return (struct1.key < struct2.key); } }; std::vector < MyStruct > vec; vec.push_back(MyStruct(4, "test")); vec.push_back(MyStruct(3, "a")); vec.push_back(MyStruct(2, "is")); vec.push_back(MyStruct(1, "this")); std::sort(vec.begin(), vec.end(), less_than_key()); 

Редактировать: Как указал Кирилл В. Лядвинский, вместо подачи предиката сортировки вы можете реализовать operator< для MyStruct :

 struct MyStruct { int key; std::string stringValue; MyStruct(int k, const std::string& s) : key(k), stringValue(s) {} bool operator < (const MyStruct& str) const { return (key < str.key); } }; 

Используя этот метод, вы можете просто отсортировать вектор следующим образом:

 std::sort(vec.begin(), vec.end()); 

Edit2: Как говорит Каппа, вы также можете отсортировать вектор в порядке убывания, перегрузив оператор > и немного изменив вызов сортировки:

 struct MyStruct { int key; std::string stringValue; MyStruct(int k, const std::string& s) : key(k), stringValue(s) {} bool operator > (const MyStruct& str) const { return (key > str.key); } }; 

И вы должны вызвать сортировку как:

 std::sort(vec.begin(), vec.end(),greater()); 

В интересах покрытия. Я предложил реализацию с использованием lambda-выражений .

C ++ 11

 #include  #include  using namespace std; vector< MyStruct > values; sort( values.begin( ), values.end( ), [ ]( const MyStruct& lhs, const MyStruct& rhs ) { return lhs.key < rhs.key; }); 

C ++ 14

 #include  #include  using namespace std; vector< MyStruct > values; sort( values.begin( ), values.end( ), [ ]( const auto& lhs, const auto& rhs ) { return lhs.key < rhs.key; }); 

Вы можете использовать функтор в качестве третьего аргумента std::sort , или вы можете определить operator< в своем classе.

 struct X { int x; bool operator<( const X& val ) const { return x < val.x; } }; struct Xgreater { bool operator()( const X& lx, const X& rx ) const { return lx.x < rx.x; } }; int main () { std::vector my_vec; // use X::operator< by default std::sort( my_vec.begin(), my_vec.end() ); // use functor std::sort( my_vec.begin(), my_vec.end(), Xgreater() ); } 

Ты на правильном пути. std::sort будет использовать operator< как функцию сравнения по умолчанию. Поэтому для сортировки ваших объектов вам придется либо перегрузить bool operator<( const T&, const T& ) либо предоставить функтор, который выполняет сравнение, примерно так:

  struct C { int i; static bool before( const C& c1, const C& c2 ) { return c1.i < c2.i; } }; bool operator<( const C& c1, const C& c2 ) { return c1.i > c2.i; } std::vector values; std::sort( values.begin(), values.end() ); // uses operator< std::sort( values.begin(), values.end(), C::before ); 

Преимущество использования функтора заключается в том, что вы можете использовать функцию с доступом к частным членам classа.

Сортировка такого vector или любого другого применимого (изменяемого входного iteratorа) диапазона пользовательских объектов типа X может быть достигнута с использованием различных методов, в частности, включая использование стандартных библиотечных алгоритмов, таких как

  • sort ,
  • stable_sort ,
  • partial_sort или
  • partial_sort_copy .

Поскольку большинство методов для получения относительного упорядочения элементов X уже были опубликованы, я начну с некоторых заметок о «почему» и «когда» использовать различные подходы.

«Лучший» подход будет зависеть от разных факторов:

  1. Является ли сортировка диапазонов X объектов общей или редкой задачей (будут ли такие диапазоны отсортированы в разных местах в программе или через пользователей библиотеки)?
  2. Является ли требуемая сортировка «естественной» (ожидаемой) или существует несколько способов сопоставления типа с самим собой?
  3. Является ли производительность проблемой или следует сортировать диапазоны объектов X без надежной защиты?

Если диапазоны сортировки X являются общей задачей, и ожидаемая сортировка должна быть ожидаемой (т. Е. X просто обертывает одно фундаментальное значение), то, вероятно, перейдет к перегрузке operator< поскольку он позволяет сортировать без какого-либо fuzz (например, правильно передавать соответствующие компараторы) и многократно дает ожидаемые результаты.

Если сортировка является общей задачей или может потребоваться в разных контекстах, но существует множество критериев, которые можно использовать для сортировки объектов X , я бы пошел на функторы (перегруженные функции operator() пользовательских classов) или указатели на функции (т.е. один функтор / функция для лексического упорядочения и другой для естественного упорядочения).

Если диапазоны сортировки типа X являются необычными или маловероятными в других контекстах, я стараюсь использовать lambdas вместо загромождения любого пространства имен с большим количеством функций или типов.

Это особенно верно, если сортировка не является «ясной» или «естественной». Вы можете легко получить логику, лежащую в основе заказа, когда смотрите на лямбду, которая применяется на месте, тогда как operator< представляет собой непрозрачность с первого взгляда, и вам нужно будет найти определение, чтобы знать, какая логика упорядочения будет применена.

Обратите внимание, однако, что один operator< определение является единственной точкой отказа, тогда как несколько lambas являются множественными точками отказа и требуют большей осторожности.

Если определение operator< недоступно, когда выполняется сортировка / шаблон сортировки скомпилирован, компилятор может быть вынужден сделать вызов функции при сравнении объектов, вместо того, чтобы встраивать логику упорядочения, которая может быть серьезным недостатком (при в наименьшей степени, когда оптимизация времени соединения / генерация кода не применяется).

Способы достижения сопоставимости class X для использования стандартных алгоритмов сортировки библиотек

Пусть std::vector vec_X; и std::vector vec_Y;

1. Перегрузка T::operator<(T) или operator<(T, T) и использование стандартных шаблонов библиотек, которые не ожидают функции сравнения.

operator< элемента перегрузки operator< :

 struct X { int i{}; bool operator<(X const &r) const { return i < ri; } }; // ... std::sort(vec_X.begin(), vec_X.end()); 

или свободный operator< :

 struct Y { int j{}; }; bool operator<(Y const &l, Y const &r) { return lj < rj; } // ... std::sort(vec_Y.begin(), vec_Y.end()); 

2. Используйте указатель функции с пользовательской функцией сравнения как параметр функции сортировки.

 struct X { int i{}; }; bool X_less(X const &l, X const &r) { return li < ri; } // ... std::sort(vec_X.begin(), vec_X.end(), &X_less); 

3. Создайте перегрузку bool operator()(T, T) для настраиваемого типа, который может быть передан как функция сравнения.

 struct X { int i{}; int j{}; }; struct less_X_i { bool operator()(X const &l, X const &r) const { return li < ri; } }; struct less_X_j { bool operator()(X const &l, X const &r) const { return lj < rj; } }; // sort by i std::sort(vec_X.begin(), vec_X.end(), less_X_i{}); // or sort by j std::sort(vec_X.begin(), vec_X.end(), less_X_j{}); 

Эти определения объектов функций могут быть написаны немного более общим с использованием C ++ 11 и шаблонов:

 struct less_i { template bool operator()(T&& l, U&& r) const { return std::forward(l).i < std::forward(r).i; } }; 

который можно использовать для сортировки любого типа с поддержкой элемента i < .

4. Передайте анонимное замыкание (lambda) в качестве параметра сравнения в функции сортировки.

 struct X { int i{}, j{}; }; std::sort(vec_X.begin(), vec_X.end(), [](X const &l, X const &r) { return li < ri; }); 

Где C ++ 14 допускает еще более общее выражение lambda:

 std::sort(a.begin(), a.end(), [](auto && l, auto && r) { return li < ri; }); 

которые могут быть завернуты в макрос

 #define COMPARATOR(code) [](auto && l, auto && r) -> bool { return code ; } 

что делает обычное создание компаратора совершенно гладким:

 // sort by i std::sort(v.begin(), v.end(), COMPARATOR(li < ri)); // sort by j std::sort(v.begin(), v.end(), COMPARATOR(lj < rj)); 

Да, std::sort() с третьим параметром (функцией или объектом) будет проще. Пример: http://www.cplusplus.com/reference/algorithm/sort/

В вашем classе вы можете перегрузить оператор «<».

 class MyClass { bool operator <(const MyClass& rhs) { return this->key < rhs.key; } } 

Ниже приведен код с использованием lambdas

 #include "stdafx.h" #include  #include  using namespace std; struct MyStruct { int key; std::string stringValue; MyStruct(int k, const std::string& s) : key(k), stringValue(s) {} }; int main() { std::vector < MyStruct > vec; vec.push_back(MyStruct(4, "test")); vec.push_back(MyStruct(3, "a")); vec.push_back(MyStruct(2, "is")); vec.push_back(MyStruct(1, "this")); std::sort(vec.begin(), vec.end(), [] (const MyStruct& struct1, const MyStruct& struct2) { return (struct1.key < struct2.key); } ); return 0; } 
  // sort algorithm example #include  // std::cout #include  // std::sort #include  // std::vector using namespace std; int main () { char myints[] = {'F','C','E','G','A','H','B','D'}; vector myvector (myints, myints+8); // 32 71 12 45 26 80 53 33 // using default comparison (operator <): sort (myvector.begin(), myvector.end()); //(12 32 45 71)26 80 53 33 // print out content: cout << "myvector contains:"; for (int i=0; i!=8; i++) cout << ' ' < 

Вы можете использовать определенный пользователем class компаратора.

 class comparator { int x; bool operator()( const comparator &m, const comparator &n ) { return mx 

Чтобы отсортировать вектор, вы можете использовать алгоритм sort () в.

 sort(vec.begin(),vec.end(),less()); 

Третий используемый параметр может быть больше или меньше, или можно использовать любую функцию или объект. Однако по умолчанию оператор <, если вы оставите третий параметр пустым.

 // using function as comp std::sort (myvector.begin()+4, myvector.end(), myfunction); bool myfunction (int i,int j) { return (i 
 typedef struct Freqamp{ double freq; double amp; }FREQAMP; bool struct_cmp_by_freq(FREQAMP a, FREQAMP b) { return a.freq < b.freq; } main() { vector  temp; FREQAMP freqAMP; freqAMP.freq = 330; freqAMP.amp = 117.56; temp.push_back(freqAMP); freqAMP.freq = 450; freqAMP.amp = 99.56; temp.push_back(freqAMP); freqAMP.freq = 110; freqAMP.amp = 106.56; temp.push_back(freqAMP); sort(temp.begin(),temp.end(), struct_cmp_by_freq); } 

если сравнивать false, он будет «заменять».

Мне было любопытно, есть ли какое-либо измеримое влияние на производительность между различными способами вызова std :: sort, поэтому я создал этот простой тест:

 $ cat sort.cpp #include #include #include #include #define COMPILER_BARRIER() asm volatile("" ::: "memory"); typedef unsigned long int ulint; using namespace std; struct S { int x; int y; }; #define BODY { return s1.x*s2.y < s2.x*s1.y; } bool operator<( const S& s1, const S& s2 ) BODY bool Sgreater_func( const S& s1, const S& s2 ) BODY struct Sgreater { bool operator()( const S& s1, const S& s2 ) const BODY }; void sort_by_operator(vector & v){ sort(v.begin(), v.end()); } void sort_by_lambda(vector & v){ sort(v.begin(), v.end(), []( const S& s1, const S& s2 ) BODY ); } void sort_by_functor(vector &v){ sort(v.begin(), v.end(), Sgreater()); } void sort_by_function(vector &v){ sort(v.begin(), v.end(), &Sgreater_func); } const int N = 10000000; vector random_vector; ulint run(void foo(vector &v)){ vector tmp(random_vector); foo(tmp); ulint checksum = 0; for(int i=0;i & v)){ ulint check_sum = 0; // warm up const int WARMUP_ROUNDS = 3; const int TEST_ROUNDS = 10; for(int t=WARMUP_ROUNDS;t--;){ COMPILER_BARRIER(); check_sum += run(foo); COMPILER_BARRIER(); } for(int t=TEST_ROUNDS;t--;){ COMPILER_BARRIER(); auto start = std::chrono::high_resolution_clock::now(); COMPILER_BARRIER(); check_sum += run(foo); COMPILER_BARRIER(); auto end = std::chrono::high_resolution_clock::now(); COMPILER_BARRIER(); auto duration_ns = std::chrono::duration_cast>(end - start).count(); cout << "Took " << duration_ns << "s to complete round" << endl; } cout << "Checksum: " << check_sum << endl; } #define M(x) \ cout << "Measure " #x " on " << N << " items:" << endl;\ measure(x); int main(){ random_vector.reserve(N); for(int i=0;i 

Он создает случайный вектор, а затем измеряет, сколько времени требуется для его копирования и сортировки его копии (и вычислить некоторую контрольную сумму, чтобы избежать слишком сильного удаления кода).

Я компилировал с g ++ (GCC) 7.2.1 20170829 (Red Hat 7.2.1-1)

 $ g++ -O2 -o sort sort.cpp && ./sort 

Вот результаты:

 Measure sort_by_operator on 10000000 items: Took 0.994285s to complete round Took 0.990162s to complete round Took 0.992103s to complete round Took 0.989638s to complete round Took 0.98105s to complete round Took 0.991913s to complete round Took 0.992176s to complete round Took 0.981706s to complete round Took 0.99021s to complete round Took 0.988841s to complete round Checksum: 18446656212269526361 Measure sort_by_lambda on 10000000 items: Took 0.974274s to complete round Took 0.97298s to complete round Took 0.964506s to complete round Took 0.96899s to complete round Took 0.965773s to complete round Took 0.96457s to complete round Took 0.974286s to complete round Took 0.975524s to complete round Took 0.966238s to complete round Took 0.964676s to complete round Checksum: 18446656212269526361 Measure sort_by_functor on 10000000 items: Took 0.964359s to complete round Took 0.979619s to complete round Took 0.974027s to complete round Took 0.964671s to complete round Took 0.964764s to complete round Took 0.966491s to complete round Took 0.964706s to complete round Took 0.965115s to complete round Took 0.964352s to complete round Took 0.968954s to complete round Checksum: 18446656212269526361 Measure sort_by_function on 10000000 items: Took 1.29942s to complete round Took 1.3029s to complete round Took 1.29931s to complete round Took 1.29946s to complete round Took 1.29837s to complete round Took 1.30132s to complete round Took 1.3023s to complete round Took 1.30997s to complete round Took 1.30819s to complete round Took 1.3003s to complete round Checksum: 18446656212269526361 

Похоже, что все параметры, кроме указателя функции, очень похожи, а передача указателя функции вызывает + 30% -ный штраф.

Он также выглядит как оператор <версия на ~ 1% медленнее (я повторял тест несколько раз, и эффект сохраняется), что немного странно, поскольку предполагает, что сгенерированный код отличается (мне не хватает навыков для анализа --save- выход temps).

  • Сортировка массивов примитивных типов в порядке убывания
  • Порядок LINQ по нулевому столбцу, где порядок возрастает, а null должны быть последними
  • Найти подходящее или ближайшее значение в массиве
  • Сортировка ArrayList массива в Java
  • Сортировка массива объекта по свойству (с пользовательским порядком, а не в алфавитном порядке)
  • Быстрая сортировка Vs Merge Sort
  • Найти пару через 2 массива с k-й наибольшей суммой
  • Функция библиотеки C для сортировки
  • MySQL: Сортировка значений GROUP_CONCAT
  • Сортировка поля varchar численно в MySQL
  • Пользовательская логика сортировки в OrderBy с использованием LINQ
  • Давайте будем гением компьютера.