Warum wurde „std::list::sort()' in Visual Studio 2015 auf eine Zusammenführungssortierung von oben nach unten umgestellt?

Warum der plötzliche Wechsel zur Top-Down-Strategie in std::list<>::sort()?

In Visual Studio 2015 (VS2015) hat Microsoft die Sortierstrategie von std::list<>::sort() von der traditionellen Bottom-Up-Merge-Sortierung auf einen Top-Down-Ansatz umgestellt. Durch diese Änderung entfällt die Verwendung eines internen Arrays von Listen und es werden Iteratoren übernommen, um sortierte Laufgrenzen innerhalb der ursprünglichen Liste zu verfolgen.

Gründe für die Änderung

Stephan T. Lavavej , der Entwickler des Top-Down-Ansatzes, verwies auf die Notwendigkeit, die Speicherzuweisung und den Aufbau nicht standardmäßiger Allokatoren zu vermeiden. VS2015 führte Allokatoren ein, die nicht mehr standardmäßig konstruierbar und zustandsbehaftet waren, was bei Verwendung des vorherigen Bottom-up-Ansatzes zu Problemen führte.

Implementierung des Top-Down-Ansatzes

Die Oberseite Der -down-Ansatz verwendet einen rekursiven Algorithmus, der die Liste rekursiv in Hälften teilt, bis Basisfälle erreicht werden, in denen die Listen leer sind oder ein einzelnes Element enthalten. Die Funktion _Sort unterteilt die Liste in drei Segmente: Linkslauf, Rechtslauf und den Enditerator. Die Zusammenführungslogik wird mithilfe von std::list::splice durchgeführt, um Knoten innerhalb der ursprünglichen Liste zu verschieben und dabei die Ausnahmesicherheit aufrechtzuerhalten.

Leistungsüberlegungen

Während der Top-Down-Methode Der Ansatz behebt Bedenken bei der Speicherzuordnung, bringt jedoch im Vergleich zur ursprünglichen Bottom-up-Merge-Sortierung einen Leistungseinbußen mit sich. Bei großen Listen mit verstreuten Knoten leidet der Top-Down-Ansatz unter einer erhöhten Anzahl von Cache-Fehlern, was zu langsameren Ausführungszeiten führt. In solchen Fällen kann es schneller sein, die Liste in ein Array oder einen Vektor zu verschieben, sie zu sortieren und aus dem sortierten Array oder Vektor eine neue Liste zu erstellen.

Das obige ist der detaillierte Inhalt vonWarum wurde „std::list::sort()' in Visual Studio 2015 auf eine Zusammenführungssortierung von oben nach unten umgestellt?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!