algorithm - Как реализовать классические алгоритмы сортировки в современном C++?




sorting c++14 c++-faq (3)

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

Сортировка сортировки

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

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

template<typename ForwardIterator>
void counting_sort(ForwardIterator first, ForwardIterator last)
{
    if (first == last || std::next(first) == last) return;

    auto minmax = std::minmax_element(first, last);  // avoid if possible.
    auto min = *minmax.first;
    auto max = *minmax.second;
    if (min == max) return;

    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
    std::vector<difference_type> counts(max - min + 1, 0);

    for (auto it = first ; it != last ; ++it) {
        ++counts[*it - min];
    }

    for (auto count: counts) {
        first = std::fill_n(first, count, min++);
    }
}

Хотя это полезно только тогда, когда диапазон целых чисел для сортировки известен как маленький (обычно не больше размера сортировки для сортировки), что делает подсчет более родовым, делая его более медленным для своих лучших случаев. Если диапазон известен невелик, вместо spreadsort можно использовать другой алгоритм такой сортировки radix , ska_sort или spreadsort .

Подробности опущены :

  • Мы могли бы пройти границы диапазона значений, принятых алгоритмом, в качестве параметров, чтобы полностью избавиться от первого std::minmax_element через коллекцию. Это сделает алгоритм еще более быстрым, когда известно, что с помощью небольшого диапазона ограничений известно другое. (Это не должно быть точным: передача константы от 0 до 100 по-прежнему намного лучше, чем дополнительный проход над миллионом элементов, чтобы выяснить, что истинные границы от 1 до 95. Стоило бы даже от 0 до 1000; дополнительные элементы записываются один раз с нулем и читаются один раз).

  • Растущий counts на лету» - еще один способ избежать отдельного первого прохода. Удвоение размера counts каждый раз, когда оно должно расти, дает амортизированное время O (1) для отсортированного элемента (см. Анализ затрат на вставку таблицы хеш-таблицы для доказательства того, что экспоненциальный рост является ключевым). Выращивание в конце для нового max легко с помощью std::vector::resize для добавления новых обнуленных элементов. Изменение min на лету и вставка новых обнуленных элементов на передней панели можно выполнить с помощью std::copy_backward после роста вектора. Затем std::fill ноль новыми элементами.

  • Цикл инкремента counts является гистограммой. Если данные, вероятно, будут очень повторяющимися, а количество бункеров невелико, может быть целесообразно развернуть несколько массивов, чтобы уменьшить узкое место для хранения / перезагрузки данных сериализации данных в одном и том же ящике. Это означает, что в начале все больше нуля до нуля, а больше - в конце цикла, но для большинства наших процессоров это стоит того, чтобы на нашем примере миллионы от 0 до 100 чисел, особенно если входные данные уже могут быть (частично) отсортированы и имеют длинные пробежки того же числа.

  • В вышеприведенном алгоритме мы используем проверку min == max для возврата раньше, когда каждый элемент имеет одинаковое значение (в этом случае сортировка коллекции). Фактически, возможно, можно полностью проверить, отсортирована ли коллекция уже при поиске экстремальных значений коллекции без дополнительного времени, потраченного впустую (если первый проход все еще запоминается в узком месте с дополнительной работой по обновлению min и max). Однако такой алгоритм не существует в стандартной библиотеке, и писать было бы более утомительно, чем писать остальную часть подсчета. Он оставлен как упражнение для читателя.

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

  • В то время как современный C ++ классный, будущий C ++ может быть еще более холодным: структурированные привязки и некоторые части диапазонов TS сделают алгоритм еще более чистым.

Алгоритм std::sort (и его кузены std::partial_sort и std::nth_element ) из стандартной библиотеки C ++ в большинстве реализаций представляет собой сложное и гибридное объединение более элементарных алгоритмов сортировки , таких как сортировка сортировки, сортировка вставки, быстрая сортировка , сортировка слияния или сортировка кучи.

Здесь много вопросов и на таких сайтах, как https://codereview.stackexchange.com/ связанных с ошибками, сложностью и другими аспектами реализации этих классических алгоритмов сортировки. Большинство предлагаемых реализаций состоят из необработанных циклов, использования манипуляций с индексами и конкретных типов и, как правило, нетривиальных для анализа с точки зрения правильности и эффективности.

Вопрос : как можно реализовать вышеупомянутые классические алгоритмы сортировки с использованием современного C ++?

  • нет сырых циклов , но сочетания алгоритмических блоков стандартной библиотеки из <algorithm>
  • интерфейс итератора и использование шаблонов вместо манипулирования индексами и конкретных типов
  • C ++ 14 , включая полную стандартную библиотеку, а также синтаксические шумоподавители, такие как auto , псевдонимы шаблонов, прозрачные компараторы и полиморфные лямбды.

Примечания :

  • для дальнейших ссылок на реализации алгоритмов сортировки см. Wikipedia , Rosetta Code или http://www.sorting-algorithms.com/
  • согласно соглашениям Шона Родитель (слайд 39), необработанная петля является for -loop дольше, чем состав двух функций с оператором. Итак, f(g(x)); или f(x); g(x); f(x); g(x); или f(x) + g(x); не являются сырыми петлями, и ни одна из них не является петлями в selection_sort и insertion_sort ниже.
  • Я следую терминологии Скотта Мейерса, чтобы обозначить текущий C ++ 1y уже как C ++ 14, и обозначить C ++ 98 и C ++ 03 как C ++ 98, поэтому не пламените меня для этого.
  • Как было предложено в комментариях @Mehrdad, в конце ответа я представляю четыре реализации в виде Live Пример: C ++ 14, C ++ 11, C ++ 98 и Boost и C ++ 98.
  • Сам ответ представлен только в C ++ 14. Там, где это уместно, я обозначаю различия в синтаксисе и библиотеке, где разные языковые версии различаются.

Алгоритмические строительные блоки

Мы начнем с сборки алгоритмических строительных блоков из стандартной библиотеки:

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next
  • инструменты итератора, такие как non-member std::begin() / std::end() а также с std::next() доступны только с C ++ 11 и более поздних версий. Для C ++ 98 их нужно написать сами. Есть замены из Boost.Range в boost::begin() / boost::end() и от Boost.Utility в boost::next() .
  • алгоритм std::is_sorted доступен только для C ++ 11 и более std::is_sorted . Для C ++ 98 это может быть реализовано в терминах std::adjacent_find и рукописный функциональный объект. Boost.Algorithm также предоставляет boost::algorithm::is_sorted как замену.
  • алгоритм std::is_heap доступен только для C ++ 11 и более std::is_heap .

Синтаксические лакомства

C ++ 14 предоставляет прозрачные компараторы формы std::less<> которые полиморфно действуют на свои аргументы. Это позволяет избежать ввода типа итератора. Это можно использовать в сочетании с аргументами шаблона функции по умолчанию C ++ 11, чтобы создать единую перегрузку для алгоритмов сортировки, которые принимают < как сравнение, и те, которые имеют пользовательский объект функции сравнения.

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

В C ++ 11 можно определить многоразовый шаблонный псевдоним, чтобы извлечь тип значения итератора, который добавляет незначительные помехи в подписи алгоритмов сортировки:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

В C ++ 98 необходимо написать две перегрузки и использовать подробное typename xxx<yyy>::type syntax

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}
  • Другая синтаксическая тонкость заключается в том, что C ++ 14 облегчает перенос пользовательских компараторов через полиморфные лямбдаauto параметрами, которые выводятся как аргументы шаблона функции).
  • C ++ 11 имеет только мономорфные лямбды, которые требуют использования вышеупомянутого псевдонима шаблона value_type_t .
  • В C ++ 98 необходимо либо написать автономный функциональный объект, либо использовать подробный тип синтаксиса std::bind1st / std::bind2nd / std::not1 .
  • Boost.Bind улучшает это с помощью синтаксиса boost::bind и _1 / _2 .
  • C ++ 11 и далее также имеют std::find_if_not , тогда как C ++ 98 требует std::find_if с std::not1 вокруг объекта функции.

Стиль C ++

В настоящее время нет общепринятого стиля C ++ 14. К лучшему или к худшему я внимательно слежу за проектом «Эффективный современный C ++» Скотта Майерса и обновленным GotW от Herb Sutter. Я использую следующие рекомендации стиля:

  • Рекомендация «Почти всегда авто» Херба Саттера и Скотта Мейерса «Предпочитаю авто для конкретных типов» , для которой краткость является непревзойденной, хотя ее ясность иногда disputed .
  • «Distinguish () и {} Скотта Мейерса « при создании объектов » и последовательно выбирают braced-initialization {} вместо старой старой инициализации в скобках () (для того, чтобы перетаскивать все наиболее неприятные-разборные проблемы в общем коде).
  • Скотт Мейерс «Предпочитает псевдоним объявления для typedefs» . Для шаблонов это все равно, и использование его везде, а не typedef экономит время и добавляет согласованность.
  • Я использую шаблон for (auto it = first; it != last; ++it) в некоторых местах, чтобы разрешить проверку инвариантности цикла для уже отсортированных поддиапазонов. В производственном коде использование while (first != last) и ++first где-то внутри цикла может быть немного лучше.

Выбор сортировки

Сортировка сортировки никак не адаптируется к данным, поэтому ее время выполнения всегда равно O(N²) . Однако сортировка выбора имеет свойство минимизировать количество свопов . В приложениях, где стоимость подкачки элементов высока, выбор сортировки очень хорошо может быть алгоритмом выбора.

Чтобы реализовать его с использованием стандартной библиотеки, повторно используйте std::min_element чтобы найти оставшийся минимальный элемент, и iter_swap чтобы заменить его на место:

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Обратите внимание, что selection_sort имеет уже обработанный диапазон [first, it) отсортированный как его инвариант цикла. Минимальные требования - это итераторы вперед , по сравнению с итераторами произвольного доступа std::sort .

Подробности опущены :

  • сортировка выбора может быть оптимизирована с ранним тестом, if (std::distance(first, last) <= 1) return; (или для форвардных / двунаправленных итераторов: if (first == last || std::next(first) == last) return; ).
  • для двунаправленных итераторов вышеуказанный тест можно комбинировать с циклом над интервалом [first, std::prev(last)) , поскольку последний элемент гарантированно является минимальным оставшимся элементом и не требует свопа.

Сортировка вставки

Хотя это один из элементарных алгоритмов сортировки с наихудшим временем O(N²) , сортировка вставки - это алгоритм выбора, когда данные почти отсортированы (поскольку они адаптивны ) или когда размер проблемы мал (поскольку он имеет низкие накладные расходы). По этим причинам, а также потому, что он также стабилен , сортировка вставки часто используется в качестве рекурсивного базового случая (когда размер проблемы мал) для более сложных алгоритмов сортировки по делению и побегу, таких как сортировка слияния или быстрая сортировка.

Чтобы внедрить insertion_sort со стандартной библиотекой, повторно используйте std::upper_bound чтобы найти место, куда должен идти текущий элемент, и используйте std::rotate чтобы сдвинуть оставшиеся элементы вверх во входном диапазоне:

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Обратите внимание, что insertion_sort имеет уже обработанный диапазон [first, it) отсортированный как его инвариант цикла. Сортировка вставки также работает с итераторами вперед.

Подробности опущены :

  • сортировка вставки может быть оптимизирована с ранним тестом, if (std::distance(first, last) <= 1) return; (или для форвардных / двунаправленных итераторов: if (first == last || std::next(first) == last) return; ) и цикл по интервалу [std::next(first), last) , потому что первый элемент гарантированно находится на месте и не требует поворота.
  • для двунаправленных итераторов двоичный поиск для поиска точки вставки можно заменить на обратный линейный поиск с использованием стандартного алгоритма std::find_if_not стандартной библиотеки.

Четыре живых примера ( C++14 , C++11 , C ++ 98 и Boost , C++98 ) для фрагмента ниже:

using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first), 
    [=](auto const& elem){ return cmp(*it, elem); }
).base();
  • Для случайных входов это дает сравнение O(N²) , но это улучшает сравнение O(N) для почти отсортированных входов. В двоичном поиске всегда используются сравнения O(N log N) .
  • Для небольших диапазонов ввода лучшая локальность памяти (кеш, предварительная выборка) линейного поиска также может доминировать в двоичном поиске (конечно, это нужно проверить).

Быстрая сортировка

При тщательном внедрении быстрый сортировка является надежной и имеет ожидаемую сложность O(N log N) , но с наихудшей сложностью O(N²) которая может быть инициирована с использованием смежных входных данных. Когда стабильный вид не нужен, быстрый сортировка - отличный вид общего назначения.

Даже для самых простых версий быстрый сорт довольно сложнее реализовать с использованием стандартной библиотеки, чем другие классические алгоритмы сортировки. Подход ниже использует несколько итератора утилиты , чтобы найти средний элемент входного диапазона [first, last) в качестве шарнира, а затем использовать два вызова std::partition (которые O(N) ) , чтобы трехходовой разделить на вход диапазон в сегменты элементов, которые меньше, равны и больше, чем выбранные опорные точки, соответственно. Наконец, рекурсивно отсортированы два внешних сегмента с элементами, меньшими и большими, чем ось поворота:

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

Однако быстрый сортировка довольно сложная, чтобы получить правильную и эффективную работу, так как каждый из вышеуказанных шагов должен быть тщательно проверен и оптимизирован для кода уровня производства. В частности, для сложности O(N log N) свод должен приводить к сбалансированному разделению входных данных, который вообще не может быть гарантирован для оси O(1) , но который может быть гарантирован, если задавать опорную точку как O(N) медиана входного диапазона.

Подробности опущены :

  • вышеприведенная реализация особенно уязвима для специальных материалов, например, она имеет сложность O(N^2) для ввода « органных труб » 1, 2, 3, ..., N/2, ... 3, 2, 1 ( потому что середина всегда больше всех остальных элементов).
  • median-of-3 выбор median-of-3 из случайно выбранных элементов из входных диапазонов защиты от почти отсортированных входов, для которых сложность иначе ухудшилась бы до O(N^2) .
  • 3-стороннее разбиение (разделение элементов меньше, чем равное и большее, чем точка поворота), как показано двумя вызовами std::partition , не является наиболее эффективным алгоритмом O(N) для достижения этого результата.
  • для итераторов с произвольным доступом гарантированная сложность O(N log N) может быть достигнута посредством медианного выбора с помощью std::nth_element(first, middle, last) , а затем рекурсивных вызовов quick_sort(first, middle, cmp) и quick_sort(middle, last, cmp) .
  • эта гарантия приходит за счет, однако, поскольку постоянный коэффициент сложности O(N) std::nth_element может быть более дорогим, чем коэффициент сложности O(1) std::nth_element 3-го поворота, за которым следует O(N) вызывает std::partition (который является независимым от кэширования одним переходом по данным).

Сортировка слиянием

Если использование O(N) дополнительного пространства не вызывает беспокойства, то сортировка слияния является отличным выбором: это единственный стабильный алгоритм сортировки O(N log N) .

Это просто реализовать с помощью стандартных алгоритмов: используйте несколько утилит итератора, чтобы найти середину диапазона ввода [first, last) и объединить два рекурсивно отсортированных сегмента с помощью std::inplace_merge :

template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;                   
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

Для сортировки Merge требуются двунаправленные итераторы, узким местом является std::inplace_merge . Обратите внимание, что при сортировке связанных списков сортировка слияния требует только O(log N) дополнительного пространства (для рекурсии). Последний алгоритм реализуется методом std::list<T>::sort в стандартной библиотеке.

Куча сортировки

Сорт Heap прост для реализации, выполняет сортировку O(N log N) на месте, но не является стабильной.

Первый цикл, O(N) «heapify», ставит массив в порядок кучи. Второй цикл, этап «сортировки» O(N log N ), многократно извлекает максимум и восстанавливает порядок кучи. Стандартная библиотека делает это чрезвычайно простым:

template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
    lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

Если вы считаете, что это «обман» для использования std::make_heap и std::sort_heap , вы можете пойти на один уровень глубже и написать эти функции самостоятельно в терминах std::push_heap и std::pop_heap , соответственно:

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp); 
        assert(std::is_heap(first, it, cmp));           
    }
}

template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));           
    } 
}

}   // namespace lib

Стандартная библиотека определяет как push_heap и pop_heap как сложность O(log N) . Обратите внимание, однако, что внешний цикл в диапазоне [first, last) приводит к сложности O(N log N) для make_heap , тогда как std::make_heap имеет только сложность O(N) . Для общей сложности O(N log N) heap_sort это не имеет значения.

Подробности опущены : O(N) реализация make_heap

тестирование

Вот четыре примера Live ( C++14 , C++11 , C ++ 98 и Boost , C++98 ), которые тестируют все пять алгоритмов на разных входах (не должны быть исчерпывающими или строгими). Просто обратите внимание на огромные различия в LOC: C ++ 11 / C ++ 14 требуется около 130 LOC, C ++ 98 и Boost 190 (+ 50%) и C ++ 98 более 270 (+ 100%).


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

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

Абстрактная машина в спецификации C ++ 98 / C ++ 03 принципиально однопоточная. Таким образом, невозможно написать многопоточный код C ++, который полностью переносится по спецификации. Спецификация даже не говорит ничего об атомарности загрузок и хранилищ памяти или о порядке загрузки и хранения данных, не говоря уже о таких вещах, как мьютексы.

Конечно, вы можете написать многопоточный код на практике для конкретных конкретных систем - например, pthreads или Windows. Но нет стандартного способа написания многопоточного кода для C ++ 98 / C ++ 03.

Абстрактная машина в C ++ 11 имеет многопоточность по дизайну. Он также имеет хорошо определенную модель памяти ; то есть он говорит, что компилятор может и не может делать, когда дело доходит до доступа к памяти.

Рассмотрим следующий пример, при котором пару глобальных переменных обращаются одновременно двумя потоками:

           Global
           int x, y;

Thread 1            Thread 2
x = 17;             cout << y << " ";
y = 37;             cout << x << endl;

Что могло бы вывести Thread 2?

В C ++ 98 / C ++ 03 это даже не неопределенное поведение; сам вопрос бессмыслен, поскольку стандарт не рассматривает ничего, называемое «нитью».

В C ++ 11 результатом является Undefined Behavior, потому что нагрузки и магазины не обязательно должны быть атомарными вообще. Что может показаться не очень хорошим улучшением ... И само по себе это не так.

Но с C ++ 11 вы можете написать это:

           Global
           atomic<int> x, y;

Thread 1                 Thread 2
x.store(17);             cout << y.load() << " ";
y.store(37);             cout << x.load() << endl;

Теперь все становится намного интереснее. Прежде всего, здесь определяется поведение. Thread 2 теперь может печатать 0 0 (если он работает до Thread 1), 37 17 (если он выполняется после Thread 1) или 0 17 (если он запускается после того, как Thread 1 назначает x, но до того, как он назначит y).

То, что он не может напечатать, равен 37 0 , потому что режим по умолчанию для атомных нагрузок / хранилищ в C ++ 11 заключается в обеспечении последовательной согласованности . Это означает, что все нагрузки и хранилища должны быть «как если бы», они произошли в том порядке, в котором вы их записывали в каждом потоке, тогда как операции между потоками могут чередоваться, но система нравится. Таким образом, поведение Atomics по умолчанию обеспечивает как атомарность, так и порядок загрузки и хранения.

Теперь, на современном процессоре, обеспечение последовательной согласованности может быть дорогостоящим. В частности, компилятор, вероятно, испускает полномасштабные барьеры памяти между каждым доступом здесь. Но если ваш алгоритм может терпеть неуправляемые нагрузки и магазины; т.е. если он требует атомарности, но не упорядочивает; т.е. если он может вынести 37 0 качестве выхода из этой программы, тогда вы можете написать это:

           Global
           atomic<int> x, y;

Thread 1                            Thread 2
x.store(17,memory_order_relaxed);   cout << y.load(memory_order_relaxed) << " ";
y.store(37,memory_order_relaxed);   cout << x.load(memory_order_relaxed) << endl;

Чем более современный процессор, тем более вероятно, что это будет быстрее, чем предыдущий пример.

Наконец, если вам просто нужно сохранить определенные нагрузки и магазины в порядке, вы можете написать:

           Global
           atomic<int> x, y;

Thread 1                            Thread 2
x.store(17,memory_order_release);   cout << y.load(memory_order_acquire) << " ";
y.store(37,memory_order_release);   cout << x.load(memory_order_acquire) << endl;

Это возвращает нас к упорядоченным нагрузкам и магазинам - поэтому 37 0 больше не является возможным выходом, но он делает это с минимальными накладными расходами. (В этом тривиальном примере результат такой же, как полномасштабная последовательная согласованность, в более крупной программе этого не будет).

Конечно, если только выходы, которые вы хотите увидеть, 0 0 или 37 17 , вы можете просто обернуть мьютексом вокруг исходного кода. Но если вы зачитали это далеко, я уверен, вы уже знаете, как это работает, и этот ответ уже дольше, чем я предполагал :-).

Итак, нижняя строка. Мьютексы велики, и C ++ 11 их стандартизирует. Но иногда по соображениям производительности вам нужны примитивы нижнего уровня (например, классический шаблон с двойной проверкой блокировки ). Новый стандарт обеспечивает высокоуровневые гаджеты, такие как мьютексы и переменные состояния, а также предоставляет низкоуровневые гаджеты, такие как атомные типы и различные варианты защиты памяти. Итак, теперь вы можете писать сложные, высокопроизводительные параллельные подпрограммы полностью на языке, указанном стандартом, и вы можете быть уверены, что ваш код будет компилироваться и работать без изменений как на сегодняшних системах, так и на завтрашнем.

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

Подробнее об этом см. В этом сообщении в блоге .





c++ algorithm sorting c++14 c++-faq