c++ - 为什么vector没有sort()方法作为vector的成员函数，而list有？

Question

STL 中有一个用于列表的 sort() 方法。这是荒谬的，因为我更倾向于对数组/vector 进行排序。为什么不为 vector 提供 sort()？ vector 容器的创建或使用背后是否有一些基本哲学，没有为它提供排序？

Answer 1

正如已经说过的，标准库提供了一个非成员函数模板，它可以在给定一对随机访问迭代器的情况下对任何范围进行排序。

使用成员函数对 vector 进行排序是完全多余的。以下将具有相同的含义:

std::sort(v.begin(), v.end());
v.sort();

STL 的首要原则之一是算法不与容器耦合。数据的存储方式和数据的操作方式应尽可能松散耦合。

迭代器用作容器(存储数据)和算法(对数据进行操作)之间的接口(interface)。这样，你可以编写一次算法，它可以对各种类型的容器进行操作，如果你编写一个新的容器，就可以使用现有的通用算法来操作它的内容。

std::list之所以提供自己的sort函数作为成员函数，是因为它不是一个随机可访问的容器；它只提供双向迭代器(因为它旨在表示一个双向链表，这是有道理的)。通用 std::sort 函数需要随机访问迭代器，因此您不能将它与 std::list 一起使用。 std::list 提供了自己的 sort 函数，以便对其进行排序。

一般来说，容器应该实现算法有两种情况:

• 如果通用算法不能在容器上运行，但有一个不同的、特定于容器的算法可以提供相同的功能，例如 std::list::sort.

• 如果容器可以提供比通用算法更高效的算法的具体实现，如 std::map::find 的情况，它允许一个元素以对数时间在 map 中找到(通用 std::find 算法执行线性搜索，因为它不能假定范围已排序)。