c++ - 为什么 std::vector 不使用偏移量？

Question

真的很简单的问题。在 vector 的前面添加或删除时，为什么需要移动所有元素以适应这种变化？使用偏移量来修改索引到 vector 时给出的索引可以解决这个问题。当然，这可能会导致(最多)内存中有 2 个连续的数据 block ，但这似乎是将线性操作减少到恒定时间所付出的很小的代价。

这里有一个尽可能清楚的例子:

['A', 'B', 'C', _, _, _, _, _] offset is 0, 4th through 8th position unused.
push_front('M')
['A', 'B', 'C, _, _, _, _, 'M'] offset is -1

然后在索引时

operator[](size_t index) {
    return backing_array[(index + offset) % size]
}

我明白这意味着可能没有一个纯连续的数据 block ，但从 1 移动到 2 似乎不是一个巨大的交易来换取恒定的时间推送和弹出前端。

Answer 1

I get this means there might not be one pure contiguous block of data

不，那是故事的结尾。 vector 的全部意义在于它是“纯连续数据 block ”。这是实现的基本要求。

执行此操作的能力是 vector 整个目的的核心部分:

T *ptr = &vec[0];
ptr+1;
ptr == &vec[1];

因此，该接口(interface)无法提供阻止 vector 连续的额外要求。