Сортировка диапазона (без дубликатов) в C ++, это std :: vector и std :: sort быстрее, чем std :: set?

Question

У меня есть последовательность double (без дубликатов), и мне нужно отсортировать их. Заполняет ли vector и затем sort быстрее, чем insert значения в 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))).

Набор может быть быстрее для больших объектов, которые невозможно эффективно переместить или поменять местами, поскольку объекты не нужно перемещать более одного раза. Вектор может быть быстрее для небольших объектов, поскольку сортировка не требует обновления указателя и меньшей косвенности.

Что быстрее в любой конкретной ситуации, можно определить только путем измерения (или глубокого знания как реализации, так и целевой платформы).

Answer 2

Использование вектора может быть быстрее из-за факторов кэширования данных, так как обрабатываемые данные будут находиться в более согласованной области памяти (вероятно).

У вектора также будет меньше затрат памяти на значение.

Если вы можете, зарезервируйте размер вектора перед вставкой данных, чтобы минимизировать усилия при заполнении вектора значениями.

Answer 3

Поскольку вы сказали, что сортировка по диапазону, вы можете использовать partial_sort вместо сортировки всей коллекции.
Если мы не хотим нарушать существующую коллекцию и хотим иметь новую коллекцию с отсортированными данными и бездубликаты, то std::set дает нам прямое решение.

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

using namespace std;


int main()
{
    int arr[] = { 1, 3, 4, 1, 6, 7, 9, 6 , 3, 4, 9 };
    vector<int> ints ( arr, end(arr));
    const int ulimit = 5;
    auto last = ints.begin();
    advance(last, ulimit);
    set<int> sortedset;
    sortedset.insert(ints.begin() , last);

    for_each(sortedset.begin(), sortedset.end(), [](int x) { cout << x << "\n"; });
}

Answer 4

Ответ не тривиален. Если в вашем программном обеспечении есть 2 основных раздела: 1-й настройка , 2-й поиск и поиск используется более чем настройка : отсортированный 1009 * может быть быстрее по двум причинам:

1. lower_bound <algorithm> быстрее, чем обычная древовидная реализация <set>,
2. std::vector памяти выделяется меньше страницы кучи, поэтому при поиске элемента будет меньше ошибок на странице.

Если использование смешано, или lookup не больше, чем setup , чем <set> будет быстрее. Больше информации: Скотт Мейерс: Эффективный STL, пункт 23 .

Answer 5

По сложности оба должны быть одинаковыми, т.е. nlog (n).