10

将非重复元素添加到 STL 容器中的最有效方法是什么，哪种容器最快？我有大量的数据，恐怕每次尝试检查它是否是新元素时，都会花费很多时间。我希望地图很快。

// 1- Map
map<int, int> Map;
...
if(Map.find(Element)!=Map.end()) Map[Element]=ID;

// 2-Vector
vector<int> Vec;
...
if(find(Vec.begin(), Vec.end(), Element)!=Vec.end()) Vec.push_back(Element);

// 3-Set
// Edit: I made a mistake: set::find is O(LogN) not O(N)
4

6 回答 6

19

两者都set具有map查找O(log(N))键的性能。vector有O(N)。

set和之间的区别map，就您而言，是您需要将键与值相关联，还是直接存储值。如果您需要前者，请使用 a map，如果您需要后者，请使用 a set。

在这两种情况下，您都应该只使用insert()而不是使用find().

原因是insert()当且仅当容器尚未包含该值时才会将该值插入容器中（在 的情况下map，如果容器不包含该键）。这可能看起来像

Map.insert(std::make_pair(Element, ID));

对于地图或

Set.insert(Element);

为一套。

您可以参考返回值来确定是否实际执行了插入。

如果您使用的是 C++11，您还有两个选择，即std::unordered_map和std::unordered_set. 这些都具有O(1)插入和查找的摊销性能。但是，它们还要求键（或值，在 set 的情况下）是可散列的，这意味着您需要专门std::hash<>针对您的键。相反，std::map并std::set要求您的键（或值，在 set 的情况下）响应operator<().

于 2013-01-22T23:15:19.510 回答
7

如果您使用的是 C++11，则可以使用std::unordered_set. 这将允许您进行O(1)存在检查（技术上已摊销O(1)——O(n)在最坏的情况下）。

std::set可能是您的第二选择O(lg n)。

基本上，std::unordered_set是一个哈希表，std::set是一个树结构（在我见过的每个实现中都是一个红黑树）1。

根据您的散列分布情况以及您拥有的项目数量， std::set 实际上可能更快。如果它确实对性能至关重要，那么一如既往，您将需要进行基准测试。

1）从技术上讲，我不认为需要将其实现为哈希表或平衡 BST。如果我没记错的话，标准只是规定了运行时界限，而不是实现——事实证明，这些是唯一符合界限的可行实现。

于 2013-01-22T23:15:37.960 回答
3

你应该使用std::set; 它是一个容器，旨在保存对象的单个（等效）副本，并实现为二叉搜索树。因此，它在容器的大小上是O(log N)，而不是。O(N)

std::set并且std::map经常共享它们的大部分底层实现；你应该检查你当地的 STL 实施。

说了这么多，复杂性只是衡量性能的一种方式。使用排序向量可能会获得更好的性能，因为它使数据彼此保持本地，因此更有可能命中缓存。如今，缓存一致性是数据结构设计的重要组成部分。

于 2013-01-22T23:15:19.177 回答
1

听起来你想使用std::set. 它的元素是唯一的，因此在添加元素时不需要关心唯一性，并且a.find(k)（其中a是一个std::set和k是一个值）被定义为复杂度的对数。

于 2013-01-22T23:15:34.200 回答
1

如果您的元素可以为 O(1) 散列，那么最好在 aunordered_map或unordered_set（而不是在map/中使用索引，set因为它们在实现中使用 RB 树，这是 O(logN) 发现复杂性）

于 2013-01-22T23:16:19.040 回答
1

您的示例显示了明确的模式：

check if the value is already in container
  if not, add the value to the container.

这两种操作都可能需要一些时间。首先，查找一个元素可以在 O(N) 时间内完成（线性搜索），如果元素没有以任何特定方式排列（例如，只是一个 plain std::vector），它可以在 O(logN) 时间内完成（二分搜索) 如果元素已排序（例如，要么std::map或），并且如果元素被散列（例如，要么或std::set），则可以在 O(1) 时间内完成。std::unordered_mapstd::unordered_set

对于普通向量或无序容器（散列容器），插入将是 O(1)（摊销），尽管散列容器会慢一些。对于 set 或 map 之类的排序容器，您将进行 log-time 插入，因为它需要在插入之前寻找插入它的位置。

所以，结论，使用std::unordered_set或std::unordered_map（如果你需要键值功能）。而且您在插入之前不需要检查，这些是唯一键容器，它们不允许重复。

如果std::unordered_set/ std::unordered_map（来自 C++11）或std::tr1::unordered_set/ std::tr1::unordered_map（自 2007 年以来）对您（或任何等价物）不可用，那么下一个最佳选择是std::set/ std::map。

于 2013-01-22T23:25:39.873 回答