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

Question

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

这是一个尽可能清晰的例子:

['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]
}

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

Answer 1

我明白这意味着可能没有一个纯粹连续的数据块

不,这就是故事的结尾.整个问题vector是它是一个"纯粹的连续数据块".这是实施的基本要求.

这样做的能力是vector整个目的的核心部分:

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

因此,接口不能提供防止vector连续的附加要求.

Answer 2

向量背后的整个想法是针对单个连续的数据块:例如,您可以将它们(好的,第一个元素的地址)传递给C API,获得良好的缓存局部性等.

本标准规定deque了恰好你所需要的场景:快速推/流行的容器的正面/背面.