5

Deque gives constant complexity for accessing any element( cpp reference ). In Vector, it's always constant complexity(the address of the first element in vector + no of elements * size of each element) but how does it work for Deque? Deque elements are not contiguous in memory, so how does it enable O(1) time complexity to access any element? When I ran the following program, in the case of Vector, it gives correct output, but for Deque, it gives some arbitrary numbers (agreed to not give the correct result because elements are not contiguous).

vector<int> v1;
deque<int> d1;
for(int i =0; i < 1000000;++i)
    v1.push_back(i);
for( int j =0; j < 1000000;++j)
    d1.push_back(j);
cout << *(&v1[0] +90000) << endl; // output 90000
cout << *(&d1[0] +90000)<<endl;   // Output is not 90000
Neel Sandell
  • 429
  • 5
  • 12
Alok
  • 1,997
  • 2
  • 18
  • 30

3 Answers3

9

A deque is typically implemented as a two-layer structure, the top level is an array of pointers to fixed-sized chunks. Using knowledge of that size it is constant complexity to determine which chunk holds the item of interest and constant complexity to determine which item in the chunk is being requested.

Just because it is constant does not indicate that it is always a simple direct memory access, only that all accesses for that particular operation will require the same steps.

SoronelHaetir
  • 14,104
  • 1
  • 12
  • 23
  • 1
    "Just because it is constant does not indicate that it is always a simple direct memory access, only that all accesses for that particular operation will require the same steps" - So wrong.. the same step could be "iterate on all the elements" for example, which makes it O(n).. – Dr.Haimovitz Sep 09 '18 at 04:21
  • 1
    @Dr.Haimovitz It depends on what you count as "the same steps". – eesiraed Sep 09 '18 at 04:32
  • @Fei xiang unless "step" is limited to O(1) i don't see any reason that step could not be any sequence of operations of any type.. – Dr.Haimovitz Sep 09 '18 at 04:38
  • 1
    @Dr.Haimovitz The word "step" as used here likely does mean a simple operation that takes `O(1)`. – eesiraed Sep 09 '18 at 04:39
  • 1
    "Using knowledge of that size it is constant complexity to determine which chunk holds the item of interest" - can you explain how, if the chunks are not part of a continues memory?? – Dr.Haimovitz Sep 09 '18 at 04:40
  • 1
    @Fei Xiang if thats true and what is meant is that step is O(1) then each operation does not have to take the "same steps"... – Dr.Haimovitz Sep 09 '18 at 04:43
  • 1
    @Dr.Haimovitz In regards to how you would determine which chunk the element is in, you simply do `index / chunkSize`. The answerer is just using a slightly simplified explanation here, no need to be all strict about it. – eesiraed Sep 09 '18 at 04:46
  • 1
    @Fei Xiang and what if the chunk is full and you need to enqueue (in O(1))? You create a new chunk before the "old" first chunk, then how you random access with index/chunkSize? – Dr.Haimovitz Sep 09 '18 at 05:08
  • 1
    @Dr.Haimovitz - the point of both CoronhelHaetir's answer and Fei Ziang's comments are that doing a fixed number of O(1) operations also gives O(1) complexity. That only changes if the number of operations being performed is variable. Multiplying two constants gives a constant. – Peter Sep 09 '18 at 05:18
  • 1
    @Peter this point is clear, i think that for op as well though it does not answer the question.. – Dr.Haimovitz Sep 09 '18 at 05:21
  • 2
    @Dr.Haimovitz It doesn't matter where in memory the chunks are related to each other. Finding the pointer to any chunk is constant time, and indexing that pointer to get the value is constant time. It is the same effort to access any element of a deque, the value of n doesn't matter. If it always took 100 operations and 10 seconds to find any value in an imaginary container that access would still be O(1). It is a measure of complexity, not time. – Retired Ninja Sep 09 '18 at 05:39
  • @Retired Ninja "Finding the pointer to any chunk is constant time" why?? This is the question... see my other comments.. – Dr.Haimovitz Sep 09 '18 at 06:47
  • What happens if the first array or first chunk is full and there is an enqueue operation, a new array must be allocate (it's O(1)) because the array is of fixed size but then how is the bookkeeping updates so the next random access for index 0 for instance will pick the right element, before the new array index 0 was pointing to another array and if well change this mapping will also have to change every other index mapping which is O(n) means the insertion of element is o(1) only in *avarage because every time one of the arrays is full a new mapping is required (n) – Dr.Haimovitz Sep 09 '18 at 06:55
  • https://stackoverflow.com/questions/2297164/stl-deque-accessing-by-index-is-o1 – Retired Ninja Sep 09 '18 at 06:59
  • The container contains N pointers to chunks of size M. index / M tells you which pointer points to the chunk, and index % M tells you the offset in the chunk the pointer points to. The chunks can be anywhere in memory and it doesn't matter because of the double dereference. – Retired Ninja Sep 09 '18 at 07:03
2

Don't let the "1" confuse you. O(1) is the computer-science way of saying that the number of calculation steps necessary to arrive at the desired element does not depend on the size of the container. Whether you have a std::deque<T> with 10 elements or a std::deque<T> with 10000000 elements doesn't matter - getting the desired element at index i always involves two pointer dereferences.

See https://en.cppreference.com/w/cpp/container/deque:

typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences

Compare this to a std::list<T>, where the number of calculation steps necessary to get the element at index i does depend on the size of the container.

Christian Hackl
  • 27,051
  • 3
  • 32
  • 62
  • What happens if the first array or first chunk is full and there is an enqueue operation, a new array must be allocate (it's O(1)) because the array is of fixed size but then how is the bookkeeping updates so the next random access for index 0 for instance will pick the right element, before the new array index 0 was pointing to another array and if well change this mapping will also have to change every other index mapping which is O(n) means the insertion of element is o(1) only in *avarage because every time one of the arrays is full a new mapping is required (n) – Dr.Haimovitz Sep 09 '18 at 06:54
  • *"What happens if the first array or first chunk is full and there is an enqueue operation*" - This question is about random access, not about modifying the container. Please don't try to make this appear more complicated than it really is. – Christian Hackl Sep 09 '18 at 07:07
1

Random access to deque elements involves two pointer de-referencing, and is constant across any elements. However it won't be as efficient as vector.

GSAT
  • 56
  • 2