真的很简单的问题。在 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 似乎不是一个巨大的交易来换取恒定的时间推送和弹出前端。
最佳答案
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
连续的额外要求。
关于c++ - 为什么 std::vector 不使用偏移量?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37555523/