哪种STL容器最适合std::sort？（这真的重要吗？）

Question

哪种STL容器最适合std::sort？（这真的重要吗？）

c++stlsorting

16

标题已经说明了问题....

选择容器是否会影响默认的std::sort算法的速度？例如，如果我使用list，排序算法只是切换节点指针还是同时切换节点中的所有数据？

- Karel Bílek

谢谢大家……我之前不知道list::sort，现在知道了。 - Karel Bílek

9个回答

12

我认为 std::sort 在列表上不起作用，因为它需要随机访问迭代器，而 list<> 不提供这种类型的迭代器。请注意，list<> 提供了一个名为 sort 的方法，但它与 std::sort 完全不同。

容器的选择确实很重要。STL 的 std::sort 依赖于迭代器来抽象化容器存储数据的方式。它只使用您提供的迭代器来移动元素。这些迭代器在访问和分配元素方面工作得越快，std::sort 就会运行得越快。

- Mehrdad

1

不确定标准对此问题的立场，但像快速排序这样的算法实际上并不需要随机访问迭代器。它们只需要指向要排序的子范围中第一个和最后一个项目的指针/迭代器即可。快速排序在双向链表上也可以正常工作。 - Andy Ross

8

std::list 绝对不是std::sort() 的好选择，因为 std::sort() 需要随机存取迭代器。 std::map 和其他关联容器也不行，因为无法强制执行元素的位置；也就是说，元素在 map 中的位置不能通过特定位置插入或交换来强制执行。在标准容器中，我们只能选择使用std::vector和std::deque。

std::sort() 像其他标准算法一样，仅通过交换元素值(*t = *s)来操作。即使列表可以神奇地支持O(1)访问，链接也不会被重新组织，而是它们的值会被交换。

由于std::sort() 不会改变容器的大小，在运行时性能方面，使用std::vector 或者 std::deque应该没有区别。原始数组排序速度也应该很快，可能甚至比标准容器更快--但我并不希望这种差异足以证明使用它们的价值。

- wilhelmtell

自从什么时候开始，std::map和std::set就不是有序的了？ - MartinStettner

我的意思是顺序由容器指定，而不是由用户指定。 - wilhelmtell

顺序不是由容器决定的，而是由 map 或 set 中类型的 operator< 运算符决定的。 - Brian Neal

..或者通过comp参数。但是你明白我的意思。std::sort在std::map的变体上毫无意义。 - wilhelmtell

同意，你甚至不能在它们上面调用。 - Brian Neal

这是问题的真正答案。 - Bamboo

6

这取决于元素类型。

如果您只存储指针（或POD），那么vector将是最快的。如果您存储对象，则list的排序会更快，因为它会交换节点而不是物理元素。

- Andrew Grant

我认为这个问题只是针对std::sort()的。 - wilhelmtell

1

这是因为我不知道list::sort，所以才会这样。我喜欢Stack Overflow，感谢大家 :) - Karel Bílek

+1。但是要明确的是，std::list确实直接在节点结构体内存储对象--list::sort()只是交换这些节点内部指针的值。 - j_random_hacker

你有什么数字证据支持这个观点吗？虽然我没有，但根据我的经验，对于排序大型对象来说，列表比向量要慢得多。运算的局部性和排序算法、处理器高速复制的事实都起到了一定作用。不过，这取决于许多因素！ - MattyT

没有，这只是我多年来观察到的！根据向量中的内容可能会有很大的变化 - 例如，如果对象在相似的时间分配，则内存访问模式将更好！归根结底，任何重要的事情都应该经过测试和测量。 - Andrew Grant

@MattyT：看起来C++标准并没有提到仅交换节点指针，所以你可能是对的——但任何体面的实现都会这样做。（例如SGI的STL实现声明，在sort()之后迭代器将继续指向它们原来的元素，这意味着这一点。） - j_random_hacker

1

我完全同意上面的观点。但是学习新知识最好的方法是什么？嘿！！！当然不是阅读文本并死记硬背，而是……例子 :D 最近我沉浸在STL中指定的容器中，这里是一个简单易懂的快速测试代码，希望能够自我解释：

#include <iostream>
#include <vector>
#include <deque>
#include <array>
#include <list>
#include <iterator>
#include <cstdlib>
#include <algorithm>
#include "Timer.h"

constexpr int SIZE = 1005000;

using namespace std;

void test();

int main(){
    cout<<"array allocates "<<static_cast<double>(SIZE)/(1024*1024)<<" MB\n";
    test();


    return 0;
}


void test(){
    int values[SIZE];
    int size = 0;

    //init values to sort:
    do{
        values[size++] = rand() % 100000;
    }while(size < SIZE);

    //feed array with values:
    array<int, SIZE> container_1;
    for(int i = 0; i < SIZE; i++)
        container_1.at(i) = values[i];

    //feed vector with values
    vector<int> container_2(begin(values), end(values));
    list<int> container_3(begin(values), end(values)); 
    deque<int> container_4(begin(values), end(values)); 

    //meassure sorting time for containers
    {
       Timer t1("sort array");
       sort(container_1.begin(), container_1.end());
    }

    {
       Timer t2("sort vector");
       sort(container_2.begin(), container_2.end());
    }

    {
       Timer t3("sort list");
       container_3.sort();
    }

    {
       Timer t4("sort deque");
       sort(container_4.begin(), container_4.end());
    }

}

计时器的代码如下：

#include <chrono>
#include <string>
#include <iostream>

using namespace std;

class Timer{

public:
    Timer(string name = "unnamed") : mName(name){ mStart = chrono::system_clock::now();}
    ~Timer(){cout<<"action "<<mName<<" took: "<<
             chrono::duration_cast<chrono::milliseconds>(
                     chrono::system_clock::now() - mStart).count()<<"ms"<<endl;}
private:
    chrono::system_clock::time_point mStart;
    string mName;
};

以下是无优化时的结果（使用g++ --std=c++11 file.cpp -o a.out）：

数组分配了0.958443 MB 对数组进行排序的操作花费了183毫秒对向量进行排序的操作花费了316毫秒对列表进行排序的操作花费了725毫秒对双端队列进行排序的操作花费了436毫秒

以下是使用优化后的结果（使用g++ -O3 --std=c++11 file.cpp -o a.out）：

数组分配了0.958443 MB 对数组进行排序的操作花费了55毫秒对向量进行排序的操作花费了57毫秒对列表进行排序的操作花费了264毫秒对双端队列进行排序的操作花费了67毫秒

需要注意的是，虽然在这种情况下向量和数组的排序时间相似，但由于数组的大小受限（默认情况下应该在堆栈上初始化，而不使用自己的分配器等），因此这取决于是否为编译器使用优化。如果没有使用优化，我们可能会看到明显的差异。

- Lukasz

1

排序算法不知道你的容器是什么，它只知道随机访问迭代器。因此，你可以对不在STL容器中的东西进行排序。因此，其速度取决于你给它的迭代器，以及解引用和复制它们指向内容的速度。

std::sort无法在std::list上工作，因为sort需要随机访问迭代器。在这种情况下，你应该使用std::list的一个成员函数sorts。这些成员函数将有效地交换链接列表指针而不是复制元素。

- Brian Neal

std::sort 不适用于 std::list（它需要随机访问），这就是为什么有 std::list::sort 的存在。 - user83255

我意识到在我输入后，现在已经被更正了。谢谢。 - Brian Neal

1

向量。

始终使用向量作为默认容器。它具有任何其他容器中最低的空间开销和最快的访问速度（除了其他优点，如与 C 兼容的布局和随机访问迭代器）。

现在，问问自己 - 你的容器还需要做什么？你需要强大的异常保证吗？列表、集合和映射可能是更好的选择（虽然它们都有自己的排序例程）。你需要经常向容器前面添加元素吗？考虑双端队列。你的容器是否需要始终保持排序？集合和映射可能更适合。

最后，确定对于你来说“最佳”是什么，然后选择最合适的容器并测量其在满足你需求方面的表现。

- MattyT

0

这确实很重要，因为不同的容器具有不同的内存访问模式等，这可能会起到作用。

然而，std::sort 无法在 std::list<>::iterators 上工作，因为它们不是 RandomAccessIterators。此外，虽然可以为 std::list<> 实现一个特化版本来洗牌节点指针，但它可能会产生奇怪和令人惊讶的语义后果 - 例如，如果您在向量中的排序范围内拥有迭代器，则其值将在排序后更改，而这在此特化中不成立。

- jpalecek

0

std::sort需要随机访问迭代器，因此您唯一可以使用的选项是vector或deque。它将交换值，并且猜测vector可能比deque执行得稍微快一些，因为它通常具有更简单的底层数据结构。不过差异可能非常微小。

如果您使用std::list，则有一个专门化（std::list::sort），应该交换指针而不是值。但是，由于它不是随机访问，它将使用归并排序而不是快速排序，这可能意味着算法本身会慢一些。

无论如何，我认为答案通常是vector。如果每个元素都有大型类，因此复制开销占主导地位，则list可能会击败它。或者，您可以在vector中存储对它们的指针，并提供自定义谓词以适当地对它们进行排序。

- Peter

快速排序可以使用链表高效地实现（简单来说，每个链表元素被移动到两个新链表之一，然后这些链表在枢轴出现的位置连接起来）。此外，原始数组可以使用std::sort()进行排序。 - j_random_hacker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- anon · Accepted Answer

选择确实会产生影响，但预测哪种容器最有效是非常困难的。最好的方法是使用对您的应用程序最易于使用的容器（可能是std::vector），查看该容器是否足够快速地进行排序，如果是，则坚持使用它。如果不是，请对您的排序问题进行性能分析，并根据分析数据选择不同的容器。

作为一名前讲师和前培训师，我有时会感到个人责任，因为人们普遍认为链表具有神秘的性能增强属性。从一个知道真相的人那里得到这个结论：链表出现在很多教科书和教程中的唯一原因是因为对于编写这些书籍和教程的人来说，拥有一个可以说明指针、动态内存管理、递归、搜索和排序的数据结构非常方便——这与效率无关。