What's the difference between deque and list STL containers?

user_113124 0
Viewed 88520

What is the difference between the two? I mean the methods are all the same. So, for a user, they work identically.

Is that correct??

deque list stl c++
9 Answers

I've made illustrations for the students in my C++ class. This is based (loosely) on (my understanding of) the implementation in the GCC STL implementation ( https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_deque.h and https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_list.h)

Double-ended queue

Illustration of std::deque

Elements in the collection are stored in memory blocks. The number of elements per block depends on the size of the element: the bigger the elements, the fewer per block. The underlying hope is that if the blocks are of a similar size no matter the type of the elements, that should help the allocator most of the time.

You have an array (called a map in the GCC implementation) listing the memory blocks. All memory blocks are full except the first one which may have room at the beginning and the last which may have room at the end. The map itself is filled from the center outwards. This is how, contrarily to a std::vector, insertion at both ends can be done in constant time. Similarly to a std:::vector, random access is possible in constant time, but requires two indirections instead of one. Similarly to std::vector and contrarily to std::list, removing or inserting elements in the middle is costly because you have to reorganize a large part of the datastructure.

Doubly-linked list

Illustration of a std::list

Doubly-linked list are perhaps more usual. Every element is stored in its own memory block, allocated independently from the other elements. In each block, you have the element's value and two pointers: one to the previous element, one to the next element. It makes it very easy to insert element at any position in the list, or even to move a subchain of elements from one list to another (an operation called splicing): you just have to update the pointers at the beginning and end of the insertion point. The downside is that to find one element by its index, you have to walk the chain of pointers, so random access has a linear cost in the numbers of elements in the list.

user_23221720

Among eminent differences between deque and list

  • For deque :

    Items stored side by side;

    Optimized for adding datas from two sides (front, back);

    Elements indexed by numbers (integers).

    Can be browsed by iterators and even by element's index.

    Time access to data is faster.

  • For list

    Items stored "randomly" in the memory;

    Can be browsed only by iterators;

    Optimized for insertion and removal in the middle.

    Time access to data is slower, slow to iterate, due to its very poor spatial locality.

    Handles very well large elements

You can check also the following Link, which compares the performance between the two STL containers (with std::vector)

Hope i shared some useful informations.

user_96941340

Here's a proof-of-concept code use of list, unorded map that gives O(1) lookup and O(1) exact LRU maintenance. Needs the (non-erased) iterators to survive erase operations. Plan to use in a O(1) arbitrarily large software managed cache for CPU pointers on GPU memory. Nods to the Linux O(1) scheduler (LRU <-> run queue per processor). The unordered_map has constant time access via hash table.

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