Vector vs Deque operator[]

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.