为什么vector :: iterator在重新分配时失效？

Question

我不明白为什么vector在重新分配时应该使迭代器失效.

难道只是通过在迭代器中存储偏移量而不是指针来阻止这种情况吗？

为什么vector没有这样设计？

Answer 1

因为迭代器要这样做,他们需要存储一个指向矢量对象的指针.对于每次数据访问,他们需要按照指向矢量的指针,然后按照其中的指针到数据数组的当前位置,然后添加偏移量*元素大小.这会慢得多,并且会员需要更多内存size_type.

当然,它有时是一个很好的折衷方案,能够在需要时选择它会很好,但它比(C风格)直接阵列使用更慢,更笨重. std::vector在引入STL时,我们对性能进行了无情的审查,并且正常实现针对空间和速度优化了这个便利性/可靠性因素,正如数组等效operator[]速度与数组一样快但不安全at().

Answer 2

只是为与性能相关的理由添加一个引用:在设计C++时,Stroustrup认为像std :: vector这样的模板类接近本机数组的性能特征至关重要:

强调运行时效率的一个原因是我希望模板在时间和空间上足够高效,可用于阵列和列表等低级类型.

...

更高级别的替代方案 - 例如,带有size()操作的范围检查数组,多维数组,具有适当数字向量操作和复制语义的向量类型等 - 只有在运行时才会被用户接受 - 时间,空间和符号方便性接近内置数组.

换句话说,提供参数化类型的语言机制应该使得相关用户应该能够消除使用数组而支持标准库类.

Bjarne Stroustrup,C++的设计和演变,p.342.

Answer 3

你可以通过包装标准来增加安全性std::vector<T>::iterator,但你不能通过包装来增加速度extension::vector<T>::safe_iterator.这是一般原则,并解释了许多C++设计选择.