c++ - 选择什么容器来快速搜索/插入大量数据？

Question

所以这是一个思想实验。我想要大量的结构，例如:

struct
{
    KeyType key;
    ValueType value;
}

我需要通过键快速访问并快速插入新值。

我不会使用 std::map，因为它对于一个结构和大量数据来说有太大的内存开销，这可能是极端的。对吧？

所以接下来我会考虑使用排序的 std::vector 和 binary_search。搜索很好，但是向 vector 添加新值会太慢。想象一下，您需要向排序数组的开头添加一个新值，您必须向右移动数据 aaaaaAAAALOT!

如果我使用双端队列呢？据我所知，push_back/push_front 的复杂度为 O(1)，但插入的复杂度仍然为 O(n)(因为无论如何它都必须移动数据，尽管数据更少)。

问题是:

1) 在实际情况下，在双端队列中插入数据的 O(n) 是否比 vector 中的 O(n) 快得多？

2) 当你向双端队列插入一个值并且它应该进入的桶已满时会发生什么？

3) 如果您需要存储大量数据并需要两个快速操作:搜索和插入，是否还有另一种更好的容器类型？

谢谢!

Answer 1

I would not use std::map cuz it has too big memory overhead for one structure and for huge amounts of data it might be drastical. Right?

这取决于您的结构的大小……它们越大，开销在整体内存使用中所占的比例就越小。例如，一个 std::map 实现可能平均说每个元素 20 个字节的内务处理数据(我刚刚编造的 - 在你自己的系统上测量)，所以如果你的结构大小是数百个字节 - 谁在乎...？但是，如果该结构包含 2 个 int，则比例很大....

So next I would consider using sorted std::vector and binary_search. It's fine for searching, but adding new values to the vector would be too slow. Imagine you need to add a new value to the beginning of the sorted array, you'd have to move data right aaaaaAAAALOT!

完全不合适....

1) Is O(n) of inserting data in deque much faster in real situation than O(n) in vector?

由于 deque 很可能实现为固定大小数组的 vector ，插入意味着将所有元素改组到容器的最近端。混洗可能会稍微降低缓存效率，但如果插入到靠近容器前端的位置，它可能仍会更快结束。

2) 当你向双端队列插入一个值并且它应该进入的桶已满时会发生什么？

如上所述，它需要洗牌，溢出:

• 成为下一个“桶”的第一个元素的最后一个元素，移动所有这些元素并溢出到下一个桶等。

• 成为前一个桶的最后一个元素的第一个元素，移动所有这些元素并溢出到下一个桶等。

3) Is there another preferable type of container in case you need to store lots of data and need two fast operations: search and insertion?

unordered_map，实现为 HashMap 。如果您有小对象(例如小于 20 或 30 字节)或元素数量有固定上限，您通常可以使用自定义代码轻松胜过 unordered_map，但很少值得付出努力，除非表访问决定了您应用程序的性能，而该性能至关重要。