为什么只有std::list::sort()可以使用？

Question

可能重复：
使用stl sort函数对列表进行排序

C++标准库提供了严格的线性序列容器、线性序列容器和关联容器。

std::sort()可用于所有类型的容器。但为什么它只为列表提供 std::list::sort()？

- vrbilgi

---

可能是因为可以有更优化的实现方式，能够利用列表的实现细节——这些细节可能并不适用于常规排序函数。 - Nim

这里提供了一个解释：[https://dev59.com/K3E95IYBdhLWcg3wJKp_]。 - Vlad

@Nim：不完全是这样。看看回复就知道了。 - John Dibling

Answer 1

std::sort 只适用于随机访问容器。标准库中唯一有意义的非随机访问容器是 std::list。

std::sort 显然不适用于关联式容器，正如你所想的那样。这有什么意义呢？关联式容器是按键值访问的，而不是按位置访问的。

正如 Mike 所指出的，C++11 还引入了 std::forward_list，也有自己的排序函数。

- Benjamin Lindley

---

现在也有std::forward_list。 - Mike Seymour

还要注意，列表排序和标准排序的复杂度保证是不同的。 - Kerrek SB

根据C++11标准，两者都是O(N log N)。 - Yakov Galka

@ybungalobill：是的，你说得对。关键区别在于std::sort重新分配元素，而std::list::sort移动节点而不触及它们的值。 - Kerrek SB

Answer 2

std::sort 只适用于随机访问迭代器，但 std::list 仅提供双向迭代器。因此它不能与 std::sort 一起使用，需要自己实现，这也可能更适用于双向链表的优化算法。

同样，您也无法将 std::map 或 std::set 迭代器与 std::sort 一起使用。但是对于这些情况，您根本不需要使用它，因为它们总是已排序的。

顺便说一下，还有 std::map::find 等函数。虽然可以使用所有迭代器与 std::find，但成员函数版本提供了针对各个容器的优化算法，这比 std::find 的线性复杂度更有效率。

- Christian Rau