Jam*_*lis 18
正如已经说过的那样,标准库提供了一个非成员函数模板,可以在给定一对随机访问迭代器的情况下对任何范围进行排序.
使用成员函数对向量进行排序将是完全多余的.以下内容具有相同的含义:
std::sort(v.begin(), v.end());
v.sort();
STL的第一个原则之一是算法不与容器耦合.如何存储数据以及如何操作数据应尽可能松散耦合.
迭代器用作容器(存储数据)和算法(对数据进行操作)之间的接口.通过这种方式,您可以编写一次算法,它可以在各种类型的容器上运行,如果您编写一个新容器,现有的通用算法可用于操作其内容.
,之所以std::list提供它自己的sort功能作为一个成员函数,它不是一个随机访问的容器; 它只提供双向迭代器(因为它用于表示双向链表,这是有道理的).泛型std::sort函数需要随机访问迭代器,因此您不能将它与a一起使用std::list. std::list提供自己的sort功能,以便可以进行排序.
通常,有两种情况,容器应该实现算法:
如果通用算法不能对容器进行操作,但是有一个不同的,特定于容器的算法可以提供相同的功能,就像这样std::list::sort.
如果容器可以提供比通用算法更有效的算法的特定实现,就像这样std::map::find,允许在对数时间内在地图中找到元素(通用std::find算法执行线性搜索,因为它不能假设范围已排序).
目前已经有答案的有趣的元素，但其实更多是约的问题说：当回答“为什么不std::vector有一个sort成员函数？” 确实是“因为标准库只在提供比泛型算法更多的时候才提供成员函数”，真正有趣的问题是“为什么std::list要有sort成员函数？”，还有一些事情还没有解释：是的，std::sort只有效使用随机访问迭代器并且std::list只提供双向迭代器，但即使std::sort使用双向迭代器，std::list::sort仍然会提供更多. 这就是原因：
首先，std::list::sort是稳定的，而std::sort不是。当然还有std::stable_sort，但它也不适用于双向迭代器。
std::list::sort通常实现合并排序，但它知道它正在对列表进行排序并且可以重新链接节点而不是复制内容。列表感知归并排序可以在 O(n log n) 时间内对列表进行排序，仅需要 O(log n) 额外内存，而典型的归并排序（例如std::stable_sort）使用 O(n) 额外内存或具有 O(n log² n) ) 复杂性。
std::list::sort不会使迭代器无效。如果迭代器指向列表中的特定对象，它在排序后仍将指向同一个对象，即使它在列表中的位置与排序前不同。
最后但并非最不重要的一点是，std::list::sort不会移动或交换对象，因为它只会重新链接节点。这意味着当您需要对移动/交换成本高昂的对象进行排序时，它可能会更高效，而且它可以对甚至不可移动的对象列表进行排序，这对于std::sort!
基本上，即使std::sort并std::stable_sort使用双向或前向迭代器（这完全有可能，我们知道与它们一起使用的排序算法），它们仍然无法提供所有std::list::sort必须提供的东西，并且它们也无法重新链接节点，因为标准库算法不允许修改容器，只能修改指向值（重新链接节点算作修改容器）。另一方面，专用std::vector::sort方法不会提供任何有趣的东西，因此标准库不提供。
请注意，已经说过的所有内容std::list::sort也适用于std::forward_list::sort。
具体的载体排序不会提供优势std::sort的<algorithm>.但是,std::list提供它自己的,sort因为它可以使用如何list实现的特殊知识来通过操纵链接而不是复制对象来对项目进行排序.