什麼是當前在C++中使用最廣泛的集合集合

我正在C++中搜索一組容器。我想要一些我可以添加元素的地方，但是他們不會重複多次，並且在那個集合中搜索將會是O（1）。現在什麼是目前事實上的交叉編譯器容器。我看到一些在boost（如mpl）和未來的C++標準中有一個，但現在和這裏最好使用什麼？什麼是當前在C++中使用最廣泛的集合集合

EDIT在升壓存儲載體的

例:: 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;

來源

2011-06-09 Sergej Andrejev

如果您有支持C++ 0x的兼容編譯器，則可以使用std::unordered_set。

如果你不是這種情況，截取在Microsoft VC++中可用，如stdext::hash_set，或者通常使用boost::unordered_set。後者是目前可移植性最好的選擇，因爲它具有更廣泛的C++ 0x可用性。正如@Nemo的評論所指出的那樣，對於std::tr1::unordered_set也有廣泛的支持，作爲Boost使用的替代方案。

[std::set將是O（log n），因爲它基於搜索樹。爲了得到O（1），你需要使用一個基於哈希表的容器，並適當考慮到有效實施你的成員對象的散列函數]

來源

2011-06-09 12:29:26

。你還可以評論boost :: unsorted_set如何管理更復雜的對象。說一個std：向量。 – 2011-06-09 12:39:39

從機械角度來看，它的工作原理與其他任何物體一樣 - 關鍵是始終提供良好的散列函數，以最大限度地減少衝突並且不會影響性能。對於複雜對象來說，這比對'std :: string'更困難了，它本身已經夠難了。 – 2011-06-09 12:44:02

這一切都取決於你如何爲該矢量對象創建散列函數。例如，你會搜索一個元素一個元素，有點像'memcmp'對數據數組有用，檢查每個元素是否相同，大於或小於彼此，然後確定向量是否相等，當第一次不匹配發生時，是大於還是小於另一個向量？如果你這樣做了，你可以看到散列函數與實際的散列表插入時間相比如何很慢（即與恆定時間相比是線性的）。 – Jason 2011-06-09 12:46:17

C++ 03：boost::unordered_set

C++ 0x：std::unordered_set

以前的實現（在VC++中爲stdext::hash_set）不是交叉編譯器。

注：boost::unordered_set接口已經被重用爲std::unordered_set，因此遷移是一件容易的事

編輯：有趣除了==>如果性能是一個擔心，你想快速測試的情況下，你可能有興趣查找Bloom Filters。

來源

2011-06-09 12:30:12

至少在過去六年中，Microsoft，Apple和GCC支持'std :: tr1 :: unordered_set'。它在什麼意義上不是「交叉編譯器」？ – Nemo 2011-06-09 13:39:32

@Nemo：我不是在討論'std :: tr1 :: unordered_set'，而是關於編譯器在'unordered_set'之前提供的'std :: tr1 :: hash_set'（名稱從編譯器到編譯器）而這實際上是我們爲什麼稱新的'unordered_set'而不是'hash_set'的原因：爲了避免碰撞和混淆。 – 2011-06-09 15:22:59

@Matthieu：我以爲TR1是[技術報告1]（http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf），這是一個由C++工作的文檔組。它定義了'std :: tr1'命名空間，並且絕對不包含任何'hash_set'。你是說一些編譯器把自己的符號放到'std :: tr1'命名空間中嗎？ – Nemo 2011-06-09 17:13:04

爲了獲得O（1）的搜索時間（即恆定的搜索時間），您需要使用基於哈希表的集合，以便得到std::unordered_set和/或boost::unordered_set。當前的C++ 03 std::set和std::multiset基於RB樹，因此具有O（log n）的搜索時間。

來源

2011-06-09 12:33:55 Jason

您可能還想看看Poco C++ libraries的HashSet課程。順便說一句，

來源

2011-06-09 12:50:07 StackedCrooked

從未聽說過波科。它是跨平臺嗎？我能否輕鬆移植它？ – 2011-06-09 12:53:19

@Sergej是的，它是跨平臺的。 – StackedCrooked 2011-06-09 14:50:56

什麼是當前在C++中使用最廣泛的集合集合

回答

相關問題