我一直在浏览C++ STL，但我不确定哪种数据结构最适合这个特定的用例。 它需要能够在恒定的时间内完成以下三件事：
常- 量时间 按索引随机访问(因此可以在常量时间内选择随机元素(
- 仅在末端持续推送/弹出
- 推送/弹出时，指向所包含项的指针不能失效(不关心迭代器(
最初，我尝试使用向量;它完全满足前两个条件。 然而，我学到了艰难的方式，当你将新项目推送到向量上时，指向其元素的指针将失效，因为向量会重新定位自身以保持其所有内存连续。 虽然这个问题可以通过提前使用向量的reserve()方法来解决，但问题是它需要知道我可能需要存储在其中的最大数量的元素，这不是我提前知道的值，我也无法真正计算它。 我也不能在大小变大时再次使用保留，因为指向向量元素的指针仍然会失效。
所以后来我尝试了一个deque。 信不信由你，一个deque实际上完全满足了这三个标准。 指向元素的指针不会因推送/弹出而失效，这是恒定时间。 但是，我注意到有成本;双克比矢量慢约两倍。 我知道 deque 具有能够将项目放在前面的额外功能，这对于我的目的来说是不必要的，我不确定是专门用于这种附加功能还是并非所有内存都连续保存的事实导致速度变慢。
因此，虽然 deque 确实满足这三个标准，但 C++ STL 中是否有一种数据结构可以做得更好？ 或者也许是矢量的解决方法，以防止指针失效？ 你觉得怎么样？
你基本上需要一个std::deque，但是std::deque是基于std::vector如果达到容量并且必须分配一个新的连续内存块，则所有迭代器都会失效(参考(。由于您不关心迭代器失效，因此这不会打扰您，并且std::deque结构足以满足您的用例。看看参考资料。但是，如果您只想拥有一个push/pop接口，请考虑编写包装器。