Sortowanie takiego vectorlub dowolnego stosownego (niestandardowego iteratora wejściowego) typu obiektów niestandardowych Xmożna osiągnąć za pomocą różnych metod, w tym w szczególności za pomocą standardowych algorytmów bibliotecznych, takich jak
Ponieważ większość technik mających na celu uzyskanie względnego uporządkowania Xelementów została już opublikowana, zacznę od kilku uwag na temat „dlaczego” i „kiedy”, aby zastosować różne podejścia.
Podejście „najlepsze” będzie zależeć od różnych czynników:
- Czy sortowanie zakresów
Xobiektów jest powszechnym czy rzadkim zadaniem (czy takie zakresy będą sortowane na wiele różnych miejsc w programie czy przez użytkowników biblioteki)?
- Czy wymagane sortowanie jest „naturalne” (oczekiwane), czy też istnieje wiele sposobów na porównanie tego typu z samym sobą?
- Czy wydajność stanowi problem, czy też zakresy sortowania
Xobiektów powinny być niezawodne?
Jeśli zakresy sortowania Xsą powszechnym zadaniem i należy oczekiwać osiągniętego sortowania (tj. Po Xprostu otacza jedną podstawową wartość), to prawdopodobnie przejdzie on do przeciążenia, operator<ponieważ umożliwia sortowanie bez żadnych zakłóceń (jak prawidłowe przekazywanie odpowiednich komparatorów) i wielokrotne oczekiwane wyniki wyniki.
Jeśli sortowanie jest częstym zadaniem lub prawdopodobnie będzie wymagane w różnych kontekstach, ale istnieje wiele kryteriów, które można zastosować do sortowania Xobiektów, wybrałbym Functors (przeciążone operator()funkcje klas niestandardowych) lub wskaźniki funkcji (tj. Jeden funktor / funkcja dla porządku leksykalnego i innego dla porządku naturalnego).
Jeśli zakresy sortowania typów Xsą rzadkie lub mało prawdopodobne w innych kontekstach, zwykle używam lambdów zamiast zaśmiecać przestrzeń nazw większą liczbą funkcji lub typów.
Jest to szczególnie prawdziwe, jeśli sortowanie nie jest w jakiś sposób „jasne” lub „naturalne”. Możesz łatwo zrozumieć logikę operator<związaną z porządkowaniem, patrząc na lambda, która jest stosowana w miejscu, podczas gdy na pierwszy rzut oka jest niejasna i trzeba by sprawdzić definicję, aby wiedzieć, która logika porządkowania zostanie zastosowana.
Zauważ jednak, że jedna operator<definicja jest pojedynczym punktem awarii, podczas gdy wiele lambas jest wieloma punktami awarii i wymaga większej ostrożności.
Jeśli definicja operator<nie jest dostępna w miejscu, w którym odbywa się sortowanie / kompilowany jest szablon sortowania, kompilator może zostać zmuszony do wywołania funkcji podczas porównywania obiektów, zamiast wprowadzania logiki porządkowania, co może być poważną wadą (przynajmniej gdy optymalizacja czasu łącza / generowanie kodu nie jest stosowane).
Sposoby osiągnięcia porównywalności class Xw celu użycia standardowych algorytmów sortowania bibliotek
Niech std::vector<X> vec_X;istd::vector<Y> vec_Y;
1. Przeciąż T::operator<(T)lub operator<(T, T)użyj standardowych szablonów bibliotek, które nie oczekują funkcji porównania.
Członek przeciążenia operator<:
struct X {
int i{};
bool operator<(X const &r) const { return i < r.i; }
};
// ...
std::sort(vec_X.begin(), vec_X.end());
lub za darmo operator<:
struct Y {
int j{};
};
bool operator<(Y const &l, Y const &r) { return l.j < r.j; }
// ...
std::sort(vec_Y.begin(), vec_Y.end());
2. Użyj wskaźnika funkcji z niestandardową funkcją porównania jako parametru funkcji sortowania.
struct X {
int i{};
};
bool X_less(X const &l, X const &r) { return l.i < r.i; }
// ...
std::sort(vec_X.begin(), vec_X.end(), &X_less);
3. Utwórz bool operator()(T, T)przeciążenie dla typu niestandardowego, który można przekazać jako funktor porównawczy.
struct X {
int i{};
int j{};
};
struct less_X_i
{
bool operator()(X const &l, X const &r) const { return l.i < r.i; }
};
struct less_X_j
{
bool operator()(X const &l, X const &r) const { return l.j < r.j; }
};
// 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{});
Te definicje obiektów funkcji można zapisać nieco bardziej ogólnie, używając C ++ 11 i szablonów:
struct less_i
{
template<class T, class U>
bool operator()(T&& l, U&& r) const { return std::forward<T>(l).i < std::forward<U>(r).i; }
};
które mogą być użyte do sortowania dowolnego typu z iobsługą elementów <.
4. Przekaż zamknięcie anonimowe (lambda) jako parametr porównawczy do funkcji sortujących.
struct X {
int i{}, j{};
};
std::sort(vec_X.begin(), vec_X.end(), [](X const &l, X const &r) { return l.i < r.i; });
Gdzie C ++ 14 umożliwia jeszcze bardziej ogólne wyrażenie lambda:
std::sort(a.begin(), a.end(), [](auto && l, auto && r) { return l.i < r.i; });
które można zawinąć w makro
#define COMPARATOR(code) [](auto && l, auto && r) -> bool { return code ; }
dzięki czemu tworzenie zwykłego komparatora jest dość płynne:
// sort by i
std::sort(v.begin(), v.end(), COMPARATOR(l.i < r.i));
// sort by j
std::sort(v.begin(), v.end(), COMPARATOR(l.j < r.j));