我一直在查看 C++ STL，但我不确定哪种数据结构最适合这个特定用例。它需要能够在恒定时间内完成以下三件事:
- Constant time Random Access by Index(因此可以在恒定时间内选择随机元素)
- 仅在最后恒定时间推送/弹出
- 在压入/弹出时指向包含项的指针不能无效(不关心迭代器)
最初，我尝试使用 vector ；它完全满足前两个标准。但是，我通过艰难的方式了解到，当您将新项目推送到 vector 上时，指向其元素的指针将失效，因为 vector 会重新定位自身以保持其所有内存连续。虽然这个问题可以通过提前使用 vector 的 reserve() 方法来解决，但问题是它需要知道我可能需要在其中存储的最大元素数量，这是不是我提前知道的值，我也无法真正计算它。我也不能在大小变大时再次使用保留，因为指向 vector 元素的指针仍然会失效。
然后我尝试了双端队列。信不信由你，双端队列实际上完全满足所有三个条件。指向元素的指针不会因推送/弹出而失效，它们是恒定时间。但是，我注意到这是有代价的；双端队列比 vector 慢大约两倍。我知道 deque 具有能够将项目放在前面的额外功能，这对我的目的来说是不必要的，而且我不确定它是否特别是这种额外的功能或者并非所有内存都是这样的事实保持连续，这是导致减速的原因。
因此，虽然双端队列确实满足这三个标准，但 C++ STL 中是否有可以做得更好的数据结构？或者也许是 vector 的变通方法以防止指针失效？你怎么看？
最佳答案
您基本上需要一个 std::deque，但是 std::deque 是基于 std::vector 的，它会在以下情况下使所有迭代器失效达到容量并且必须分配一个新的连续内存块(Reference)。由于您不关心迭代器失效，这不应该打扰您，std::deque 结构足以满足您的用例。看看 reference .但是，如果您只想拥有一个 push/pop 接口(interface)，请考虑编写一个包装器。
关于C++ STL 数据结构常量时间推送/弹出/通过索引随机访问元素的可靠指针，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52015967/