Welcher STL-Container eignet sich am besten für std :: sort? (Ist es überhaupt wichtig?)

Question

Der Titel spricht für sich selbst ....

Beeinflusst die Wahl des Containers die Geschwindigkeit des Standardstandards std :: sort irgendwie oder nicht? Wenn ich zum Beispiel eine Liste verwende, schaltet der Sortieralgorithmus einfach die Knotenzeiger um oder wechselt er die gesamten Daten in den Knoten?

Answer 1

Ich glaube nicht, std::sort Werke auf Listen, da sie einen Direktzugriffs Iterator erfordert, die von einem list<> nicht vorgesehen ist. Beachten Sie, dass eine sort-Methode bereitstellt, die jedoch vollständig von std::sort getrennt ist.

Die Wahl des Behälters ist wichtig. STLs std::sort beruht auf Iteratoren, um die Art und Weise, in der ein Container Daten speichert, zu abstrahieren. Es verwendet nur die Iteratoren, die Sie bereitstellen, um Elemente zu verschieben. Je schneller diese Iteratoren hinsichtlich des Zugriffs und der Zuweisung eines Elements arbeiten, desto schneller würde die std::sort funktionieren.

Answer 2

Es hängt vom Elementtyp ab.

Wenn Sie nur Zeiger (oder POD) speichern, wird Vektor am schnellsten sein. Wenn Sie Objekte speichern, ist die Sortierung der Liste schneller, da Knoten und nicht physische Elemente ausgetauscht werden.

Answer 3

Der Sortieralgorithmus weiß nichts über Ihren Container. Alles, was es weiß, sind Random-Access-Iteratoren. So können Sie Dinge sortieren, die nicht einmal in einem STL-Container sind. Wie schnell es sein wird, hängt von den Iteratoren ab, die Sie ihm geben, und wie schnell es ist, zu demeferenzieren und zu kopieren, worauf es hinweist.

std :: sort funktioniert nicht auf std :: list, da sort wahlfreie Zugriff Iteratoren erfordert. Sie sollten für diesen Fall eine der Sortierfunktionen von std :: list verwenden. Diese Member-Funktionen tauschen effizient verknüpfte Listenzeiger aus, anstatt Elemente zu kopieren.

Answer 4

std::list ist definitiv keine gute (gültige) Wahl für std::sort(), weil std::sort() Random-Access-Iteratoren erfordert. std::map und Freunde sind auch nicht gut, weil die Position eines Elements nicht durchgesetzt werden kann; Das heißt, die Position eines Elements in einer Karte kann vom Benutzer nicht durch Einfügen in eine bestimmte Position oder einen Austausch erzwungen werden. Unter den Standard-Containern sind wir std::vector und std::deque.

std::sort() ist wie andere Standardalgorithmen, in dem es nur durch den Austausch von Elementen Werte um (*t = *s) handelt. Selbst wenn die Liste magisch den O (1) -Zugang unterstützen würde, würden die Links nicht reorganisiert, sondern ihre Werte würden vertauscht werden.

Da std::sort() die Größe des Containers nicht ändert, sollte es keinen Unterschied in der Laufzeitleistung geben, ob Sie std::vector oder std::deque verwenden. Primitive Arrays sollten auch schnell zu sortieren sein, wahrscheinlich sogar schneller als die Standardcontainer - aber ich erwarte nicht, dass der Geschwindigkeitsunterschied signifikant genug ist, um ihre Verwendung zu rechtfertigen.

Answer 5

Es ist sicherlich wichtig, nur weil verschiedene Container unterschiedliche Speicherzugriffsmuster usw. haben, die eine Rolle spielen könnten.

Allerdings funktioniert std::sort nicht auf std::list<>::iterators, da diese nicht RandomAccessIterators sind. Darüber hinaus, obwohl es möglich wäre, eine Spezialisierung für zu implementieren, die die Zeiger der Knoten mischen würde, hätte es wahrscheinlich seltsame und überraschende semantische Konsequenzen - z.Wenn Sie einen Iterator innerhalb des sortierten Bereichs in einem Vektor haben, ändert sich sein Wert nach der Sortierung, was bei dieser Spezialisierung nicht der Fall wäre.

Answer 6

Die Wahl macht einen Unterschied, aber voraussagen, welcher Container der effizienteste ist, ist sehr schwierig. Der beste Ansatz ist es, den Container zu verwenden, der am einfachsten für Ihre Anwendung funktioniert (wahrscheinlich std :: vector), um zu sehen, ob die Sortierung mit diesem Container ausreichend schnell ist, und wenn ja, bleiben Sie dabei. Wenn nicht, führen Sie eine Leistungsprofilerstellung für Ihr Sortierproblem durch und wählen Sie basierend auf den Profildaten einen anderen Container aus.

Als Ex-Dozent und Ex-Trainer fühle ich mich manchmal persönlich verantwortlich für die gemeinsame Idee, dass eine verkettete Liste mystische leistungssteigernde Eigenschaften hat. Nehmen Sie es von jemandem, der es weiß: Der einzige Grund, warum eine verkettete Liste in so vielen Lehrbüchern und Tutorien erscheint, ist, dass die Leute, die diese Bücher und Tutorials geschrieben haben, eine Datenstruktur haben, die Zeiger, dynamische Speicherverwaltung, Rekursion darstellen kann alles suchen und sortieren - das hat nichts mit Effizienz zu tun.

Answer 7

std :: sort erfordert Direktzugriffs-Iteratoren. Sie können also nur Vektor oder Deque verwenden. Es wird die Werte tauschen, und bei einem Ratenvektor wird es wahrscheinlich etwas schneller als Deque sein, weil es typischerweise eine einfachere zugrundeliegende Datenstruktur hat. Der Unterschied ist jedoch wahrscheinlich sehr gering.

Wenn Sie eine std :: list verwenden, gibt es eine Spezialisierung (std :: list :: sort), die die Zeiger anstelle der Werte tauschen sollte. Da es sich jedoch nicht um einen Direktzugriff handelt, wird Mergesort anstelle von Quicksort verwendet, was wahrscheinlich bedeutet, dass der Algorithmus selbst etwas langsamer ist.

Wie auch immer, ich denke, die Antwort ist normalerweise Vektor. Wenn Sie für jedes Element große Klassen haben, wird der Sortiervorgang durch den Kopieraufwand dominiert. Alternativ können Sie Zeiger auf sie in einem Vektor speichern und ein benutzerdefiniertes Prädikat bereitstellen, um sie entsprechend zu sortieren.

Answer 8

Vektor.

Verwenden Sie immer Vektor als Standard. Es hat die geringsten Platzkosten und den schnellsten Zugriff auf andere Container (neben anderen Vorteilen wie C-kompatible Layout- und Random-Access-Iteratoren).

Nun, fragen Sie sich - was machen Sie noch mit Ihrem Container? Brauchen Sie starke Ausnahmegarantien? List, Set und Map sind wahrscheinlich bessere Optionen (obwohl sie alle ihre eigenen Sortierroutinen haben). Müssen Sie regelmäßig Elemente an der Vorderseite Ihres Containers hinzufügen? Betrachten Sie deque. Muss Ihr Container immer sortiert haben? Set und Map sind wahrscheinlich besser geeignet.

Schließlich herauszufinden, was "am besten" für Sie ist und dann wählen Sie die am besten geeigneten Container und messen, wie es für Ihre Bedürfnisse erfüllt.

Answer 9

Ich bin absolut einverstanden mit den Aussagen, die die Jungs oben gepostet haben. Aber was ist der beste Weg, um neue Dinge zu lernen? Hallo!!!! sicherlich nicht den Text und Auswendiglernen zu lesen, aber .... Beispiele: D Wie kürzlich eingetaucht ich in Containern in STL angegeben, hier ist der Schnelltest-Code, den selbsterklärend ist, hoffe ich:

#include <iostream> 
#include <vector> 
#include <deque> 
#include <array> 
#include <list> 
#include <iterator> 
#include <cstdlib> 
#include <algorithm> 
#include "Timer.h" 

constexpr int SIZE = 1005000; 

using namespace std; 

void test(); 

int main(){ 
    cout<<"array allocates "<<static_cast<double>(SIZE)/(1024*1024)<<" MB\n"; 
    test(); 


    return 0; 
} 


void test(){ 
    int values[SIZE]; 
    int size = 0; 

    //init values to sort: 
    do{ 
     values[size++] = rand() % 100000; 
    }while(size < SIZE); 

    //feed array with values: 
    array<int, SIZE> container_1; 
    for(int i = 0; i < SIZE; i++) 
     container_1.at(i) = values[i]; 

    //feed vector with values 
    vector<int> container_2(begin(values), end(values)); 
    list<int> container_3(begin(values), end(values)); 
    deque<int> container_4(begin(values), end(values)); 

    //meassure sorting time for containers 
    { 
     Timer t1("sort array"); 
     sort(container_1.begin(), container_1.end()); 
    } 

    { 
     Timer t2("sort vector"); 
     sort(container_2.begin(), container_2.end()); 
    } 

    { 
     Timer t3("sort list"); 
     container_3.sort(); 
    } 

    { 
     Timer t4("sort deque"); 
     sort(container_4.begin(), container_4.end()); 
    } 

} 

Und der Code für timer:

#include <chrono> 
#include <string> 
#include <iostream> 

using namespace std; 

class Timer{ 

public: 
    Timer(string name = "unnamed") : mName(name){ mStart = chrono::system_clock::now();} 
    ~Timer(){cout<<"action "<<mName<<" took: "<< 
      chrono::duration_cast<chrono::milliseconds>(
        chrono::system_clock::now() - mStart).count()<<"ms"<<endl;} 
private: 
    chrono::system_clock::time_point mStart; 
    string mName; 
}; 

Hier ist das Ergebnis, wenn keine Optimierung verwendet wird (g ++ --std = C++ 11 file.cpp -o a.ou t):

Array ordnet 0,958443 MB
Aktion sort Array hat: 183ms
Aktion sort Vektor hat: 316ms
Aktion Sortierliste hat: 725ms
Aktion sort Deque nahm: 436ms

und Optimierung (g ++ -O3 --std = C++ 11 file.cpp -o a.out):

Array ordnet 0.958443 MB
Aktion sort Array nahm: 55ms
Aktion Art Vektor nahm: 57ms
Aktion Sortierliste nahm: 264ms
Aktion sort deque nahm: 67ms

Beachten Sie, dass obwohl Vektor- und Array ähnlich Bei der Sortierung für diesen Fall ist die Array-Größe begrenzt, da sie auf dem Stack initialisiert werden soll (standardmäßig keine eigenen Allokatoren usw.).

Es hängt also auch davon ab, ob Sie die Optimierung für den Compiler verwenden, wenn nicht erkennbaren Unterschied sehen.