将非重复元素添加到 STL 容器中的最有效方法是什么？哪种容器最快？我有大量数据，恐怕每次我尝试检查它是否是新元素时，都会花费很多时间。我希望 map 非常快。
// 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)
最佳答案
两者都是 set和 map有O(log(N))查找键的性能。 vector有O(N) .
set之间的区别和 map ，至于你应该关心的是，你是否需要将一个键与一个值相关联，或者只是直接存储一个值。如果您需要前者，请使用 map ，如果您需要后者，请使用 set .
在这两种情况下，您都应该使用 insert()而不是做 find() .
原因是insert()当且仅当容器尚未包含该值时(在 map 的情况下，如果容器不包含该键)，才会将该值插入容器中。这可能看起来像
Map.insert(std::make_pair(Element, ID));
map 或
Set.insert(Element);
一组。
您可以引用返回值来确定是否实际执行了插入。
如果您使用的是 C++11，您还有两个选择，即 std::unordered_map和 std::unordered_set .这些都摊销了O(1)插入和查找的性能。但是，它们还要求键(或值，在 set 的情况下)是可散列的，这意味着您需要专门化 std::hash<>为你的 key 。相反，std::map和 std::set要求您的键(或值，在 set 的情况下)响应 operator<() .
关于c++ - 对于非重复项，最有效的标准容器是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14469785/