爲什麼只有std :: list :: sort（）？

可能重複：
Sort list using stl sort function 爲什麼只有std :: list :: sort（）？

C++標準庫給出嚴格線性序列容器，線性序列容器，關聯容器。

std::sort()適用於各種容器。但爲什麼只有它提供了排序清單。 std::list::sort()？

2011-11-03 vrbilgi

大概是因爲可以有一個更優化的實現，可以利用列表的實現細節 - 這可能無法用於一般的排序功能 – Nim

給出了一個解釋[here]（http://stackoverflow.com/questions/2432857 /排序列表使用-STL排序函數）。 – Vlad

@Nim：不是。查看回復。 –

std::sort只適用於隨機存取容器。標準庫中唯一的非隨機訪問容器，它是有意義的排序是std::list。

std::sort肯定不會在關聯容器上工作，因爲您似乎認爲。這會產生什麼意義？關聯容器可以通過鍵的值訪問，而不是按位置訪問。如Mike所述，C++ 11也有std::forward_list，這並不意外，它也有自己的排序功能。

2011-11-03 14:03:21

這些天還有'std :: forward_list'。 –

另請注意，列表排序和標準排序的複雜性保證是不同的。 –

@KerrekSB：根據C++ 11，兩者都是O（N log N）。 – ybungalobill

std::sort只適用於隨機訪問迭代器，但std::list只提供雙選迭代器。因爲它因此不能與std::sort一起使用，所以它需要它自己的實現，對於雙向鏈表也可能更加優化。

同樣，您不能使用std::map或std::set迭代器與std::sort。但對於這些你不需要它，因爲它們總是被分類。

作爲附註，也有std::map::find等。這些確實不是必需的，因爲您可以將所有迭代器與std::find一起使用。但是成員函數版本爲單個容器提供了優化的算法，這些算法比std::find的線性複雜度更高效。

2011-11-03 14:04:27

回答