Ich habe mir STL-Container angesehen und versucht herauszufinden, was sie wirklich sind (dh die verwendete Datenstruktur) und die deque hielt mich auf: Ich dachte zuerst, dass es sich um eine doppelt verknüpfte Liste handelt, die das Einfügen und Löschen von beiden Enden in konstanter Zeit ermöglichen würde, aber ich bin beunruhigt darüber das gemachte Versprechen durch den Betreiber [] in konstanter Zeit zu erledigen. In einer verketteten Liste sollte der beliebige Zugriff O(n) sein, richtig?
Und wenn es ein dynamisches Array ist, wie kann es Elemente hinzufügen in konstanter Zeit? Es sollte erwähnt werden, dass es zu einer Neuzuweisung kommen kann und dass O(1) Amortisationskosten sind, wie für einen Vektor.
Ich frage mich also, was diese Struktur ist, die willkürlichen Zugriff in konstanter Zeit ermöglicht und gleichzeitig nie an einen neuen, größeren Ort verlegt werden muss.
Eine deque ist etwas rekursiv definiert: intern verwaltet sie eine doppelendige Warteschlange von Brocken von fester Größe. Jeder Chunk ist ein Vektor, und die Warteschlange („Map“ in der Grafik unten) von Chunks selbst ist ebenfalls ein Vektor.

Es gibt eine großartige Analyse der Leistungsmerkmale und wie sie mit denen verglichen werden vector
bei CodeProject.
Die Implementierung der GCC-Standardbibliothek verwendet intern a T**
die Karte darzustellen. Jeder Datenblock ist a T*
die mit einer festen Größe zugewiesen ist __deque_buf_size
(was davon abhängt sizeof(T)
).
Aus der Übersicht können Sie denken deque
Als ein double-ended queue

Die Daten in deque
werden durch Chunks mit Vektoren fester Größe gespeichert, die sind
verwiesen durch a map
(Das ist auch ein Teil des Vektors, aber seine Größe kann sich ändern)

Der Hauptteilcode der deque iterator
ist wie folgt:
/*
buff_size is the length of the chunk
*/
template <class T, size_t buff_size>
struct __deque_iterator{
typedef __deque_iterator<T, buff_size> iterator;
typedef T** map_pointer;
// pointer to the chunk
T* cur;
T* first; // the begin of the chunk
T* last; // the end of the chunk
//because the pointer may skip to other chunk
//so this pointer to the map
map_pointer node; // pointer to the map
}
Der Hauptteilcode der deque
ist wie folgt:
/*
buff_size is the length of the chunk
*/
template<typename T, size_t buff_size = 0>
class deque{
public:
typedef T value_type;
typedef T& reference;
typedef T* pointer;
typedef __deque_iterator<T, buff_size> iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
typedef pointer* map_pointer;
// allocate memory for the chunk
typedef allocator<value_type> dataAllocator;
// allocate memory for map
typedef allocator<pointer> mapAllocator;
private:
//data members
iterator start;
iterator finish;
map_pointer map;
size_type map_size;
}
Unten gebe ich Ihnen den Kerncode von deque
hauptsächlich über drei Teile:
-
Iterator
-
Wie baut man ein deque
1. Iterator (__deque_iterator
)
Das Hauptproblem des Iterators ist, wenn ++, — Iterator zu einem anderen Chunk springen kann (wenn er auf den Rand des Chunks zeigt). Beispielsweise gibt es drei Datenblöcke: chunk 1
,chunk 2
,chunk 3
.
Die pointer1
Hinweise auf den Anfang von chunk 2
wenn Betreiber --pointer
es zeigt auf das Ende von chunk 1
um die pointer2
.

Im Folgenden werde ich die Hauptfunktion von angeben __deque_iterator
:
Springen Sie zunächst zu einem beliebigen Chunk:
void set_node(map_pointer new_node){
node = new_node;
first = *new_node;
last = first + chunk_size();
}
Notiere dass der chunk_size()
Funktion, die die Chunk-Größe berechnet, können Sie sich vorstellen, dass sie hier zur Vereinfachung 8 zurückgibt.
operator*
Holen Sie sich die Daten im Chunk
reference operator*()const{
return *cur;
}
operator++, --
// Präfixformen des Inkrements
self& operator++(){
++cur;
if (cur == last){ //if it reach the end of the chunk
set_node(node + 1);//skip to the next chunk
cur = first;
}
return *this;
}
// postfix forms of increment
self operator++(int){
self tmp = *this;
++*this;//invoke prefix ++
return tmp;
}
self& operator--(){
if(cur == first){ // if it pointer to the begin of the chunk
set_node(node - 1);//skip to the prev chunk
cur = last;
}
--cur;
return *this;
}
self operator--(int){
self tmp = *this;
--*this;
return tmp;
}
Iterator überspringt n Schritte / Direktzugriff
self& operator+=(difference_type n){ // n can be postive or negative
difference_type offset = n + (cur - first);
if(offset >=0 && offset < difference_type(buffer_size())){
// in the same chunk
cur += n;
}else{//not in the same chunk
difference_type node_offset;
if (offset > 0){
node_offset = offset / difference_type(chunk_size());
}else{
node_offset = -((-offset - 1) / difference_type(chunk_size())) - 1 ;
}
// skip to the new chunk
set_node(node + node_offset);
// set new cur
cur = first + (offset - node_offset * chunk_size());
}
return *this;
}
// skip n steps
self operator+(difference_type n)const{
self tmp = *this;
return tmp+= n; //reuse operator +=
}
self& operator-=(difference_type n){
return *this += -n; //reuse operator +=
}
self operator-(difference_type n)const{
self tmp = *this;
return tmp -= n; //reuse operator +=
}
// random access (iterator can skip n steps)
// invoke operator + ,operator *
reference operator[](difference_type n)const{
return *(*this + n);
}
2. Wie konstruiere ich a deque
gemeinsame Funktion von deque
iterator begin(){return start;}
iterator end(){return finish;}
reference front(){
//invoke __deque_iterator operator*
// return start's member *cur
return *start;
}
reference back(){
// cna't use *finish
iterator tmp = finish;
--tmp;
return *tmp; //return finish's *cur
}
reference operator[](size_type n){
//random access, use __deque_iterator operator[]
return start[n];
}
template<typename T, size_t buff_size>
deque<T, buff_size>::deque(size_t n, const value_type& value){
fill_initialize(n, value);
}
template<typename T, size_t buff_size>
void deque<T, buff_size>::fill_initialize(size_t n, const value_type& value){
// allocate memory for map and chunk
// initialize pointer
create_map_and_nodes(n);
// initialize value for the chunks
for (map_pointer cur = start.node; cur < finish.node; ++cur) {
initialized_fill_n(*cur, chunk_size(), value);
}
// the end chunk may have space node, which don't need have initialize value
initialized_fill_n(finish.first, finish.cur - finish.first, value);
}
template<typename T, size_t buff_size>
void deque<T, buff_size>::create_map_and_nodes(size_t num_elements){
// the needed map node = (elements nums / chunk length) + 1
size_type num_nodes = num_elements / chunk_size() + 1;
// map node num。min num is 8 ,max num is "needed size + 2"
map_size = std::max(8, num_nodes + 2);
// allocate map array
map = mapAllocator::allocate(map_size);
// tmp_start,tmp_finish poniters to the center range of map
map_pointer tmp_start = map + (map_size - num_nodes) / 2;
map_pointer tmp_finish = tmp_start + num_nodes - 1;
// allocate memory for the chunk pointered by map node
for (map_pointer cur = tmp_start; cur <= tmp_finish; ++cur) {
*cur = dataAllocator::allocate(chunk_size());
}
// set start and end iterator
start.set_node(tmp_start);
start.cur = start.first;
finish.set_node(tmp_finish);
finish.cur = finish.first + num_elements % chunk_size();
}
Angenommen i_deque
hat 20 int-Elemente 0~19
dessen Chunk-Größe 8 ist, und push_back nun 3 Elemente (0, 1, 2) an i_deque
:
i_deque.push_back(0);
i_deque.push_back(1);
i_deque.push_back(2);
Es ist interne Struktur wie unten:

Dann push_back erneut, es wird aufgerufen, einen neuen Chunk zuzuweisen:
push_back(3)

Wenn wir push_front
es wird ein neuer Chunk vor dem vorherigen zugewiesen start

Notieren Sie wann push_back
Element in deque, wenn alle Maps und Chunks gefüllt sind, wird es eine neue Map zuweisen und Chunks anpassen. Aber der obige Code könnte ausreichen, um Sie zu verstehen deque
.
Stellen Sie es sich als Vektor von Vektoren vor. Nur sind sie nicht Standard std::vector
S.
Der äußere Vektor enthält Zeiger auf die inneren Vektoren. Wenn seine Kapazität durch Neuzuweisung geändert wird, anstatt den gesamten leeren Speicherplatz bis zum Ende zuzuweisen std::vector
tut, wird der leere Raum am Anfang und am Ende des Vektors in gleiche Teile geteilt. Dies erlaubt push_front
und push_back
auf diesem Vektor, um beide in amortisierter Zeit O(1) aufzutreten.
Das Verhalten des inneren Vektors muss sich ändern, je nachdem, ob es vorne oder hinten ist deque
. Auf der Rückseite kann es sich wie ein Standard verhalten std::vector
wo es am Ende wächst, und push_back
tritt in O(1)-Zeit auf. An der Front muss es das Gegenteil tun, am Anfang mit jedem wachsen push_front
. In der Praxis wird dies leicht erreicht, indem dem vorderen Element ein Zeiger und die Wachstumsrichtung zusammen mit der Größe hinzugefügt werden. Mit dieser einfachen Modifikation push_front
kann auch O(1)-Zeit sein.
Der Zugriff auf ein beliebiges Element erfordert das Versetzen und Dividieren auf den richtigen äußeren Vektorindex, der in O (1) auftritt, und das Indizieren in den inneren Vektor, der ebenfalls O (1) ist. Dies setzt voraus, dass die inneren Vektoren alle eine feste Größe haben, mit Ausnahme derjenigen am Anfang oder am Ende von deque
.
deque = doppelseitige Warteschlange
Ein Behälter, der in beide Richtungen wachsen kann.
Deque ist typisch umgesetzt als vector
von vectors
(Eine Liste von Vektoren kann keinen konstanten zufälligen Zugriff geben). Während die Größe der sekundären Vektoren implementierungsabhängig ist, besteht ein üblicher Algorithmus darin, eine konstante Größe in Bytes zu verwenden.
Ich habe “Datenstrukturen und Algorithmen in C++” von Adam Drozdek gelesen und fand das nützlich. HTH.
Ein sehr interessanter Aspekt von STL deque ist seine Implementierung. Eine STL-Deque wird nicht als verknüpfte Liste implementiert, sondern als ein Array von Zeigern auf Blöcke oder Arrays von Daten. Die Anzahl der Blöcke ändert sich dynamisch je nach Speicherbedarf, und die Größe des Arrays von Zeigern ändert sich entsprechend.
Sie können in der Mitte das Array von Zeigern auf die Daten (Chunks auf der rechten Seite) sehen, und Sie können auch feststellen, dass sich das Array in der Mitte dynamisch ändert.
Ein Bild sagt mehr als tausend Worte.

Während der Standard keine bestimmte Implementierung vorschreibt (nur wahlfreien Zugriff zu konstanter Zeit), wird eine Deque normalerweise als Sammlung zusammenhängender Speicher-“Seiten” implementiert. Neue Seiten werden nach Bedarf zugewiesen, aber Sie haben immer noch wahlfreien Zugriff. nicht wie std::vector
wird Ihnen nicht versprochen, dass Daten zusammenhängend gespeichert werden, aber wie bei Vektoren erfordern Einfügungen in der Mitte viele Verschiebungen.
deque
könnte als Ringpuffer mit einem Array fester Größe implementiert werden:
- Verwenden Sie einen Ringpuffer, damit wir an beiden Enden wachsen/schrumpfen können, indem wir ein Array fester Größe mit O(1)-Komplexität hinzufügen/entfernen
- Verwenden Sie ein Array mit fester Größe, damit der Index einfach berechnet werden kann. Daher greifen Sie über den Index mit zwei Zeigerdereferenzen zu – auch O (1).
Mögliches Duplikat des STL-Deque-Zugriffs nach Index ist O (1)?
– fredoverflow
9. Juni 2011 um 12:02 Uhr
@Graham „dequeue“ ist ein anderer gebräuchlicher Name für „deque“. Ich habe die Bearbeitung trotzdem genehmigt, da „deque“ normalerweise der kanonische Name ist.
– Konrad Rudolf
9. Juni 2011 um 12:09 Uhr
@ Konrad Danke. Die Frage bezog sich speziell auf die C++-STL-Deque, die die kürzere Schreibweise verwendet.
– Graham Borland
9. Juni 2011 um 12:11 Uhr
deque
steht für doppelte Warteschlangeobwohl die strenge Anforderung des O(1)-Zugriffs auf mittlere Elemente offensichtlich spezifisch für C++ ist– Matthias M.
9. Juni 2011 um 12:11 Uhr