为什么只有std :: list :: sort()？

Question

可能重复:
使用stl排序功能排序列表

C++标准库提供严格的线性序列容器,线性序列容器,关联容器.

std::sort()适用于各种容器.但为什么只提供列表排序.std::list::sort()？

Answer 1

std::sort仅适用于随机访问容器.标准库中唯一一个排序有意义的非随机访问容器是std::list.

std::sort你似乎认为,肯定不会对关联容器起作用.这有什么意义呢？关联容器可通过其键的值访问,而不是按位置访问.

正如迈克所指出的,C++ 11也有std::forward_list,不出意外,它也有自己的排序功能.

Answer 2

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

同样,你不能使用std::map或使用std::set迭代器std::sort.但是对于这些你无论如何都不需要它,因为它们总是被排序.

作为旁注,还有std::map::find其他类似的东西.这些确实不是必需的,因为您可以使用所有迭代器std::find.但是成员函数版本为各个容器提供了优化的算法,这比单独std::find的线性复杂性更有效.