std::unique為什麼不用一個hash table實現,而是要先std::sort?

前者是O(nlogn),後者是O(n),是因為algorithm通用性的問題,還是因為移動次數或者空間的考量.

---

unique在這個語義下的定義並不是去重，而是去除連續的相同元素: unique - C++ Reference. 因此演算法的時間複雜度本身就是線性O(n)的，說白了就是排序本來就不是這個演算法的一部分。

Linux里的uniq命令也是同樣的設計，就我自己的經驗來看，這麼設計的原因大概就是你說的空間上的考量，以及數據可能已經排序了，碰撞不好解決等等，總之還是那句話，排序不是這個演算法的一部分，如果使用場景更適合hash，完全可以自己再實現。

另外hash table版本的sort+uniq的效率實際上沒有看起來的O(n)那麼好。可以思考一下，hash table不但碰撞處理麻煩，而且時間複雜度的常數很大，因為要比較同一個hash值的元素是不是真正相同，這一步的比較次數是可以退化成O(n)的，那樣總的複雜度就是O(n^2)了。

輪子哥的回答有點偏了，題主在題目中問了，「是因為algorithm通用性的問題，還是因為移動次數或者空間的考量」，既然題主考慮到了通用性，那麼題主肯定沒有認為兩個演算法在功能上是等價的，完全可以由調用者傳入一個哈希函數嘛。

---

涉及 hash table 需要很多額外的信息，例如 hash function、bucket size，並且因為需要分配額外空間需要allocator。如果這些都不考慮，我嘗試利用std::unordered_set（C++11）寫了一個簡單版本：

#include &

template &
ForwardIt unique_unordered(ForwardIt first, ForwardIt last) {
using T = typename std::iterator_traits&::value_type;
std::unordered_set& s;
for (auto itr = first; itr != last; ++itr)
s.insert(std::move(*itr));
for (auto i : s)
*first++ = std::move(i);
return first;
}


但這個版本的結果順序會改變。

---

你要是能給出一個演算法，自動把unique的第三個參數（pred）轉換成一個hash function，那你可以在這麼實現的同時，順便搞個圖靈獎什麼的。

---

Unique不是O(n)？？？？

我貌似看錯題目了

---

推薦閱讀：