c++ - C++ STL 数据结构恒定时间推送/弹出/随机访问，通过具有可靠的元素指针的索引

Question

我一直在查看 C++ STL，但我不确定哪种数据结构最适合这个特定用例。它需要能够在恒定时间内完成以下三件事：

1. 恒定时间按索引随机访问（因此可以在恒定时间内选择随机元素）
2. 仅在最后的恒定时间推送/弹出
3. 推送/弹出时指向包含项目的指针不能无效（不关心迭代器）

最初，我尝试使用向量；它完全满足前两个标准。然而，我学到了当你将新项目推送到向量上时，指向其元素的指针将变得无效，因为向量会重新定位自身以保持其所有内存连续。虽然问题可以通过reserve()提前使用向量的方法来解决，但问题是它需要知道我可能需要在其中存储的最大元素数量，而这不是我提前知道的值，我也无法真正计算出来。每当大小变大时，我也不能再次使用reserve，因为指向向量元素的指针仍然会失效。

所以然后我尝试了一个双端队列。信不信由你，一个双端队列实际上完美地满足了所有三个标准。指向元素的指针不会因推送/弹出而失效，这是恒定的时间。但是，我注意到这是有代价的。双端队列比向量慢大约两倍。我知道双端队列具有能够将项目放在前面的附加功能，这对我的目的来说是不必要的，我不确定是不是特别是这种附加功能，或者并非所有内存都保持连续的事实放缓的责任。

因此，虽然双端队列确实满足这三个标准，但 C++ STL 中是否存在可以做得更好的数据结构？或者也许是使用向量的一种解决方法来防止指针失效？你怎么看？

标签： c++c++11data-structuresstltime-complexity

Answer 1

您基本上需要一个std::deque，但是如果达到容量并且必须分配一个新的连续内存块（参考） ，std::deque则基于它会使所有迭代器无效。由于您不关心迭代器失效，因此这不应该打扰您，并且该结构足以满足您的用例。看看参考。但是，如果您只想拥有一个接口，请考虑编写一个包装器。std::vectorstd::dequepush/pop