c++ - C++中目前使用最广泛的set集合是什么

Question

我正在寻找 C++ 中的集合容器。我想要一些东西，我可以在其中添加元素，但它们不会重复多次，并且在该集合中搜索将是 O(1)。目前的实际交叉编译器容器是什么。我在 boost 中看到了一些(比如 mpl)并且在未来的 c++ 标准中有一个，但是现在和这里最好使用什么？

编辑

在 boost::unordered_set 容器中存储 vector 的示例。所以对我来说，它似乎非常适合我的需要，但我会有很多数据在里面，所以如果有人立即看到一些潜在的错误，你能评论一下可能出错的地方。同样，所有元素都将是没有指针的排序 vector 。

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;

Answer 1

您可以使用 std::unordered_set如果您有支持它的 C++0x 兼容编译器。

如果您不在那种情况下，Microsoft VC++ 中的拦截可用 stdext::hash_set , 或者一般使用 boost::unordered_set .后者是目前可移植性的最佳选择，等待更广泛的 C++0x 可用性。正如@Nemo 在评论中指出的那样，std::tr1::unordered_set 也得到广泛支持，作为 Boost 用法的替代方法。

[std::set 将是 O(log n)，因为它基于搜索树。要获得 O(1)，您需要使用基于哈希表的容器，并适当考虑成员对象的哈希函数的高效实现。]