Какой контейнер STL лучше всего подходит для std:: sort? (Это даже имеет значение?)

Название говорит само за себя....

Какой-либо выбор контейнера влияет на скорость стандартного алгоритма std:: sort? Например, если я использую список, алгоритм сортировки просто переключает указатели node или он переключает все данные в узлах?

Ответы

Ответ 1

Я не думаю, что std::sort работает в списках, поскольку для него требуется итератор с произвольным доступом, который не предоставляется list<>. Обратите внимание, что list<> предоставляет метод sort, но полностью отделяется от std::sort.

Выбор контейнера имеет значение. STL std::sort полагается на итераторы, чтобы абстрагироваться от того, как контейнер хранит данные. Он просто использует итераторы, которые вы предоставляете для перемещения элементов вокруг. Чем быстрее эти итераторы работают с точки зрения доступа и назначения элемента, тем быстрее будет работать std::sort.

Ответ 2

Выбор действительно имеет значение, но предсказать, какой контейнер будет наиболее эффективным, очень сложно. Лучшим подходом является использование контейнера, который проще всего работать с вашим приложением (возможно, std::vector), проверьте, правильно ли выполняется сортировка с этим контейнером, и если это так. Если нет, выполните профилирование производительности по вашей проблеме сортировки и выберите другой контейнер на основе данных профиля.

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

Ответ 3

std::list определенно не является хорошим (допустимым) выбором для std::sort(), потому что для std::sort() требуются итераторы с произвольным доступом. std::map и друзья тоже не хороши, потому что позиция элемента не может быть принудительно; то есть позиция элемента на карте не может быть принудительно введена пользователем с вставкой в ​​конкретную позицию или своп. Среди стандартных контейнеров мы доходим до std::vector и std::deque.

std::sort() подобен другим стандартным алгоритмам, поскольку он действует только путем замены значений элементов вокруг (*t = *s). Поэтому даже если список будет магически поддерживать O (1) доступ, ссылки не будут реорганизованы, а их значения будут заменены.

Поскольку std::sort() не изменяет размер контейнера, он не должен влиять на производительность во время выполнения, если вы используете std::vector или std::deque. Примитивные массивы также должны быстро сортироваться, возможно, даже быстрее, чем стандартные контейнеры, но я не ожидаю, что разница в скорости будет достаточно значительной, чтобы оправдать их использование.

Ответ 4

Это зависит от типа элемента.

Если вы просто храните указатели (или POD), тогда вектор будет самым быстрым. Если вы храните объекты, сортировка списка будет быстрее, поскольку она будет заменять узлы, а не физические элементы.

Ответ 5

Алгоритм сортировки ничего не знает о вашем контейнере. Все, что он знает, это итераторы с произвольным доступом. Таким образом, вы можете сортировать вещи, которые даже не находятся в контейнере STL. Итак, как быстро это будет зависеть от итераторов, которые вы ему даете, и как быстро это происходит, чтобы разыменовать и скопировать то, на что они указывают.

std:: sort не будет работать в std:: list, поскольку для сортировки требуются итераторы произвольного доступа. Вы должны использовать один из типов функций std:: list member для этого случая. Эти функции-члены будут эффективно заменять указатели связанных списков вместо копирования элементов.

Ответ 6

Vector.

Всегда используйте вектор по умолчанию. Он имеет минимальные накладные расходы и быстрый доступ к любому другому контейнеру (среди других преимуществ, таких как совместимость с C и итераторы с произвольным доступом).

Теперь спросите себя - что еще вы делаете с контейнером? Вам нужны надежные гарантии исключения? Список, набор и карта, вероятно, будут лучшими параметрами (хотя все они имеют свои собственные процедуры сортировки). Вам нужно регулярно добавлять элементы к передней части контейнера? Рассмотрим deque. Необходимо ли всегда сортировать контейнер? Набор и карта, вероятно, будут лучше подходят.

Наконец, определите, что именно "лучше" для вас, а затем выберите наиболее подходящий контейнер и определите, как он выполняется для ваших нужд.

Ответ 7

Это, безусловно, имеет значение, просто потому, что разные контейнеры имеют разные шаблоны доступа к памяти и т.д., которые могут играть определенную роль.

Однако std::sort не работает на std::list<>::iterators, поскольку это не RandomAccessIterators. Более того, хотя было бы возможно реализовать специализацию для std::list<>, которая перетасовывала указатели узлов, вероятно, имела бы странные и неожиданные семантические последствия - например. если у вас есть итератор внутри отсортированного диапазона в векторе, его значение изменится после сортировки, что не соответствует истине с этой специализацией.

Ответ 8

std:: sort требует итераторов с произвольным доступом, поэтому ваши единственные варианты использования - векторные или deque. Он поменяет значения, и в векторе предположений, вероятно, будет выполняться несколько быстрее, чем deque, потому что он обычно имеет более простую базовую структуру данных. Разница, вероятно, очень незначительна, хотя.

Если вы используете std:: list, существует специализация (std:: list:: sort), которая должна менять указатели, а не значения. Однако, поскольку это не произвольный доступ, он будет использовать mergesort вместо quicksort, что, вероятно, будет означать, что сам алгоритм немного медленнее.

В любом случае, я думаю, что ответ обычно является вектором. Если у вас есть большие классы для каждого элемента, поэтому копирование служебных данных доминирует над процессом сортировки, список может побить его. Или, альтернативно, вы можете хранить указатели на них в векторе и снабжать пользовательский предикат, чтобы отсортировать их соответствующим образом.

Ответ 9

Я полностью согласен с утверждениями, которые ребята разместили выше. Но каков наилучший способ узнать что-то новое? Привет!!!! конечно, не читая текст и не изучая наизусть, но... ПРИМЕРЫ: 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 = С++ 11 file.cpp -o a.out):

массив выделяет 0,958443 МБ
массив сортировки действий занял: 183ms
действие сортировка вектора взял: 316ms
список сортировки действий занял: 725ms
action sort deque взял: 436ms

и с оптимизацией (g++ -O3 --std = С++ 11 file.cpp -o a.out):

массив выделяет 0,958443 МБ
массив сортировки действий занял: 55ms
действие сортировка вектора взял: 57ms
список сортировки действий занял: 264ms
action sort deque взял: 67ms

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

Таким образом, это зависит также от использования оптимизации для компилятора, если нет, мы можем видеть заметную разницу.