两全其美：矢量与列表的插入/擦除效率
我需要一个容器，它可以为我提供快速索引器，并且在任意插入和删除操作（即在容器的任何位置）中也可以非常高效。
我记得读过有关使用桶的容器的信息，但我似乎无法找到它或追溯引导我找到它的步骤（我将开始使用书签，保证！）
谢谢您。
I need a container that gives me a fast indexer and can also be very efficiency in arbitrary insertion and deletion operations (meaning at any position of the container).
I remember reading about such container that uses buckets but I can't seem to find it or retrace the steps that lead me to it (I will start using the bookmarks, promise!)
Thank you kindly.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可能正在寻找某种哈希映射，例如
boost::unordered_map（很快将纳入 C++ 标准）。还有很多其他的哈希实现。You may be looking for some sort of hash map, like
boost::unordered_map(soon to be in the C++ standard). There are plenty of other hash implementations out there.您正在寻找 std::deque，在许多（但不是全部）情况下，当需要在末端以外的位置插入时，它的性能优于 std::list。它使用“桶”来做到这一点，并支持随机访问。实际上，对于任何标准库容器，您都需要根据应用程序的使用来测试其性能 - 我们无法为您预测什么是最好的。
You are looking for std::deque, which out-performs std::list under many (but not all) circumstances when insertion at places other than the ends is required. It uses "buckets" to do this, and supports random access. Really, for any standard library container, you need to test its performance against your application's use of it - we can't predict for you what will be best.
我需要这种用于我编写的稀疏向量容器的容器，我不能使用map<>因为它需要太多的内存（向量不是那么稀疏）。
我最终使用了压缩位向量。每个枚举值都有自己的位向量，而且效果很好。
我仍然希望我能找到一个高效的向量/列表混合体，它在随机访问时为 O(1)，在擦除/插入时至少为 O(log N)。
I need this kind of container for a sparse vector container that I wrote, I can't use map<> because it takes too much memory (the vector is not that sparse).
I ended up using a compressed bit vector. Each enum value has its own bit vector and this turn up rather well.
I still wish that I could find an efficient vector/list hybrid that is O(1) on random access and at least O(log N) in erase/insert.