c++ - 向量与双端运算符 []

Question

如果我们不断地在容器的前后添加，则应选择双端队列而不是向量。但是抵消呢？vector's 和deque' 的工作方式相同吗operator[]？如果不是，哪个更快？

Answer 1

Astd::vector<T>是T元素的平面数组。std::deque<T>是一个大小相等的数组的数组T。在这两种情况下，索引访问的复杂度都是 O(1)，但std::deque<T>需要做更多的工作来确定要访问的元素，并且还有一个指示。就像，迭代器std::deque<T>需要进行多次检查（尽管算法可以通过识别分段结构来优化这一点，从而使开销相当小。因此，如果您需要使用下标运算符通常std::deque<T>可能是一个糟糕的选择，并且移动元素的成本在std::vector<T>前面插入/删除时可能会发生偏移。

只是说明一下，大致std::deque<T>在使用下标运算符的情况下需要做什么：可以考虑做这些操作：

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];
}

除法/模数运算符不太可能太昂贵，因为size_of_subarray几乎可以肯定选择为 2 的幂，即它们基本上相当于位运算。

Answer 2

双端队列

下标接近向量的效率

Bjarne Stroustrup 《C++ 编程语言》17.2.3

它不完全相同，因为访问元素需要一个额外的间接。在许多情况下，这又会由于缓存未命中而导致额外的内存命中。因此，随机访问的速度可能会慢几个数量级（实际上，大约是 1000 倍）。但是，这将为许多连续访问摊销，因此在实践中通常不会那么糟糕。

Answer 3

std::deque类似于 的列表std::vectors，因此如果您确实需要[]运算符，std::vector则取数据会更快，但差异不大，因此您最好查看将数据前后推送的频率，以确定是否需要std::vector或std::deque。

还有一件事，如果你使用 for 循环来获取容器的一些索引，你应该更好地使用iterator，因为从中获取数据的速度差异std::vector并且std::deque不会明显。