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.