C++如何管理连续动态数组的迭代器

Question

我一直试图找出一种管理动态数组的有效方法,我可能偶尔会改变它,但是想要经常随机访问和迭代.

我希望能够:

• 将数组存储在连续数据块中(减少缓存未命中)
• 单独访问每个元素并独立于数组句柄(指针>索引)
• 调整数组大小(动态)

因此,为了实现这一点,我一直在尝试使用std::vector<T>::iterator,并且它工作得非常好,直到最近,当我调整向量(例如调用push_back())时,我正在存储迭代器.所有迭代器都变得无效,因为它们指向过时的内存.

是否有任何有效的(可能是STL-)方法来保持迭代器指针的最新状态？或者我是否必须手动更新每个迭代器？

这整个方法是否值得？我应该坚持指数吗？

编辑:我之前使用过指数并且没问题,但是我改变了我的方法因为它仍然不好.我总是要把整个数组拖到范围内,索引可以很容易地用于任何数组.也没有完美的方法来定义"NULL"索引(我都不知道).

更新所有指针以及调整大小操作的选项怎么样？您所要做的就是存储原始文件vector::begin,调整大小vector,然后更新所有指针vector.begin() + (ptr - prevBegin)并调整操作大小已经是您应该尽量避免的.

Answer 1

完全实现所有3个目标是不可能的.如果你是完全连续的,那么你有一个有限大小的内存块,获得更多内存的唯一方法是要求更多的内存,这将与你已有的内存不相连.所以你必须至少在某种程度上牺牲至少一个要求:

• 如果你愿意部分牺牲邻接,你可以使用std::deque.这是一种数组数组结构.它不会使引用无效,因为我认为任何增加其大小的操作.它取决于您的数据类型的详细信息,但通常其性能对于连续数组而言比链接列表非常接近.做得好但是旧的(5年)基准:https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html.另一个选择是编写一个分块分配器,与deque其他结构一起使用.这是相当多的工作.
• 如果你可以使用索引,那么你可以使用一个 vector
• 如果您不需要调整大小,您仍然可以使用a vector并且从不调整它.

除非你有充分的理由,否则我会坚持使用指数.如果你的主要性能瓶颈是与大量元素相关的迭代(正如你的连续性要求所暗示的那样),那么整个索引的东西应该是一个非问题.如果你有一个很好的理由,以避免指数(你没有说),那么我会轮廓deque相对于vector主环路操作,看看有多少糟糕的deque确实.它可能只是差一点,如果它既不适合你,deque也不vector适合你,下一个替代方案是相当多的工作(可能涉及分配器或自定义数据结构).