Jaka jest różnica między kontenerami deque i list STL?

Let me list down the differences:

• Deque zarządza swoimi elementami za pomocą tablica dynamiczna , dostarcza losowo access , i ma prawie taki sam interfejs jako wektor.
• List zarządza swoimi elementami jako podwójnie powiązana lista i nie Udostępnij dostęp losowy .

• deque zapewnia szybkie wstawianie i usuwanie w zarówno koniec, jak i początek. Wstawianie i usuwanie elementów w na środek jest stosunkowo wolny, ponieważ wszystkie elementy do jednego z obu końcówki można przesuwać, aby zrobić miejsce lub do wypełnij lukę.
• na liście wstawianie i usuwanie elementów jest szybkie na każdej pozycji, łącznie z obydwoma końcami.

• Deque: dowolne wstawianie lub usuwanie elementów inne niż na początku lub końcu unieważnia wszystkie wskaźniki, referencje, i Iteratory, które odnoszą się do elementów deque.
• List : Wstawianie i usuwanie elementów czy nie unieważnia wskaźników, referencji, i Iteratory do innych elementów.

Złożoność

             Insert/erase at the beginning       in middle        at the end

Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant

std::list jest w zasadzie podwójnie połączoną listą.

std::deque, z drugiej strony, jest zaimplementowany bardziej jak std::vector. Ma stały czas dostępu według indeksu, a także wstawianie i usuwanie na początku i końcu, co zapewnia znacznie inną charakterystykę wydajności niż lista.

Kolejną ważną gwarancją jest sposób, w jaki każdy kontener przechowuje swoje dane w pamięci:

• wektor jest pojedynczym sąsiadującym blokiem pamięci.
Deque to zbiór połączonych bloków pamięci, w których w każdym bloku pamięci przechowywany jest więcej niż jeden element.
• lista jest zbiorem elementów rozproszonych w pamięci, tzn.: tylko jeden element jest przechowywany w pamięci "bloku".

Zauważ, że deque został zaprojektowany tak, aby próbować zrównoważyć zalety zarówno wektora, jak i lista bez ich wad. Jest to szczególnie interesujący kontener w pamięci ograniczonych platform, na przykład mikrokontrolerów.

Strategia przechowywania pamięci jest często pomijana, jednak często jest to jeden z najważniejszych powodów, aby wybrać najbardziej odpowiedni kontener dla danej aplikacji.

Nie. Deque obsługuje tylko o(1) wstawianie i usuwanie z przodu iz tyłu. Może być na przykład zaimplementowany w wektorze z zawijaniem. Ponieważ gwarantuje również losowy dostęp O(1), możesz być pewien, że nie używa (tylko) podwójnie połączonej listy.

Między deque a list

• Dla deque:

  Przedmioty przechowywane obok siebie;

  Zoptymalizowany do dodawania danych z dwóch stron (przód, tył);

  Elementy indeksowane liczbami (liczbami całkowitymi).

  Może być przeglądany przez Iteratory, a nawet przez indeks elementu.

  Czas dostępu do danych jest szybszy.

• Dla list

  Elementy przechowywane "losowo" w pamięci;

  Można przeglądać tylko przez Iteratory;

  Zoptymalizowany do wstawiania i usuwania w środku.

  Czas dostępu do danych jest wolniejszy, powolny w iteracji, ze względu na bardzo słabą lokalizację przestrzenną.

  Bardzo dobrze radzi sobie z dużymi elementami

Możesz również sprawdzić następujący Link , który porównuje wydajność pomiędzy dwoma kontenerami STL (z std::vector)

Różnice w wydajności zostały dobrze wyjaśnione przez innych. Chciałem tylko dodać, że podobne lub nawet identyczne interfejsy są powszechne w programowaniu obiektowym-część ogólnej metodologii pisania oprogramowania obiektowego. Nie należy w żaden sposób zakładać, że dwie klasy działają w ten sam sposób, po prostu dlatego, że implementują ten sam interfejs, podobnie jak koń działa jak pies, ponieważ obie implementują attack () i make_noise ().

Oto kod proof-of-concept użycia listy, mapy, która daje o (1) lookup i o(1) dokładne utrzymanie LRU. Potrzebuje (nie-wymazanych) iteratorów, aby przetrwać operacje kasowania. Plan użycia w o(1) arbitralnie dużej pamięci podręcznej zarządzanej przez oprogramowanie dla wskaźników CPU w pamięci GPU. Ukłon w stronę Linuksa o(1) scheduler (LRU run queue per processor). Unordered_map ma stały dostęp czasowy poprzez tabelę hash.

#include <iostream> 
#include <list> 
#include <unordered_map>  
using namespace std; 

struct MapEntry {
  list<uint64_t>::iterator LRU_entry;
  uint64_t CpuPtr;
};
typedef unordered_map<uint64_t,MapEntry> Table;
typedef list<uint64_t> FIFO;
FIFO  LRU;        // LRU list at a given priority 
Table DeviceBuffer; // Table of device buffers

void Print(void){
  for (FIFO::iterator l = LRU.begin(); l != LRU.end(); l++) {
    std::cout<< "LRU    entry "<< *l << "   :    " ;
    std::cout<< "Buffer entry "<< DeviceBuffer[*l].CpuPtr <<endl;
  }  
}
int main() 
{ 

  LRU.push_back(0);
  LRU.push_back(1);
  LRU.push_back(2);
  LRU.push_back(3);
  LRU.push_back(4);

  for (FIFO::iterator i = LRU.begin(); i != LRU.end(); i++) {
    MapEntry ME = { i, *i}; 
    DeviceBuffer[*i] = ME;
  }

  std::cout<< "************ Initial set of CpuPtrs" <<endl;
  Print();

  {
    // Suppose evict an entry - find it via "key - memory address uin64_t" and remove from 
    // cache "tag" table AND LRU list with O(1) operations
    uint64_t key=2;
    LRU.erase(DeviceBuffer[2].LRU_entry);
    DeviceBuffer.erase(2);
  }

  std::cout<< "************ Remove item 2 " <<endl;
  Print();

  { 
    // Insert a new allocation in both tag table, and LRU ordering wiith O(1) operations
    uint64_t key=9;
    LRU.push_front(key); 
    MapEntry ME = { LRU.begin(), key };
    DeviceBuffer[key]=ME;
  }

  std::cout<< "************ Add item 9  " <<endl;
  Print();

  std::cout << "Victim "<<LRU.back()<<endl;
} 

Zrobiłem ilustracje dla uczniów z mojej klasy C++. Jest to oparte (luźno) na (moim zrozumieniu) implementacji w implementacji GCC STL ( https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_deque.h i https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_list.h )

Kolejka dwukołowa

Elementy kolekcji są przechowywane w blokach pamięci. Na liczba elementów w bloku zależy od wielkości elementu: im większe elementy, tym mniej w bloku. Podstawową nadzieją jest to, że jeśli bloki mają podobną wielkość bez względu na rodzaj elementów, powinno to pomóc alokatorowi przez większość czasu.

Masz tablicę (zwaną mapą w implementacji GCC) z listą bloków pamięci. Wszystkie bloki pamięci są pełne, z wyjątkiem pierwszego, który może mieć miejsce na początku i ostatniego, który może mieć miejsce na końcu. Mapa sam jest wypełniony od środka na zewnątrz. W ten sposób, w przeciwieństwie do std::vector, Wstawianie na obu końcach może być wykonane w stałym czasie. Podobnie jak std:::vector, dostęp losowy jest możliwy w stałym czasie, ale wymaga dwóch indirections zamiast jednego. Podobnie jak std::vector i w przeciwieństwie do std::list, usuwanie lub wstawianie elementów w środku jest kosztowne, ponieważ trzeba zreorganizować dużą część struktury danych.

Lista Dwuliterowa

Lista Podwójnie powiązana być może są bardziej zwyczajne. Każdy element jest przechowywany we własnym bloku pamięci, przydzielonym niezależnie od pozostałych elementów. W każdym bloku masz wartość elementu i dwa wskaźniki: jeden do poprzedniego elementu, Jeden do następnego elementu. Bardzo ułatwia wstawianie elementu w dowolnym miejscu listy, a nawet przenoszenie podchainu elementów z jednej listy do drugiej( operacja o nazwie splicing ): wystarczy zaktualizować Wskaźniki na początku i końcu wstawiania punkt. Minusem jest to, że aby znaleźć jeden element po jego indeksie, musisz przejść przez łańcuch wskaźników, więc losowy dostęp ma koszt liniowy w liczbie elementów na liście.