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

Question 1

Jaka jest różnica między nimi? Chodzi mi o to, że metody są takie same. Więc dla użytkownika działają identycznie.

Czy to jest poprawne??

Question 2

Z (przestarzałego, ale nadal bardzo przydatnego) podsumowania SGI STL deque :

Deque jest bardzo podobny do wektora: podobnie jak wektor, jest to sekwencja, która obsługuje losowy dostęp do elementów, wstawianie i usuwanie elementów w stałym czasie na końcu sekwencji oraz wstawianie i usuwanie elementów w środku w czasie liniowym.

Głównym sposobem, w jaki deque różni się od wektora, jest to, że deque obsługuje również wstawianie i usuwanie elementów w stałym czasie na początku sekwencji. Ponadto deque nie ma żadnych funkcji składowych analogicznych do funkcji capacity () i booking () wektora i nie zapewnia żadnych gwarancji dotyczących ważności iteratora, które są skojarzone z tymi funkcjami składowymi.

Oto podsumowanie listz tej samej witryny:

Lista to lista podwójnie połączona. Oznacza to, że jest to Sekwencja, która obsługuje zarówno przechodzenie do przodu, jak i do tyłu oraz (amortyzowane) stałe wstawianie i usuwanie elementów na początku lub na końcu lub w środku. Listy mają ważną właściwość polegającą na tym, że wstawianie i łączenie nie unieważnia iteratorów do elementów listy, a nawet usunięcie unieważnia tylko iteratory wskazujące na elementy, które są usuwane. Kolejność iteratorów może ulec zmianie (to znaczy list :: iterator może mieć innego poprzednika lub następcę po operacji na liście niż poprzednio), ale same iteratory nie zostaną unieważnione ani nie będą wskazywać na inne elementy, chyba że to unieważnienie lub mutacja jest wyraźna.

Podsumowując, kontenery mogą mieć wspólne procedury, ale gwarancje czasowe dla tych procedur różnią się w zależności od kontenera . Jest to bardzo ważne, gdy zastanawiasz się, którego z tych kontenerów użyć do wykonania zadania: uwzględnienie tego, jak kontener będzie najczęściej używany (np. Bardziej do wyszukiwania niż do wstawiania / usuwania) znacznie ułatwia kierowanie do odpowiedniego kontenera .

Question 3

Wypiszę różnice:

Deque zarządza swoimi elementami za pomocą tablicy dynamicznej , zapewnia swobodny dostęp i ma prawie taki sam interfejs jak wektor.
Lista zarządza swoimi elementami jako listą podwójnie połączoną i nie zapewnia swobodnego dostępu .

Deque zapewnia szybkie wstawianie i usuwanie zarówno na końcu, jak i na początku. Wstawianie i usuwanie elementów w środku jest stosunkowo powolne, ponieważ wszystkie elementy do obu końców można przesunąć, aby zrobić miejsce lub wypełnić lukę.
Na liście , wstawianie i usuwanie elementów jest szybkie w każdej pozycji, w tym na obu końcach.

Deque : Każde wstawienie lub usunięcie elementów innych niż na początku lub na końcu unieważnia wszystkie wskaźniki, odniesienia i iteratory, które odnoszą się do elementów deque.
Lista : Wstawianie i usuwanie elementów nie unieważnia wskaźników, odniesień i iteratorów 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

Question 4

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

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

Question 5

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

Wektor to pojedynczy ciągły blok pamięci.
Deque to zestaw połączonych bloków pamięci, w którym więcej niż jeden element jest przechowywany w każdym bloku pamięci.
Lista jest zbiorem elementów rozproszonych w pamięci, tj .: tylko jeden element jest przechowywany w "bloku" pamięci.

Zauważ, że deque został zaprojektowany, aby spróbować zrównoważyć zalety zarówno wektora, jak i listy, bez ich odpowiednich wad. Jest to szczególnie interesujący pojemnik w platformach o ograniczonej pamięci, na przykład mikrokontrolerach.

Strategia przechowywania pamięci jest często pomijana, jednak często jest to jeden z najważniejszych powodów, dla których należy wybrać najbardziej odpowiedni kontener dla określonej aplikacji.

Question 6

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

Question 7

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 zorientowanego obiektowo. NIE POWINIENEŚ w ŻADNY sposób zakładać, że dwie klasy działają w ten sam sposób po prostu dlatego, że implementują ten sam interfejs, tak samo jak nie powinieneś zakładać, że koń działa jak pies, ponieważ obie implementują attack () i make_noise ().

Question 8

Oto kod sprawdzający koncepcję użycia listy, nieuporządkowanej mapy, która zapewnia wyszukiwanie O (1) i dokładne utrzymanie LRU O (1). Potrzebuje (nieusuniętych) iteratorów, aby przetrwać operacje wymazywania. Zaplanuj użycie w O (1) dowolnie dużej pamięci podręcznej zarządzanej programowo dla wskaźników procesora w pamięci GPU. Wskazuje na program planujący Linux O (1) (kolejka uruchomień LRU <-> na procesor). Unordered_map ma stały dostęp do czasu poprzez tablicę skrótów.

#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;
}

Question 9

Wśród znaczących różnic między dequeilist

Dla deque:

Przedmioty przechowywane obok siebie;

Zoptymalizowany pod kątem dodawania danych z dwóch stron (przód, tył);

Elementy indeksowane liczbami (liczbami całkowitymi).

Można przeglądać za pomocą iteratorów, a nawet według indeksu elementu.

Czasowy dostęp do danych jest szybszy.
Dla list

Pozycje przechowywane „losowo” w pamięci;

Można przeglądać tylko przez iteratory;

Zoptymalizowany do wkładania i wyjmowania w środku.

Dostęp czasowy do danych jest wolniejszy, iteruje powoli ze względu na bardzo słabą lokalność przestrzenną.

Bardzo dobrze radzi sobie z dużymi elementami

Możesz również sprawdzić poniższy link , który porównuje wydajność między dwoma kontenerami STL (ze std :: vector)

Mam nadzieję, że podzieliłem się kilkoma przydatnymi informacjami.