我不明白为什么 avector的迭代器在重新分配发生时应该失效。
难道不能简单地通过在迭代器中存储一个偏移量——而不是一个指针——来防止这种情况吗？
为什么vector不是这样设计的？
问问题
1035 次
7 回答
15
只是为与性能相关的理由添加一个引用：在设计 C++ 时，Stroustrup 认为像std::vector这样的模板类接近原生数组的性能特征是至关重要的：
强调运行时效率的一个原因是……我希望模板在时间和空间上足够高效，以便用于数组和列表等低级类型。
...
更高级别的替代方案——例如，具有 size() 操作的范围检查数组、多维数组、具有适当数字向量操作和复制语义的向量类型等——只有在他们的运行时才会被用户接受 -时间、空间和符号的便利性接近了内置数组。
换句话说，提供参数化类型的语言机制应该是这样的，相关用户应该有能力消除数组的使用，转而使用标准库类。
Bjarne Stroustrup，C++ 的设计和演变，第 342 页。
于 2012-06-11T01:53:59.037 回答
15
因为迭代器要做到这一点，他们需要存储一个指向向量对象的指针。对于每个数据访问，他们需要跟随指向向量的指针，然后跟随其中的指针指向数据数组的当前位置，然后添加偏移量 * 元素大小。那会慢得多，并且需要为size_type成员提供更多内存。
当然，有时这是一个很好的折衷方案，并且能够在需要时选择它会很好，但它比（C 风格）直接使用数组更慢、更笨重。 std::vector在引入 STL 时，对性能进行了无情的审查，并且正常的实现针对空间和速度进行了优化，超过了这个便利性/可靠性因素，就像等效数组与数组operator[]一样快，但安全性低于at().
于 2012-06-11T01:09:35.890 回答
5
您可以通过包装标准来增加安全性std::vector<T>::iterator，但不能通过包装来增加速度extension::vector<T>::safe_iterator。这是一般原则，并解释了许多 C++ 设计选择。
于 2012-06-11T08:58:15.423 回答
3
这些决定有很多原因。正如其他人指出的那样，向量的最基本实现iterator是指向元素的普通指针。为了能够处理push_back迭代器，必须修改以处理指向向量和位置的指针，在通过运算符访问时，必须取消引用向量指针，获得指向数据的指针并添加位置，并带有额外的取消引用。
虽然这不是最有效的实施方式，但这并不是真正的限制因素。VS/Dinkumware 库（甚至在发行版中）中迭代器的默认实现是检查迭代器，它管理等量的信息。
实际问题来自其他变异操作。考虑在矢量中间插入/擦除。为了保持所有迭代器的有效性，容器必须跟踪迭代器的所有实例并调整位置字段，以便它们仍然引用相同的元素（已被插入/删除替换）。
于 2012-06-11T02:38:26.397 回答
1
您需要存储偏移量和指向矢量对象本身的指针。
如指定的那样，迭代器可以只是一个指针，它占用的空间更少。
于 2012-06-11T01:08:42.883 回答
1
TL；DR——因为您正在用简单的无效规则换取更复杂的远距离操作规则。
请注意，“存储指向向量对象的指针”会导致新的失效情况。例如，今天swap保留了迭代器的有效性，如果指向向量的指针（或引用）存储在迭代器中，则它不再可以。所有移动向量元数据本身的操作（向量的向量有人吗？）将使迭代器无效。
您交易的是“当对元素的指针/引用无效时迭代器变得无效”为“当对向量的指针/引用无效时迭代器变得无效”。
性能参数并不重要，因为建议的替代实现甚至都不正确。
于 2016-12-08T17:24:17.360 回答
0
我的迭代器没有失效，它应该指向同一个元素还是在它之前的插入之后指向同一个位置？换句话说，即使没有性能问题，决定使用哪个替代定义也并非易事。
于 2012-06-11T15:01:23.373 回答