如何保持一組向量不重複

我有一個程序在C++中產生大量的整數向量（每個向量都被排序），並且它們的生成速度非常快，而且數量很大，我需要跟蹤它們並消除重複，最後將它們全部打印出來。我應該使用什麼數據結構？如何保持一組向量不重複

我嘗試使用hash_map和unordered_map但我得到的錯誤很多的，似乎他們不支持向量的哈希表（他們怎麼這麼支持字符串，但？）：

(.text+0xdc56): undefined reference to `std::tr1::hash<std::vector<int, std::allocator<int> > >::operator()(std::vector<int, std::allocator<int> >) const' 
objects/Prog.o: In function `std::tr1::_Hashtable<std::vector<int, std::allocator<int> >, std::pair<std::vector<int, std::allocator<int> > const, int>, std::allocator<std::pair<std::vector<int, std::allocator<int> > const, int> >, std::_Select1st<std::pair<std::vector<int, std::allocator<int> > const, int> >, std::equal_to<std::vector<int, std::allocator<int> > >, std::tr1::hash<std::vector<int, std::allocator<int> > >, std::tr1::__detail::_Mod_range_hashing, std::tr1::__detail::_Default_ranged_hash, std::tr1::__detail::_Prime_rehash_policy, false, false, true>::_M_rehash(unsigned long)': 
Prog.cpp:(.text._ZNSt3tr110_HashtableISt6vectorIiSaIiEESt4pairIKS3_iESaIS6_ESt10_Select1stIS6_ESt8equal_toIS3_ENS_4hashIS3_EENS_8__detail18_Mod_range_hashingENSE_20_Default_ranged_hashENSE_20_Prime_rehash_policyELb0ELb0ELb1EE9_M_rehashEm[std::tr1::_Hashtable<std::vector<int, std::allocator<int> >, std::pair<std::vector<int, std::allocator<int> > const, int>, std::allocator<std::pair<std::vector<int, std::allocator<int> > const, int> >, std::_Select1st<std::pair<std::vector<int, std::allocator<int> > const, int> >, std::equal_to<std::vector<int, std::allocator<int> > >, std::tr1::hash<std::vector<int, std::allocator<int> > >, std::tr1::__detail::_Mod_range_hashing, std::tr1::__detail::_Default_ranged_hash, std::tr1::__detail::_Prime_rehash_policy, false, false, true>::_M_rehash(unsigned long)]+0x126): undefined reference to `std::tr1::hash<std::vector<int, std::allocator<int> > >::operator()(std::vector<int, std::allocator<int> >) const' 
collect2: ld returned 1 exit status 
make: *** [run] Error 1

是否有任何其他的方式來解決這個問題？有沒有更好的效率的其他數據結構？

來源

2014-03-25 orezvani

只要您創建自己的'hash '，您就可以擁有任何類型「T」的哈希映射。在你的情況下，你需要定義類似'my_vector_hash'的東西，它接受你的一個向量併爲它計算一個散列值。 –

所以你想刪除向量中重複的向量或向量與重複的元素或重複的元素？ ;） –

@NiklasB。一旦載體返回，我應該看它是否存在或不存在;如果它不存在，我將它添加到解決方案集。 – orezvani

您需要爲向量提供散列函數以使用unordered_map。字符串的散列函數默認提供。或者，您可以使用std :: set。 std :: set的元素保證沒有重複。

來源

2014-03-25 01:48:22

我也關心效率。如果我使用'std :: set'，插入向量的複雜度將是'O（1）'？ – orezvani

@emab Nop Set在O（1）中可以比較元素時具有O（logN）插入成本。所以你會得到類似於O（logN * K）的東西，其中K是比較兩個向量的代價。 – agarwaen

如何保持一組向量不重複

回答

相關問題