C++ std::map 或 std::set - 有效地插入重复项

Question

我有一堆充满重复的数据，我想消除重复项。你知道，例如[1, 1, 3, 5, 5, 5, 7] 变为 [1, 3, 5, 7]。

看起来我可以使用 std::map 或 std::set 来处理这个问题。但是，我不确定 (a) 将所有值简单地插入容器中是否更快，或者 (b) 检查它们是否已经存在于容器中并且仅在不存在时才插入 - 插入是否非常有效？即使有更好的方法...您能建议一种快速的方法吗？

另一个问题 - 如果我存储在其中的数据不像整数那样微不足道，而是一个自定义类，那么 std::map 如何设法正确存储(散列？)数据以便快速访问通过 operator[]?

Answer 1

std::map不使用散列。 std::unordered_map确实如此，但那是 C++11。 std::map和 std::set两者都使用您提供的比较器。类模板具有此比较器的默认值，归结为 operator<比较，但您可以提供自己的。

如果您不需要同时存储键和值(看起来您不需要)，您应该只使用 std::set ，因为这样更合适。

标准没有说明什么数据结构map s 和 set在引擎盖下使用，只是某些 Action 具有一定的时间复杂性。实际上，我所知道的大多数实现都使用树。

如果您使用 operator[]，在时间复杂度方面没有区别或 insert , 但我会使用 insert或 operator[]在我做 search 之前接着是 insert如果找不到该项目。后者将意味着两次单独的搜索以将项目插入到集合中。