BykoIanko Oct 8 2020 at 16:23

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

7 min

21K

VK corporate blogProgramming*C++*Algorithms*

+42

Comments 17

Orient Oct 8 2020 at 17:00

Жаль, что политика управления выделением доп. памяти в алгоритмах не предоставляется. Например, мне не хотелось бы, чтобы память выделялась и освобождалась в цикле, в котором вызвается std::inplace_merge. Также не хватает возможности указать аллокатор.

BykoIanko Oct 8 2020 at 18:04

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

Antervis Oct 9 2020 at 00:42

А что если требуется отсортировать контейнер, который не обеспечивает таких итераторов?… Но зачем вообще потребовались частные реализации сортировки для списков?

попахивает амнезией )

Как кажется, когда комитет C++ описывает те или иные особенности языка в стандарте, он предполагает те или иные сценарии использования и те или иные алгоритмы реализации

ну касательно sort требования кажутся достаточно логичными и простыми — он требует самую лучшую ассимптотику но стандарт не ограничивает компилятор в выборе алгоритма, удовлетворяющего этой ассимптотике. И так во всём — стандарт пытается дать побольше гарантий, не ущемляя компиляторы в быстродействии.

Orient Oct 9 2020 at 10:14

попахивает амнезией )
На самом деле std::list::sort при обмене элементов местами не имеет дело с самими значениями, а изменяет указатели во внутренних структурах. Заставить std::stable_sort делать то же самое вряд ли возможно.

BykoIanko Oct 9 2020 at 10:22

На самом деле std::list::sort при обмене элементов местами не имеет дело с самими значениями, а изменяет указатели во внутренних структурах.

Интересно. Ни когда не задумывался об этом в таком ключе. Но видимо так и устроено. Так было бы логично.

Orient Oct 9 2020 at 13:56

https://wandbox.org/permlink/J3BGcM60Ux83ezxF вектор или дек не работают с такими типами.

BykoIanko Oct 9 2020 at 17:15

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

Aldrog Oct 9 2020 at 14:52

Для вызова многопоточной версии необходимо, чтобы был подключен файл tbb/tbb.h при компиляции на платформе Intel.

Что подразумевается под платформой Intel? TBB работает независимо от производителя CPU и даже архитектуры (по крайней мере на ARM точно всё работает как надо).

Кстати, в большинстве дистрибутивов Linux для него есть предсобранные пакеты.

Orient Oct 9 2020 at 15:12

Может быть имеется ввиду использование libstdc++ совместно с icc?

Aldrog Oct 9 2020 at 16:15

Я сам не проверял, но в статье речь идёт о GCC, а не отдельно libstdc++, да и здесь эта фича тестируется с g++ из GCC 9.1, а не icc.

BykoIanko Oct 9 2020 at 17:31

Aldrog спасибо за комментарий!

> Что подразумевается под платформой Intel?

Я полагал, что Intel пишет TBB для своих процессоров. Intel x86, вероятно эта штука будет корректно работать и для AMDx86. Это то, что я имел ввиду.

Но что вы правы. У TBB список совместимости шире, чем я думал. software.intel.com/content/www/ru/ru/develop/tools/threading-building-blocks.html

> Кстати, в большинстве дистрибутивов Linux для него есть предсобранные пакеты.

Вероятно, тогда там и с реализацией ExecutionPolicy может быть получше. Для мака пришлось собирать.

PyerK Oct 9 2020 at 16:12

Ещё есть алгоритм который сортирует лишь 1 элемент из коллекции: std::nth_element.

Orient Oct 9 2020 at 17:36

Потенциально он переупорядочивает все элементы последовательности. Для n-ного элемента последовательность становится std::is_partitioned.

BykoIanko Oct 9 2020 at 17:37

Да, он был бы уместен в статье. Пишут, что он обычно использует вот такой алгоритм: en.wikipedia.org/wiki/Introselect
Вероятно, добавлю его в статью.

Спасибо!

d1gital_love Feb 17 2022 at 09:29

В идеале пригодились бы ссылки на исходники и документацию в колонке "Реализация в ...".

Ictiss Mar 31 2022 at 08:21

Подскажите пожалуйста как складывать временные сложности алгоритмов. Например в программе используется 2 алгоритма оба по O(log n) (сортируем массив за O(log n) и делаем поиск за O(log n)). Как вычислить общую сложность программы. O(log n) + O(log n) =? Это будет O(log 2n)?

-1

BykoIanko Mar 31 2022 at 08:27

O-большое, это с точность до константы, на которую умножается асимптотически заданное кол-ва операций (или кол-во какого-то другого ресурса. Памяти, например). Если в программе используются последовательно 2 алгоритма сложностью O(log n), то в итоге получим сложность O(log n). Так же замечу, что в общем случае сортировать массив за O(log n) не выйдет. Скорее это выйдет за O(n log n).