目前C++中使用最广泛的集合集合是什么？
我正在寻找 C++ 中的集合容器。我想要一些可以添加元素但它们不会重复多次的东西，并且在该集合中搜索的时间复杂度为 O(1)。目前的事实上的交叉编译器容器是什么？ 我在 boost 中看到了一些（例如 mpl），并且在未来的 C++ 标准中也有一个，但是现在和这里最好使用什么？
编辑
在 boost::unordered_set 容器中存储向量的示例。因此，对我来说，它似乎非常适合我的需求，但我会在其中包含大量数据，因此如果有人立即发现一些潜在的错误，您可以评论一下可能会出现问题的地方。同样，所有元素都将是没有指针的排序向量。
vector<string> values1;
values1.push_back("aaa");
values1.push_back("bbb");
values1.push_back("ccc");
vector<string> values2;
values2.push_back("aa");
values2.push_back("bbb");
values2.push_back("ccc");
vector<string> values3;
values3.push_back("aaa");
values3.push_back("bbb");
vector<string> values4;
values4.push_back("aaa");
values4.push_back("bbb");
values4.push_back("ccc");
values4.push_back("ddd");
vector<string> values5;
values5.push_back("aaa");
values5.push_back("bbb");
values5.push_back("ccc");
vector<string> values6;
values6.push_back("aaa");
values6.push_back("bbb");
values6.push_back("ccc");
values6.push_back("ddd");
boost::unordered_set<vector<string> > collection;
collection.insert(values1); // 1
cout << collection.size() << endl;
collection.insert(values2); // 2
cout << collection.size() << endl;
collection.insert(values3); // 3
cout << collection.size() << endl;
collection.insert(values4); // 4
cout << collection.size() << endl;
collection.insert(values5); // 4
cout << collection.size() << endl;
collection.insert(values6); // 4
cout << collection.size() << endl;
I'm searching for a set container in C++. I want something where I could add elements but they would not repeat more than once and search in that collection would be O(1). What is current defacto cross-compiler container for this now.
I seen some in boost (like mpl) and there is one in future c++ standards, but what is best to use now and here?
EDIT
Example of storing vector in boost::unordered_set container. So for me it seems to fit my need pretty well but I will have a lot of data in it so if somebody sees some potential bug right away can you comment on what can go wrong. Again, all elements will be of sorted vector with no pointers.
vector<string> values1;
values1.push_back("aaa");
values1.push_back("bbb");
values1.push_back("ccc");
vector<string> values2;
values2.push_back("aa");
values2.push_back("bbb");
values2.push_back("ccc");
vector<string> values3;
values3.push_back("aaa");
values3.push_back("bbb");
vector<string> values4;
values4.push_back("aaa");
values4.push_back("bbb");
values4.push_back("ccc");
values4.push_back("ddd");
vector<string> values5;
values5.push_back("aaa");
values5.push_back("bbb");
values5.push_back("ccc");
vector<string> values6;
values6.push_back("aaa");
values6.push_back("bbb");
values6.push_back("ccc");
values6.push_back("ddd");
boost::unordered_set<vector<string> > collection;
collection.insert(values1); // 1
cout << collection.size() << endl;
collection.insert(values2); // 2
cout << collection.size() << endl;
collection.insert(values3); // 3
cout << collection.size() << endl;
collection.insert(values4); // 4
cout << collection.size() << endl;
collection.insert(values5); // 4
cout << collection.size() << endl;
collection.insert(values6); // 4
cout << collection.size() << endl;
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
C++03:
boost::unordered_setC++0x:
std::unordered_set较旧的实现（VC++ 中的
stdext::hash_set）是不是交叉编译器。注意：
boost::unordered_set接口已被std::unordered_set重用，因此迁移也很容易编辑：有趣的补充==>如果性能是一个问题并且您想要快速测试是否存在，您可能有兴趣查找布隆过滤器。
C++03:
boost::unordered_setC++0x:
std::unordered_setOlder implementations (
stdext::hash_setin VC++) are not cross-compilers.Note:
boost::unordered_setinterface has been reused forstd::unordered_set, so the migration is easy tooedit: interesting addition ==> if performance is a worry and you want a quick test for the absence, you might be interested in looking up Bloom Filters.
您需要使用基于哈希表的集合以获得 O(1) 搜索时间（即恒定搜索时间），因此这将是
std::unordered_set和/或boost::unordered_set。当前的 C++03std::set和std::multiset基于 RB 树，因此具有 O(log n) 搜索时间。You need to use a set that is based on a hash-table in order to get O(1) search time (i.e., constant search time), so that would be
std::unordered_setand/orboost::unordered_set. The current C++03std::setandstd::multisetare based on a RB-tree, and therefore have O(log n) search time.您可能还想查看 HashSet 类 < a href="http://pocoproject.org/" rel="nofollow">Poco C++ 库。
You may also want to have a look at the HashSet class from the Poco C++ libraries.
如果您有 C++0x，则可以使用 std::unordered_set支持它的兼容编译器。
如果您不处于这种情况，则可以在 Microsoft VC++ 中使用 stdext::hash_set 进行拦截，或者一般使用 boost::unordered_set。后者是目前可移植性的最佳选择，等待更广泛的 C++0x 可用性。正如 @Nemo 的评论中所指出的，作为 Boost 使用的替代方案，std::tr1::unordered_set 也得到了广泛的支持。
[
std::set将为 O(log n)，因为它基于搜索树。要获得 O(1)，您需要使用基于哈希表的容器，并适当考虑成员对象的哈希函数的有效实现。]You can use std::unordered_set if you have a C++0x compliant compiler that supports it.
If you are not in that situation, intercepts are available in Microsoft VC++ as stdext::hash_set, or in general using boost::unordered_set. The latter is your best bet for portability at present, pending wider C++0x availability. As noted in the comments by @Nemo, there is widespread support for
std::tr1::unordered_setas well, as an alternative to Boost usage.[
std::setwill be O(log n), as it's based on a search tree. To get O(1), you need to use a hashtable-based container, with due regard to efficient implementation of the hash function for your member objects.]