Std sort c как работает

Std::sort

Std::sort это алгоритм сортировки, один из представителей семейства алгоритмов stl. Как понятно из его названия, std::sort занимается сортировкой данных. Кстати, std::sort часто (или почти всегда?) опережает по скорости стандартную функцию sort(). Вообще, в STL очень много полезных алгоритмов и sort – один из наиболее часто используемых. Давайте рассмотрим на примере std::sort() использование алгоритмов STL и разберём, где именно и как именно надо использовать алгоритмы, а так же как мы можем модифицировать их поведение с помощью функторов.

Алгоритм std::sort

Как и большинство алгоритмов STL, sort определён в двух формах:

Первая форма алгоритма использует дефолтный функтор сравнения, а вторая позволяет задать его самостоятельно. Выполним простую сортировку массива:

std::sort через функцию

Сортировка с использованием нашей собственной функции сравнения элементов в контейнере:

std::sort + функтор

А вот использование функтора:

std::sort и сортировка объектов

Как же с помощью алгоритма sort можно отсортировать контейнер с объектами? Да, собственно, практически так же – меняется мало что. Давайте предположим, что у нас есть класс и контейнер с объектами этого класса:

Вот так мы можем отсортировать объекты в этом массиве по их расположению вдоль оси Х:

Сортировка того же самого набора объектов, но уже по массе:

И, конечно же, ничего не мешает Вам написать более сложные функции сортировки. Например, сделать функтор, который будет сортировать объекты по массе, а объекты с равной массой будут сортироваться по Х-координате:

Как-то так. Если есть вопросы – задавайте.

Во. Классная штука. Спасибо за урок.

в структуре
struct sort_class_mass_pos

вас не смущает вот эта строка?
if (i.m_fMass==j.m_fMass)

Кстати, std::sort часто (или почти всегда?) опережает по скорости стандартную функцию sort()

А зачем вообще нужен функтор, с затратами на конструктор/деструктор/хранение, если можно задать функцию?

Функтор совсем не обязательно должен иметь тяжеловсные конструктор и деструктор (а если они будут пустые – то и затраты будут вообще нулевые). А главное его приемущество состоит в том, что он зачастую может работать быстрее. Что происходит, например, когда мы вызывает qsort? Плюсы для каждых двух сравниваемых заничений помещают их в стек и вызывают указанную нами функцию сортировки (что достаточно медленно). Когда же мы используем функтор – часто (не всегда, но как правило) компилятор понимает чего мы от него хотим (а хотим мы максимально зианлайнить всё) и оптимизирует соответсвующим образом. Как итог – обычно получаем заметный буст (прирост скорости т.е.).

При этом обычно стоит так же (в статье это не указано, но это так) делать функцию сравнения константной, а сами сравниваемые переменные, если это не POD-типы, а какие-то отсносительно сложные данные, передавать как константные ссылки – это поможет компилятору лучше сообразить что от него требуется.

Вы можете сами сравнить производительность – например, напишите сортировку относительного большого массива (несколько миллионов интов, например) обычным qsort и второй вариант через std::sort и засеките время работы в том и другом случае – разница будет весьма существенной.

std:: sort

Sorts the elements in the range [first, last) in non-descending order. The order of equal elements is not guaranteed to be preserved.

A sequence is sorted with respect to a comparator comp if for any iterator it pointing to the sequence and any non-negative integer n such that it + n is a valid iterator pointing to an element of the sequence, comp ( * ( it + n ) , * it ) (or * ( it + n ) < * it ) evaluates to false .

Contents

[edit] Parameters

The signature of the comparison function should be equivalent to the following:

bool cmp ( const Type1 & a, const Type2 & b ) ;

While the signature does not need to have const & , the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1& is not allowed , nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11) ).
The types Type1 and Type2 must be such that an object of type RandomIt can be dereferenced and then implicitly converted to both of them. ​

[edit] Return value

[edit] Complexity

O(N·log(N)) , where N = std:: distance ( first, last ) comparisons on average.

O(N·log(N)) , where N = std:: distance ( first, last ) comparisons.

[edit] Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

Под капотом сортировок в STL

Стандарт С++ почти никогда не указывает, как именно должен быть реализован тот или иной std алгоритм. Дается только описание того, что на входе, что на выходе и асимптотические ограничения по времени работы и памяти. В статье я постарался прикинуть, какие математические алгоритмы и структуры данных имели ввиду авторы стандарта, указывая ограничения для той или иной сортировки и для некоторых других алгоритмов. А так же как эти алгоритмы реализованы на практике.

При написании статьи я использовал стандарт C++17. В качестве реализаций рассматривал GCC 10.1.0 (май 2020) и LLVM/Clang 10.0.0 (март 2020). В каждой и них есть своя реализация STL, а значит и std алгоритмов.

1. Однопоточные реализации

1.1. Готовые сортировки

• std::sort(). Еще в стандарте C++98/C++03 мы видим, что сложность алгоритма примерно n*log(n) сравнений. А также есть примечание, что если важна сложность в худшем случае, то следует использовать std::stable_sort() или std::partial_sort() . Похоже, что в качестве реализации std::sort() подразумевался quicksort (в худшем случае O(n 2 ) сравнений). Однако, начиная с C++11 мы видим, что сложность std::sort() уже O(n*log(n)) сравнений безо всяких оговорок. GCC реализует предложенную в 1997 году introsort (O(n*log(n)) сравнений, как в среднем, так и в худшем случае). Introsort сначала сортирует как quicksort, но вскоре переключается на heapsort и в самом конце сортировки, когда остаются небольшие интервалы (в случае GCC менее 16 элементов), сортирует их при помощи insertion sort. А вот LLVM реализует весьма сложный алгоритм с множеством оптимизаций в зависимости от размеров сортируемых интервалов и того, являются ли сортируемые элементы тривиально копируемыми и тривиально конструируемыми.
• std::partial_sort(). Поиск некоторого числа элементов с минимальным значением из множества элементов и их сортировка. Во всех версиях стандарта сложность примерно n*log(m) сравнений, где n — количество элементов в контейнере, а m — количество минимальных элементов, которое нужно найти. Задача для heapsort. Сложность в точности совпадает с этим алгоритмом. Так и реализовано в LLVM и GCC.
• std::stable_sort(). Тут немного сложнее. Во-первых, в отличии от предыдущих сортировок в стандарте отмечено, что она стабильная. Т.е. не меняет местами эквивалентные элементы при сортировке. Во-вторых, сложность ее в худшем случае n*(log(n)) 2 сравнений. Но если достаточно памяти, то должно быть n*log(n) сравнений. Т.е. имеется ввиду 2 разных алгоритма стабильной сортировки. В варианте, когда памяти много подходит стандартный merge sort. Как раз ему требуется дополнительная память для работы. Сделать merge sort без дополнительной памяти за O(n*log(n)) сравнений так же возможно. Но это сложный алгоритм и не смотря на асимптотику n*log(n) сравнений константа у него велика, и в обычных условиях он будет работать не очень быстро. Поэтому обычно используется вариант merge sort без дополнительной памяти, который имеет асимптотику n*(log(n)) 2 сравнений. И в GCC и в LLVM реализации в целом похожи. Реализованы оба алгоритма: один работает при наличии памяти, другой — когда памяти не хватает. Обе реализации, когда дело доходит до небольших интервалов, используют insertion sort. Она стабильная и не требует дополнительной памяти. Но ее сложность O (n 2 ) сравнений, что не играет роли на маленьких интервалах.
• std::list::sort(), std::forward_list::sort(). Все перечисленные выше сортировки требуют итераторы произвольного доступа для задания сортируемого интервала. А что если требуется отсортировать контейнер, который не обеспечивает таких итераторов? Например, std::list или std::forward_list . У этих контейнеров есть специальный метод sort() . Согласно стандарту, он должен обеспечить стабильную сортировку за примерно n*log(n) сравнений, где n число элементов контейнера. В целом вполне подходит merge sort. Ее и реализуют GCC и LLVM и для std::list::sort() , и для std::forward_list::sort() . Но зачем вообще потребовались частные реализации сортировки для списков? Почему бы для std::stable_sort() просто не ослабить итераторы до однонаправленных или хотя бы двунаправленных, чтоб этот алгоритм можно было применять и к спискам? Дело в том, что в std::stable_sort() используются оптимизации, которые требуют итераторы произвольного доступа. Например, как я писал выше, когда дело доходит до сортировки небольших интервалов в std::stable_sort() разумно переключиться на insertion sort, а эта сортировка требует итераторы произвольного доступа.
• std::make_heap(), std::sort_heap(). Алгоритмы по работе с кучей (max heap), включая сортировку. std::sort_heap() это единственный способ сортировки, алгоритм для которого указан явно. Сортировка должна быть реализована, как heapsort. Так и реализовано в LLVM и GCC.

Сводная таблица

Примечание. В качестве реализации в GCC и LLVM указан алгоритм, который используется для больших сортируемых интервалов. Для особых случаев (небольшие интервалы и т.п.) часто используются оптимизации.

1.2. Составляющие алгоритмов сортировки

• std::merge(). Слияние двух сортированных интервалов. Этот алгоритм не меняет местами эквивалентные элементы, т.е. он стабильный. Количество сравнений не более, чем сумма длин сливаемых интервалов минус 1. На базе данного алгоритма очень просто реализовать merge sort. Однако напрямую этот алгоритм не используется в std::stable_sort() ни LLVM, ни в GCC. Для шага слияния в std::stable_sort() написаны отдельные реализации.
• std::inplace_merge(). Этот алгоритм также реализует слияние двух сортированных интервалов и он также стабильный. У него есть интерфейсные отличия от std::merge() , но кроме них есть еще одно, очень важное. По сути std::inplace_merge() это два алгоритма. Один вызывается при наличии достаточного количества дополнительной памяти. Его сложность, как и в случае std::merge() , не более чем сумма длин объединяемых интервалов минус 1. А другой, если дополнительной памяти нет и нужно сделать слияние «in place». Сложность этого «in place» алгоритма n*log(n) сравнений, где n сумма элементов в сливаемых интервалах. Все это очень напоминает std::stable_sort() , и это неспроста. Как кажется, авторы стандарта предполагали использование std::inplace_merge() или подобных алгоритмов в std::stable_sort() . Эту идею отражают реализации. В LLVM для реализации std::stable_sort() используется std::inplace_merge() , в GCC для реализаций std::stable_sort() и std::inplace_merge() используются некоторые общие методы.
• std::partition()/std::stable_partition(). Данные алгоритмы также можно использовать для написания сортировок. Например, для quicksort или introsort. Но ни GCC ни LLVM не использует их напрямую для реализации сортировок. Используются аналогичные им, но оптимизированные, для случая конкретной сортировки, варианты реализации.

2. Многопоточные реализации

В C++17 для многих алгоритмов появилась возможность задавать политику исполнения (ExecutionPolicy). Она обычно указывается первым параметром алгоритма. Алгоритмы сортировок не стали исключением. Политику исполнения можно задать для большинства алгоритмов рассмотренных выше. В том числе и указать, что алгоритм может выполняться в несколько потоков ( std::execution::par , std::execution::par_unseq ). Это значит, что именно может, а не обязан. А будет вычисляться в несколько потоков или нет зависит от целевой платформы, реализации и варианта сборки компилятора. Асимптотическая сложность также остается неизменной, однако константа может оказаться меньше за счет использования многих потоков.

Тут ключевое слово «может». Дело в том, что однопоточные реализации, описанные выше, подходят для соответствующих алгоритмов, какая бы политика исполнения ни была задана. И однопоточные реализации часто используются на настоящий момент независимо от политики исполнения. Я рассмотрел следующие версии:

• LLVM/Clang (Apple clang version 11.0.3 (clang-1103.0.32.62)) и MacOS 10.15.4. В этом случае заголовочный файл execution не нашелся. Т.е. политику многопоточности задать не получится;
• LLVM/Clang 10.0.0 сборка из brew. Тот же результат, что и в случае Apple clang;
• GCC 10.1.0 — файл execution есть и политику задать можно. Но какая бы политика ни была задана, использоваться будет однопоточная версия. Для вызова многопоточной версии необходимо, чтобы был подключен файл tbb/tbb.h при компиляции на платформе Intel. А для этого должна быть установлена библиотека Intel Threading Building Blocks (TBB) и пути поиска заголовочных файлов были прописаны. Установлен ли TBB проверяется при помощи специальной команды в gcc: __has_include(<tbb/tbb.h>) в файле c++config.h. И если данный файл виден, то используется многопоточная версия написанная на базе Threading Building Blocks, а если нет, то последовательная. Про TBB немного подробнее ниже. Дополнительную информацию о поддержке компилятором параллельных вычислений, как впрочем и другой функциональности, можно посмотреть на cppreference.com.

3. Intel Threading Building Blocks

Чтоб стало возможным использовать многопоточные версии разных алгоритмов, на сегодня нужно использовать дополнительные библиотеку Threading Building Blocks, разрабатываемую Intel. Это несложно:

• Клонируем репозиторий Threading Building Blocks с https://github.com/oneapi-src/oneTBB
• Из корня запускаем make и ждем несколько минут пока компилируется TBB или make all и ждем пару часов, чтоб прошли еще и тесты
• Далее при компиляции указываем пути к includes ( -I oneTBB/include ) и к динамической библиотеке (у меня был такой путь -L tbb/oneTBB/build/macos_intel64_clang_cc11.0.3_os10.15.4_release -ltbb , т.к. я собирал TBB при помощи Apple clang version 11.0.3 на MacOS)

4. Эпилог

Как кажется, когда комитет C++ описывает те или иные особенности языка в стандарте, он предполагает те или иные сценарии использования и те или иные алгоритмы реализации. Часто все развивается, как предполагалось. Иногда идет своим путем. Иногда не используется вовсе. Какие бы ни были реализации тех или иных алгоритмов или структур данных сегодня, завтра это может измениться. Измениться впрочем может и стандарт. Но меняясь, стандарт почти всегда обеспечивает совместимость с ранее написанным кодом. При выпуске новых версий компиляторов могут меняться и реализации. Но изменяясь они предполагают, что разработчики полагаются на стандарт. На мой взгляд, имеет смысл понимать, как обычно реализуются те или иные части стандартной библиотеки. Но полагаться при разработке нужно именно на ограничения, заданные стандартом.

# Sorting

std::sort , found in the standard library header algorithm , is a standard library algorithm for sorting a range of values, defined by a pair of iterators. std::sort takes as the last parameter a functor used to compare two values; this is how it determines the order. Note that std::sort is not stable

The comparison function must impose a Strict, Weak Ordering

(opens new window) on the elements. A simple less-than (or greater-than) comparison will suffice.

A container with random-access iterators can be sorted using the std::sort algorithm:

std::sort requires that its iterators are random access iterators. The sequence containers std::list and std::forward_list (requiring C++11) do not provide random access iterators, so they cannot be used with std::sort . However, they do have sort member functions which implement a sorting algorithm that works with their own iterator types.

Their member sort functions always sort the entire list, so they cannot sort a sub-range of elements. However, since list and forward_list have fast splicing operations, you could extract the elements to be sorted from the list, sort them, then stuff them back where they were quite efficiently like this:

# Sorting sequence containers with specifed ordering

If the values in a container have certain operators already overloaded, std::sort can be used with specialized functors to sort in either ascending or descending order:

In C++14, we don’t need to provide the template argument for the comparison function objects and instead let the object deduce based on what it gets passed in:

# Sorting sequence containers by overloaded less operator

If no ordering function is passed, std::sort will order the elements by calling operator< on pairs of elements, which must return a type contextually convertible to bool (or just bool ). Basic types (integers, floats, pointers etc) have already build in comparison operators.

We can overload this operator to make the default sort call work on user-defined types.

# Sorting sequence containers using compare function

# Sorting sequence containers using lambda expressions (C++11)

# sorting with std::map (ascending and descending)

This example sorts elements in ascending order of a key using a map. You can use any type, including class, instead of std::string , in the example below.

If entries with equal keys are possible, use multimap instead of map (like in the following example).

To sort elements in descending manner, declare the map with a proper comparison functor ( std::greater<> ):

# Sorting built-in arrays

The sort algorithm sorts a sequence defined by two iterators. This is enough to sort a built-in (also known as c-style) array.

Prior to C++11, end of array had to be "calculated" using the size of the array: