c++ - 哪个 STL 容器最适合 std::sort？ (这还重要吗？)

Question

标题不言自明....

容器的选择是否会以某种方式影响默认 std::sort 算法的速度？比如我用list，排序算法是切换节点指针还是切换节点中的全部数据？

Answer 1

选择确实会产生影响，但预测哪个容器最有效是非常困难的。最好的方法是使用对您的应用程序来说最容易使用的容器(可能是 std::vector)，看看该容器的排序是否足够快，如果是的话，坚持使用它。如果没有，请对您的排序问题进行性能分析，并根据配置文件数据选择不同的容器。

作为一名前讲师和前培训师，我个人有时会为链表具有神秘的性能增强属性这一普遍观点负责。从一个知道的人那里知道:链表出现在这么多教科书和教程中的唯一原因是因为编写这些书和教程的人有一个可以说明指针、动态内存管理、递归的数据结构很方便，搜索和排序合二为一——与效率无关。