Wie sortiere ich einen Vektor von Paaren basierend auf dem zweiten Element des Paares?

133

Wenn ich einen Paarvektor habe:

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

Gibt es eine einfache Möglichkeit, die Liste in aufsteigender Reihenfolge nach dem zweiten Element des Paares zu sortieren?

Ich weiß, dass ich ein kleines Funktionsobjekt schreiben kann, das die Arbeit erledigt, aber gibt es eine Möglichkeit, vorhandene Teile der STL zu verwenden und std::lessdie Arbeit direkt zu erledigen?

EDIT: Ich verstehe, dass ich eine separate Funktion oder Klasse schreiben kann, um sie zum Sortieren an das dritte Argument zu übergeben. Die Frage ist, ob ich es aus Standardmaterial bauen kann oder nicht. Ich hätte wirklich etwas, das aussieht wie:

std::sort(vec.begin(), vec.end(), std::something_magic<int, int, std::less>());
David Norman
quelle
Hier ist ein Beispiel: <br> std :: sort in einem Vektor von Paaren
LeppyR64
1
c ++ hat keine Lamdas, so dass Sie nicht genau das tun können, was Sie wollen. Sie müssen eine separate Funktion / Funktion erstellen. Dies kann ein Einzeiler sein, also sollte es wirklich keine große Sache sein.
Evan Teran
1
C ++ hat jetzt Lambdas! Umwerben!
David Poole

Antworten:

212

BEARBEITEN : Mit c ++ 14 ist die beste Lösung dank Lambdas, die jetzt Parameter vom Typ haben können, sehr einfach zu schreiben auto. Dies ist meine derzeitige Lieblingslösung

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

Verwenden Sie einfach einen benutzerdefinierten Komparator (dies ist ein optionales drittes Argument für 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());

Wenn Sie einen C ++ 11-Compiler verwenden, können Sie dasselbe mit Lambdas schreiben:

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

BEARBEITEN : Als Antwort auf Ihre Änderungen an Ihrer Frage sind hier einige Gedanken ... Wenn Sie wirklich kreativ sein und dieses Konzept häufig wiederverwenden möchten, erstellen Sie einfach eine Vorlage:

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);
    }
};

dann kannst du das auch machen:

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

oder auch

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

Um ehrlich zu sein, ist das alles ein bisschen übertrieben. Schreiben Sie einfach die 3-Zeilen-Funktion und fertig :-P

Evan Teran
quelle
Denken Sie daran, dass dies anders ist als operator<in pair<T1,T2>. Der Standardkomparator verwendet sowohl das erste als auch das zweite Element (falls die ersten gleich sind). Hier wird nur der zweite verwendet.
Googol
@ Googol: Genau darum hat das OP gebeten ... Er sagte: "is there and easy way to sort the list in increasing order based on the second element of the pair?"
Evan Teran
@ evan-teran, ja, ich weiß. Ich habe nur angegeben, dass das Ergebnis verwirrend sein kann, wenn beide Sekundenelemente gleich sind (wenn es beispielsweise zum Sortieren verwendet wird). Dieses Problem tritt beim Standardkomparator nicht auf, da er das zweite Element zum Brechen von Bindungen verwendet. Ich kam zu dieser Frage und suchte nach einem Komparator, der das zweite Element als Hauptinformation für den Vergleich verwendete, aber ich brauchte auch das erste Element zum Brechen der Krawatte, damit ich vermeiden möchte, dass andere diesen Punkt verpassen (wie ich in Tatsache, tat).
Googol
71

Sie können Boost wie folgt verwenden:

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

Ich kenne keinen Standardweg, um dies ebenso kurz und prägnant zu machen, aber Sie können sich vorstellen, boost::binddass alles aus Überschriften besteht.

Johannes Schaub - litb
quelle
1
+1 für die Verwendung von Boost. Übrigens, mit einem modernen Compiler könnten Sie Boost wahrscheinlich bereits durch std :: tr1 ersetzen, da dies bald im Standard sein wird.
Andreas Magnusson
Leider habe ich das gleiche mit c ++ 1x std :: bind von gcc trunk versucht, und es ist fehlgeschlagen, weil es nicht die Option op <for bind hat. Keine Ahnung, ob das, was c ++ 1x dazu sagt. wahrscheinlich sagt es dir, dass du Lambda dafür verwenden sollst :)
Johannes Schaub - litb
1
Ich nehme an, Boost ist nicht Standard, aber es ist nah genug. :-)
David Norman
Postete eine
Folgefrage
34

Es ist ziemlich einfach, wenn Sie die Sortierfunktion des Algorithmus verwenden und Ihre eigene Vergleichsfunktion hinzufügen

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

Jetzt müssen Sie den Vergleich anhand der zweiten Auswahl durchführen und deklarieren Sie "myComparison" als

bool myComparison(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
Ezio
quelle
5
Einfach und "auf den Punkt". Benötigt keinen Boost oder eine bestimmte C ++ - Version. +1
Thomio
1
Dies sollte als die beste Lösung markiert werden. Benötigt kein C ++ 14, um es zu implementieren.
Kartik Chauhan
Können Sie mir erklären, wie dieser Vergleich funktioniert? Übergeben wir zwei Elemente gleichzeitig an myComparision, wie kann es dann sortieren? Welche Rolle spielt a.second <b.second?
Ära s'q
30

Mit C ++ 0x können wir Lambda-Funktionen verwenden:

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; } );

In diesem Beispiel der Rückgabetyp bool implizit abgeleitet.

Lambda-Rückgabetypen

Wenn eine Lambda-Funktion eine einzelne Anweisung hat und dies eine return-Anweisung ist, kann der Compiler den Rückgabetyp ableiten. Ab C ++ 11, §5.1.2 / 4:

...

  • Wenn die zusammengesetzte Anweisung die Form hat { return expression ; } den Typ des zurückgegebenen Ausdrucks nach der Konvertierung von Wert zu Wert (4.1), der Konvertierung von Array zu Zeiger (4.2) und der Konvertierung von Funktion zu Zeiger (4.3);
  • sonst , void.

Um den Rückgabetyp explizit anzugeben, verwenden Sie das folgende Formular []() -> Type { }:

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
quelle
1
Warum if (lhs.second == 0)?
das Schwein
Keine besondere Bedeutung; lhs.second < rhs.secondkann zurückkehren trueoder falseund der Compiler kann eindeutig ableiten bool. Ich wollte nur den []() -> Type { }Fall demonstrieren .
Andreas Spindler
Zumindest mit clang funktioniert dieser implizite Abzug möglicherweise nicht richtig. Ich musste -> bool als Lambda-Rückgabetyp hinzufügen, damit er richtig funktioniert.
MoDJ
5

Für etwas wiederverwendbares:

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);
    }
};

Sie können es als verwenden

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

oder

std::sort(foo.begin(), foo.end(), compare_pair_second<std::less>());
Leon Timmermans
quelle
-1

Versuchen Sie, die Elemente der Paare auszutauschen, damit Sie sie std::sort()wie gewohnt verwenden können.

hadizadeh.ali
quelle