7

Deques are to be chosen over vectors if we are constantly adding in front and in the back of the container. But what about offseting? Do vector's and deque's operator[] work the same, or not? If not, which one is faster?

JFMR
  • 23,265
  • 4
  • 52
  • 76
user2653125
  • 185
  • 2
  • 9

3 Answers3

12

A std::vector<T> is a flat array of T elements. std::deque<T> is an array of equal sized arrays of T. The complexity of index access is O(1) in both cases but std::deque<T> needs to do a lot more work to determine the element to access and there is also an indication. Like, iterators on std::deque<T> need to do multiple checks (although algorithms could optimize this out mostly making the overhead rather small by recognizing the segmented structure. Thus, if you need to use the subscript operator often std::deque<T> may be a bad choice and the cost of moving elements in a std::vector<T> when inserting/deleting at the front may be offset.

Just to explain, roughly what std::deque<T> needs to do in case of using a subscript operator: it can be thought of doing these operations:

T& deque<T>::operator[](size_t n) {
    n += this->first_element;
    size_t subarray = n / size_of_subarrays;
    size_t index    = n % size_of_subarrays;
    return this->subarrays[subarray][index];
}

The division/modulus operators are unlikely to be too expensive as size_of_subarray is almost certainly chosen to be a power of 2, i.e., they basically amount to bit operations.

Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380
  • 1
    if i am looping through consecutive elements of the container, any suggestion on how to increase the speed of looping using deque? would using iterators increase the speed rather than offsetting? if so could you help me with an example on how to implement iterators on deques, or is it just the same as in vectors? – user2653125 Sep 15 '13 at 12:27
  • @user2653125: The proper way to improve iterating over a deque is to take advantage of its segmented structure: instead of iterating over the deque, iterate over each of its subarrays individually. Sadly, deque doesn't expose this segmentation structure and C++ doesn't define a segmented iterator concept, yet. The main problem with iterating over a deque is that incrementing an iterator requires a check if the iterator has reached the end of a segment. Whether the unlikely branch or the computation is less expensive, is hard to predict, you'd need to measure. – Dietmar Kühl Sep 15 '13 at 12:35
  • thanks. if because of my algorithm i simply want to add in front and fully iterate through a container in one direction, is it better if i create my own version of a linked list rather than vector or deque? Would this significantly make a change in performance of my algorithm? Or is there any other better container for this purpose? – user2653125 Sep 15 '13 at 12:40
  • @user2653125: I would expect iterating over a `std::deque` to be faster than iterating over a `std::list` but that would need to be measured. Iterating over a deque naively will be slower than iterating over a vector. The ideal data structure would be a deque exposing its internal segmentation structure, e.g., by using segmented iterators, and taking this segmentation into account in the algorithms iterating over the deque: it would have nearly efficient access during iteration and good behavior for insertion at the front and end. I would just use deque and see if it is too slow. – Dietmar Kühl Sep 15 '13 at 12:46
3

for deque

subscripting approaches the efficiency of the vector

Bjarne Stroustrup "C++ programming language" 17.2.3

It is not exactly the same because of one additional indirection needed to access element. This in turn incurs an additional memory hit due to cache miss in many cases. So it may well be orders of magnitude (actually, roughly a factor 1000) slower for random access. However, this will amortise for many consecutive accesses so it usually won’t be as bad in practice.

4pie0
  • 29,204
  • 9
  • 82
  • 118
  • … which in turn incurs an additional memory hit due to cache miss in many cases. So it may well be orders of magnitude (actually, roughly a factor 1000) slower for random access. However, this will amortise for many consecutive accesses so it usually won’t be as bad in practice. – Konrad Rudolph Sep 15 '13 at 12:02
  • 1
    Yes – accessing main memory rather than the L1 cache is roughly a factor 1000 slower. That’s why we have caches in the first place. But like I said, once you access a chunk of the deque it will usually be loaded into cache entirely, so if you subsequently access close-by elements there’s a high chance of a cache hit, and thus much faster access. – Konrad Rudolph Sep 15 '13 at 12:06
  • thank you very much, this kind of information is what we really need to learn what and when and how to use. This is obvious somehow but also it is not so straightforward in many cases to link different aspects together – 4pie0 Sep 15 '13 at 12:06
1

std::deque is something like a list of std::vectors, so if you really need [] operator, std::vector would be faster to take data, but difference is not big, so you should better look how often you push data in back and in front to determine if you need std::vector or std::deque.

One more thing, if you use for loop which takes some index of container you should better use iterator as a result speed difference of taking data from std::vector and std::deque would be not noticeable.

ST3
  • 8,826
  • 3
  • 68
  • 92
  • It’s a *vector* of vectors, not a list of vectors. Crucial difference. – Konrad Rudolph Sep 15 '13 at 12:08
  • @KonradRudolph not cure about implementation. But if it is `vector` so difference between `vector` and `deque` is even less noticeable. – ST3 Sep 15 '13 at 12:10