C++
Sortierung

Bemerkungen

Sortierreihenfolge Container mit vorgegebener Reihenfolge

Wenn die Werte in einem Container bestimmte Operatoren bereits überladen haben, kann std::sort mit spezialisierten Funktionen verwendet werden, um entweder aufsteigend oder absteigend zu sortieren:

#include <vector>
#include <algorithm>
#include <functional>

std::vector<int> v = {5,1,2,4,3};

//sort in ascending order (1,2,3,4,5)
std::sort(v.begin(), v.end(), std::less<int>());

// Or just:
std::sort(v.begin(), v.end());

//sort in descending order (5,4,3,2,1)
std::sort(v.begin(), v.end(), std::greater<int>());

//Or just:
std::sort(v.rbegin(), v.rend());

std::sort(v.begin(), v.end(), std::less<>());     // ascending order
std::sort(v.begin(), v.end(), std::greater<>());  // descending order

Sortierreihenfolge-Container durch überladenen Operator weniger

Wenn keine Sortierfunktion übergeben wird, ordnet std::sort die Elemente durch Aufruf des operator< in Elementpaaren an, der einen Typ zurückgeben muss, der in bool (oder einfach in bool ) konvertierbar ist. Grundtypen (Ganzzahlen, Gleitkommazahlen, Zeiger usw.) haben bereits Vergleichsoperatoren eingebaut.

Wir können diesen Operator überlasten die Standardeinstellung zu machen sort Anruf Arbeit auf benutzerdefinierte Typen.

// Include sequence containers
#include <vector>
#include <deque>
#include <list>

// Insert sorting algorithm
#include <algorithm>    

class Base {
 public:

    // Constructor that set variable to the value of v
    Base(int v): variable(v) {
    }
    
    // Use variable to provide total order operator less
    //`this` always represents the left-hand side of the compare.
    bool operator<(const Base &b) const { 
        return this->variable < b.variable;
    }
    
    int variable;
};

int main() {
    std::vector <Base> vector;
    std::deque <Base> deque;
    std::list <Base> list;
    
    // Create 2 elements to sort
    Base a(10);
    Base b(5);
    
    // Insert them into backs of containers
    vector.push_back(a);
    vector.push_back(b);
    
    deque.push_back(a);
    deque.push_back(b);
    
    list.push_back(a);
    list.push_back(b);
    
    // Now sort data using operator<(const Base &b) function
    std::sort(vector.begin(), vector.end());
    std::sort(deque.begin(), deque.end());
    // List must be sorted differently due to its design
    list.sort();

    return 0;
}

Sequenzcontainer mit der Compare-Funktion sortieren

// Include sequence containers
#include <vector>
#include <deque>
#include <list>

// Insert sorting algorithm
#include <algorithm>

class Base {
 public:

    // Constructor that set variable to the value of v
    Base(int v): variable(v) {
    }
       
    int variable;
};

bool compare(const Base &a, const Base &b) {
    return a.variable < b.variable;
}

int main() {
    std::vector <Base> vector;
    std::deque <Base> deque;
    std::list <Base> list;
    
    // Create 2 elements to sort
    Base a(10);
    Base b(5);
    
    // Insert them into backs of containers
    vector.push_back(a);
    vector.push_back(b);
    
    deque.push_back(a);
    deque.push_back(b);
    
    list.push_back(a);
    list.push_back(b);
    
    // Now sort data using comparing function
    std::sort(vector.begin(), vector.end(), compare);
    std::sort(deque.begin(), deque.end(), compare);
    list.sort(compare);

    return 0;
}

Sequenzcontainer mit Lambda-Ausdrücken sortieren (C ++ 11)

// Include sequence containers
#include <vector>
#include <deque>
#include <list>
#include <array>
#include <forward_list>

// Include sorting algorithm
#include <algorithm>

class Base {
 public:

    // Constructor that set variable to the value of v
    Base(int v): variable(v) {
    }
    
    int variable;
};


int main() {
    // Create 2 elements to sort
    Base a(10);
    Base b(5);
    
    // We're using C++11, so let's use initializer lists to insert items.
    std::vector <Base> vector = {a, b};
    std::deque <Base> deque = {a, b};
    std::list <Base> list = {a, b};
    std::array <Base, 2> array = {a, b};
    std::forward_list<Base> flist = {a, b};
    
    // We can sort data using an inline lambda expression
    std::sort(std::begin(vector), std::end(vector),
      [](const Base &a, const Base &b) { return a.variable < b.variable;});

    // We can also pass a lambda object as the comparator
    // and reuse the lambda multiple times
    auto compare = [](const Base &a, const Base &b) {
                     return a.variable < b.variable;};
    std::sort(std::begin(deque), std::end(deque), compare);
    std::sort(std::begin(array), std::end(array), compare);
    list.sort(compare);
    flist.sort(compare);

    return 0;
}

Container sortieren und sortieren

std::sort , im Standard-Bibliotheks-Header- algorithm , ist ein Standard-Bibliotheksalgorithmus zum Sortieren eines Wertebereichs, der von einem Iteratorpaar definiert wird. std::sort wird als letzter Parameter ein Functor verwendet, mit dem zwei Werte verglichen werden. So bestimmt es die Reihenfolge. Beachten Sie, dass std::sort nicht stabil ist .

Die Vergleichsfunktion muss den Elementen eine strikte, schwache Anordnung auferlegen. Ein einfacher Vergleich (oder mehr als) ist ausreichend.

Ein Container mit Iteratoren mit wahlfreiem Zugriff kann mit dem std::sort Algorithmus std::sort werden:

#include <vector>
#include <algorithm>

std::vector<int> MyVector = {3, 1, 2}

//Default comparison of <
std::sort(MyVector.begin(), MyVector.end());

std::sort müssen die Iteratoren Random-Access-Iteratoren sein. Die std::forward_list std::list und std::forward_list (für die C ++ 11 erforderlich ist) bieten keine Iteratoren mit wahlfreiem Zugriff, daher können sie nicht mit std::sort . Sie verfügen jedoch über sort , die einen Sortieralgorithmus implementieren, der mit ihren eigenen Iteratortypen arbeitet.

#include <list>
#include <algorithm>

std::list<int> MyList = {3, 1, 2}

//Default comparison of <
//Whole list only.
MyList.sort();

Ihre Mitglieder- sort immer die gesamte Liste, sodass sie keinen Teilbereich von Elementen sortieren können. Da list und forward_list jedoch schnelle Verknüpfungsoperationen haben, können Sie die zu sortierenden Elemente aus der Liste extrahieren, sortieren und dann dorthin zurückstellen, wo sie ziemlich effizient waren:

void sort_sublist(std::list<int>& mylist, std::list<int>::const_iterator start, std::list<int>::const_iterator end) {
    //extract and sort half-open sub range denoted by start and end iterator 
    std::list<int> tmp;
    tmp.splice(tmp.begin(), list, start, end);
    tmp.sort();
    //re-insert range at the point we extracted it from
    list.splice(end, tmp);
}

Sortierung mit std :: map (aufsteigend und absteigend)

In diesem Beispiel werden Elemente in aufsteigender Reihenfolge eines Schlüssels anhand einer Karte sortiert. Sie können im folgenden Beispiel anstelle von std::string einen beliebigen Typ verwenden, einschließlich class.

#include <iostream>
#include <utility>
#include <map>

int main()
{
    std::map<double, std::string> sorted_map;
    // Sort the names of the planets according to their size
    sorted_map.insert(std::make_pair(0.3829, "Mercury"));
    sorted_map.insert(std::make_pair(0.9499, "Venus"));
    sorted_map.insert(std::make_pair(1,      "Earth"));
    sorted_map.insert(std::make_pair(0.532,  "Mars"));
    sorted_map.insert(std::make_pair(10.97,  "Jupiter"));
    sorted_map.insert(std::make_pair(9.14,   "Saturn"));
    sorted_map.insert(std::make_pair(3.981,  "Uranus"));
    sorted_map.insert(std::make_pair(3.865,  "Neptune"));

    for (auto const& entry: sorted_map)
    {
        std::cout << entry.second << " (" << entry.first << " of Earth's radius)" << '\n';
    }
}

Ausgabe:

Mercury (0.3829 of Earth's radius)
Mars (0.532 of Earth's radius)
Venus (0.9499 of Earth's radius)
Earth (1 of Earth's radius)
Neptune (3.865 of Earth's radius)
Uranus (3.981 of Earth's radius)
Saturn (9.14 of Earth's radius)
Jupiter (10.97 of Earth's radius)

Wenn Einträge mit gleichen Schlüsseln möglich sind, verwenden Sie multimap anstelle von map (wie im folgenden Beispiel).

Um Elemente absteigend zu sortieren, deklarieren Sie die Karte mit einem entsprechenden Vergleichsfunktionscode ( std::greater<> ):

#include <iostream>
#include <utility>
#include <map>

int main()
{
    std::multimap<int, std::string, std::greater<int>> sorted_map;
    // Sort the names of animals in descending order of the number of legs
    sorted_map.insert(std::make_pair(6,   "bug"));
    sorted_map.insert(std::make_pair(4,   "cat"));
    sorted_map.insert(std::make_pair(100, "centipede"));
    sorted_map.insert(std::make_pair(2,   "chicken"));
    sorted_map.insert(std::make_pair(0,   "fish"));
    sorted_map.insert(std::make_pair(4,   "horse"));
    sorted_map.insert(std::make_pair(8,   "spider"));

    for (auto const& entry: sorted_map)
    {
        std::cout << entry.second << " (has " << entry.first << " legs)" << '\n';
    }
}

Ausgabe

centipede (has 100 legs)
spider (has 8 legs)
bug (has 6 legs)
cat (has 4 legs)
horse (has 4 legs)
chicken (has 2 legs)
fish (has 0 legs)

Eingebaute Arrays sortieren

Der sort sortiert eine Sequenz von zwei Iteratoren definiert. Dies reicht aus, um ein eingebautes Array (auch als c-Stil bezeichnet) zu sortieren.

int arr1[] = {36, 24, 42, 60, 59};

// sort numbers in ascending order
sort(std::begin(arr1), std::end(arr1));

// sort numbers in descending order
sort(std::begin(arr1), std::end(arr1), std::greater<int>());

Vor C ++ 11 musste das Ende des Arrays anhand der Größe des Arrays "berechnet" werden:

// Use a hard-coded number for array size
sort(arr1, arr1 + 5);

// Alternatively, use an expression
const size_t arr1_size = sizeof(arr1) / sizeof(*arr1);
sort(arr1, arr1 + arr1_size);