Jak posortować wektor par na podstawie drugiego elementu pary?

133

Jeśli mam wektor par:

std::vector<std::pair<int, int> > vec;

Czy istnieje łatwy sposób sortowania listy w kolejności rosnącej na podstawie drugiego elementu pary?

Wiem, że mogę napisać mały obiekt funkcyjny, który wykona pracę, ale czy istnieje sposób na użycie istniejących części STL i std::lesswykonanie tej pracy bezpośrednio?

EDYCJA: Rozumiem, że mogę napisać oddzielną funkcję lub klasę, która będzie przekazywana do trzeciego argumentu do sortowania. Pytanie brzmi, czy mogę go zbudować ze standardowych rzeczy. Naprawdę chciałbym coś, co wygląda jak:

std::sort(vec.begin(), vec.end(), std::something_magic<int, int, std::less>());
David Norman
źródło
Oto przykład: <br> std :: sort w wektorze par
LeppyR64
1
c ++ nie ma lamd, więc nie możesz robić dokładnie tego, co chcesz, musisz utworzyć osobną funkcję / funktor. Może to być jedna linijka, więc to naprawdę nie powinno być wielkim problemem.
Evan Teran,
1
C ++ ma teraz lambdy! Zabiegać!
David Poole,

Odpowiedzi:

219

EDYCJA : używając c ++ 14, najlepsze rozwiązanie jest bardzo łatwe do napisania dzięki lambdom, które mogą teraz mieć parametry typu auto. To moje obecnie ulubione rozwiązanie

std::sort(v.begin(), v.end(), [](auto &left, auto &right) {
    return left.second < right.second;
});

Po prostu użyj niestandardowego komparatora (jest to opcjonalny trzeci argument do std::sort)

struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
        return left.second < right.second;
    }
};

std::sort(v.begin(), v.end(), sort_pred());

Jeśli używasz kompilatora C ++ 11, możesz napisać to samo używając lambd:

std::sort(v.begin(), v.end(), [](const std::pair<int,int> &left, const std::pair<int,int> &right) {
    return left.second < right.second;
});

EDYTUJ : w odpowiedzi na zmiany w Twoim pytaniu, oto kilka przemyśleń ... jeśli naprawdę chcesz być kreatywny i móc wielokrotnie wykorzystywać tę koncepcję, po prostu utwórz szablon:

template <class T1, class T2, class Pred = std::less<T2> >
struct sort_pair_second {
    bool operator()(const std::pair<T1,T2>&left, const std::pair<T1,T2>&right) {
        Pred p;
        return p(left.second, right.second);
    }
};

wtedy też możesz to zrobić:

std::sort(v.begin(), v.end(), sort_pair_second<int, int>());

lub nawet

std::sort(v.begin(), v.end(), sort_pair_second<int, int, std::greater<int> >());

Chociaż szczerze mówiąc, to wszystko jest trochę przesadzone, po prostu napisz funkcję 3-liniową i skończ z tym :-P

Evan Teran
źródło
Pamiętaj, że to różni się od operator<in pair<T1,T2>. Domyślny komparator używa zarówno pierwszego, jak i drugiego elementu (w przypadku, gdy pierwsze są równe). Tutaj używany jest tylko drugi.
Googol
@Googol: Właśnie o to prosił OP ... Powiedział: "is there and easy way to sort the list in increasing order based on the second element of the pair?"
Evan Teran
@ evan-teran, tak, wiem. Wskazałem tylko, że jeśli oba elementy sekund są równe, wynik może być mylący (na przykład, jeśli jest używany do sortowania). Ten problem nie występuje w przypadku domyślnego komparatora, ponieważ używa drugiego elementu do rozstrzygania remisów. Doszedłem do tego pytania, szukając komparatora, który używałby drugiego elementu jako głównej informacji do porównań, ale potrzebowałem również, aby używał pierwszego do rozstrzygania remisów, więc chciałbym, aby inni nie przegapili tego punktu (ponieważ ja, w fakt, zrobił).
Googol
71

Możesz użyć wzmocnienia w ten sposób:

std::sort(a.begin(), a.end(), 
          boost::bind(&std::pair<int, int>::second, _1) <
          boost::bind(&std::pair<int, int>::second, _2));

Nie znam standardowego sposobu na zrobienie tego równie krótkiego i zwięzłego, ale możesz złapać boost::bindto wszystko składa się z nagłówków.

Johannes Schaub - litb
źródło
1
+1 za użycie wzmocnienia. Przy okazji, z nowoczesnym kompilatorem prawdopodobnie mógłbyś już zamienić boost na std :: tr1, ponieważ wkrótce będzie to standard.
Andreas Magnusson
Niestety, próbowałem tego samego z c ++ 1x std :: bind gcc trunk, ale nie udało się, ponieważ nie ma op <dla bind. nie wiem jednak, czy co c ++ 1x mówi o tym. prawdopodobnie mówi ci, żebyś użył do tego lambdy :)
Johannes Schaub - litb
1
Przypuszczam, że wzmocnienie nie jest standardowe, ale jest wystarczająco blisko. :-)
David Norman
Opublikowałem tutaj pytania
uzupełniające
35

To całkiem proste, gdy używasz funkcji sortowania z algorytmu i dodajesz własną funkcję porównującą

vector< pair<int,int > > v;
sort(v.begin(),v.end(),myComparison);

Teraz musisz dokonać porównania na podstawie drugiego wyboru, więc zadeklaruj jako „mojePorównanie” jako

bool myComparison(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
Ezio
źródło
5
Prosto i na temat". Nie wymaga ulepszenia ani określonej wersji C ++. +1
Thomio
1
Należy to oznaczyć jako najlepsze rozwiązanie. Nie potrzebuje c ++ 14, aby to zaimplementować.
Kartik Chauhan
Czy możesz mi wyjaśnić, jak działa to porównanie? Czy przekazujemy jednocześnie dwa elementy do funkcji myComparision, a następnie w jaki sposób może ona sortować? Ponadto, jaką rolę odgrywa a.second <b.second?
era s'q
Funkcja myComparison jest wywoływana przez funkcję sortowania, w której funkcja sort wysyła dwie wartości i oczekuje wartości True lub False, aby określić, który element powinien być umieszczony jako pierwszy, a który jako drugi, więc w ten sposób funkcja porównania pomaga deweloper, aby zdefiniować własną definicję większego niż i mniejszego niż
Ezio
30

W C ++ 0x możemy użyć funkcji lambda:

using namespace std;
vector<pair<int, int>> v;
        .
        .
sort(v.begin(), v.end(),
     [](const pair<int, int>& lhs, const pair<int, int>& rhs) {
             return lhs.second < rhs.second; } );

W tym przykładzie zwracany typ booljest niejawnie wywnioskowany.

Zwracane typy lambda

Gdy funkcja lambda ma pojedynczą instrukcję, a jest to instrukcja powrotu, kompilator może wydedukować zwracany typ. Z C ++ 11, §5.1.2 / 4:

...

  • Jeśli instrukcja-złożona ma postać { return expression ; }typu zwracanego wyrażenia po konwersji l-wartości do r-wartości (4.1), konwersji tablicy na wskaźnik (4.2) i konwersji funkcji do wskaźnika (4.3);
  • w przeciwnym razie void.

Aby jawnie określić zwracany typ, użyj formularza []() -> Type { }, takiego jak:

sort(v.begin(), v.end(),
     [](const pair<int, int>& lhs, const pair<int, int>& rhs) -> bool {
             if (lhs.second == 0)
                 return true;
             return lhs.second < rhs.second; } );
Andreas Spindler
źródło
1
Dlaczego if (lhs.second == 0)?
świnia
Bez szczególnego znaczenia; lhs.second < rhs.secondmoże zwrócić truelub falsei kompilator może jasno wywnioskować bool. Chciałem tylko zademonstrować []() -> Type { }sprawę.
Andreas Spindler
Przynajmniej z clang, ta niejawna dedukcja może nie działać poprawnie, musiałem dodać -> bool jako typ powrotu lambda, aby działał poprawnie.
MoDJ,
5

Na coś wielokrotnego użytku:

template<template <typename> class P = std::less >
struct compare_pair_second {
    template<class T1, class T2> bool operator()(const std::pair<T1, T2>& left, const std::pair<T1, T2>& right) {
        return P<T2>()(left.second, right.second);
    }
};

Możesz go używać jako

std::sort(foo.begin(), foo.end(), compare_pair_second<>());

lub

std::sort(foo.begin(), foo.end(), compare_pair_second<std::less>());
Leon Timmermans
źródło
1

Musiałbyś polegać na niestandardowym select2nd

Greg Rogers
źródło
-1

Spróbuj zamienić elementy par, aby móc std::sort()normalnie używać .

hadizadeh.ali
źródło