哪个STL容器最适合std :: sort？(这甚至重要吗？)

标题不言自明......

容器的选择是否会以某种方式影响默认的std :: sort算法的速度？例如,如果我使用list,排序算法是仅切换节点指针还是切换节点中的整个数据？

选择确实有所作为,但预测哪个容器最有效是非常困难的.最好的方法是使用最容易让你的应用程序使用的容器(可能是std :: vector),看看对那个容器的排序是否足够快,如果是这样的话.如果没有,请对排序问题进行性能分析,并根据配置文件数据选择不同的容器.

作为一名前讲师和前任培训师,我有时会对链接列表具有神秘性能增强属性的共同观点负责.从一个知道的人那里得到它:链接列表出现在如此多的教科书和教程中的唯一原因是因为它对于编写这些书籍和教程的人来说很方便,它具有可以说明指针,动态内存管理,递归的数据结构,搜索和排序一体 - 它与效率无关.

我不认为std::sort在列表上工作,因为它需要一个随机访问迭代器,它不是由a提供的list<>.请注意,它list<>提供了一种sort方法,但它完全独立于std::sort.

容器的选择很重要.STL std::sort依靠迭代器来抽象容器存储数据的方式.它只是使用您提供的迭代器来移动元素.迭代器在访问和分配元素方面的std::sort工作速度越快,工作速度就越快.

std::list绝对不是一个好的(有效的)选择std::sort(),因为std::sort()需要随机访问迭代器. std::map和朋友也不好,因为元素的位置不能强制执行; 也就是说,用户在插入特定位置或交换时无法强制执行地图中元素的位置.在标准容器中,我们需要std::vector和std::deque.

std::sort()就像其他标准算法一样,它只通过在(*t = *s)周围交换元素的值来起作用.因此,即使列表神奇地支持O(1)访问,链接也不会被重组,而是它们的值将被交换.

由于std::sort()不改变容器的大小是否使用它应该在运行时的性能没有区别std::vector或std::deque.原始数组也应该快速排序,甚至可能比标准容器更快 - 但我不认为速度的差异足以证明使用它们是合理的.

这取决于元素类型.

如果你只是存储指针(或POD),那么矢量将是最快的.如果你正在存储对象,那么列表的排序会更快,因为它将交换节点而不是物理元素.