Wie wird sort für std :: deque implementiert?

Question

Nicht so weit habe ich gelernt, wie std::deque unter der Haube implementiert ist, und entdeckte, dass es so etwas wie ein Array von Zeigern zu N-Byte-Arrays, wo die Daten tatsächlich gespeichert ist. Jetzt habe ich ein paar Fragen zu Deques.

Ein Bild, das über seine Struktur meines aktuelles Wissen beschreibt:

Die Fragen sind:

1. Wenn ein push_front Betrieb durchgeführt wird, und es gibt keinen freien Platz in Datenblock 0, a neuer Datenblock wird auf dem Heap zugewiesen und ein Zeiger auf diesen frisch zugewiesenen Speicher wird in ein "Map" -Array wie in gewöhnliches Array eingefügt - in O (number_of_blocks) -Zeit, ja?

2. Wie sortiere ich dieses Biest? Kann mir nichts besseres vorstellen, als alle Daten in ein Array zu kopieren, zu sortieren und dann wieder zurück zu legen. Aber dieser Ansatz erfordert O (n) Hilfsspeicher ... Aber! std::sort bietet eine ähnliche Schnittstelle zum Sortieren sowohl std::vector als auch std::deque. Wie werden verschiedene Algorithmen für unterschiedliche Datenstrukturen implementiert? Verwenden einer Template-Spezialisierung? Wenn ja, warum kann std::list nicht mit std::sort sortiert werden? Oder vielleicht, std::sort kümmert sich nicht um interne Struktur dieser Container und verwendet nur Iteratoren und Methoden, die in std::vector und std::deque ähnlich sind (wie operator[], size(), etc)? Diese Idee klingt vernünftig und eine Antwort auf "warum kann std::sort nicht sortieren std::list?" wird offensichtlich.

3. Wie werden die Datenblöcke ausgewählt? Sie werden sagen "Es ist abhängig von der Implementierung", aber bitte erzählen Sie mehr über verschiedene Implementierungen und Motivation hinter Lösungen.

benötigen hier Präzisierungen. Danke.

Answer 1

Um Ihre erste Frage zu beantworten, ja, das ist so ziemlich wie es funktioniert. Man kann feststellen, dass dieser Ansatz zu einer mehrstufigen hierarchischen Struktur erweitert werden kann. Aber praktische Implementierungen halten sich normalerweise an eine zweistufige Struktur, genau wie in Ihrem Bild gezeigt.

Für Ihre zweite Frage, wenn Sie etwa std::sort nehmen, dann funktioniert std::sort funktioniert ohne Wissen über die Mechanik des eigentlichen Behälters. Funktioniert bei einer Reihe von Iteratoren mit wahlfreiem Zugriff. Da die Iteratoren std::deque Random-Access-Iteratoren sind, kann std::sort auf std::deque angewendet werden. Und man kann tatsächlich argumentieren, dass der zufällige Zugriff auf Elemente einer solchen Datenstruktur ziemlich effizient ist. Es ist nicht so effizient wie der Direktzugriff in einem Vektor, aber es ist immer noch ziemlich effizient, um im Kontext von std::sort Sinn zu machen.

Sie können std::sort mit std::list nicht verwenden, da die Iteratoren von std::list keine Direktzugriffsiteratoren sind. Wenn Sie möchten, können Sie Ihre eigene triviale (langsame) Version des Random-Access-Iterators für std::list implementieren. Sie können std::sort auf eine Reihe solcher Iteratoren anwenden und so std::list mit std::sort sortieren. Aber aus offensichtlichen Gründen wird es prohibitiv ineffizient sein.

Im Fall von std::deque sind Random Access Iteratoren mehr als ausreichend effizient.

Ich bin nicht bereit, die dritte Frage zu beantworten. Tatsächlich wäre ich nicht überrascht, wenn man herausfindet, dass diese Größen aufgrund einer Reihe von Experimenten empirisch ausgewählt werden. Und natürlich gibt es wahrscheinlich keine Lösung für alle Fälle.