c++ - 在 C++ 中对范围(没有重复项)进行排序，std::vector 和 std::sort 是否比 std::set 更快？

Question

我有一个 double 序列(没有重复项)，我需要对它们进行排序。填充 vector 然后对其进行排序是否比将值插入 set 更快？

这个问题是否可以在不了解标准库的实现(并且不了解程序将在其上运行的硬件)但仅使用 C++ 标准提供的信息的情况下回答？

#include <vector>
#include <set>
#include <algorithm>
#include <random>
#include <iostream>

std::uniform_real_distribution<double> unif(0,10000);
std::default_random_engine re;

int main()
{
    std::vector< double > v;
    std::set< double > s;
    std::vector< double > r;
    size_t sz = 10;
    for(size_t i = 0; i < sz; i++) {
        r.push_back( unif(re) );
    }

    for(size_t i = 0; i < sz; i++) {
        v.push_back(r[i]);
    }
    std::sort(v.begin(),v.end());

    for(size_t i = 0; i < sz; i++) {
        s.insert(r[i]);
    }

    return 0;
}

Answer 1

从 C++ 标准来看，我们只能说它们都具有相同的渐近复杂度 (O(n*log(n)))。

对于无法有效移动或交换的大型对象，该集合可能会更快，因为对象不需要移动多次。对于小对象， vector 可能更快，因为对它进行排序不涉及指针更新和更少的间接。

在任何给定情况下哪个更快只能通过测量(或对实现和目标平台的透彻了解)来确定。