Function template adaptive_merge . Boost , The Boost C++ Libraries BoostBook Documentation Subset , Reference

Function template adaptive_merge

boost::movelib::adaptive_merge

Synopsis

// In header: <boost/move/algo/adaptive_merge.hpp>

template<typename RandIt, typename Compare> 
  void adaptive_merge(RandIt first, RandIt middle, RandIt last, Compare comp, 
                      typename iterator_traits< RandIt >::value_type * uninitialized = 0, 
                      std::size_t uninitialized_len = 0);

Description

Эффект: Слияние двух последовательных отсортированных диапазонов [первый, средний) и [средний, последний] в один отсортированный диапазон [первый, последний] в соответствии с данной функцией сравнения. Алгоритм стабилен (если в исходных двух диапазонах присутствуют эквивалентные элементы, то элементы из первого диапазона (сохранение их исходного порядка) предшествуют элементам из второго диапазона (сохранение их исходного порядка).

Требуется:

Рэнд Он должен соответствовать требованиям ValueSwappable и RandomAccessIterator.
Тип RandIt должен соответствовать требованиям MoveAssignable и MoveConstructible.

Параметры:

Первый: начало первого отсортированного диапазона.
середина: конец первого отсортированного диапазона и начало второго
последний: конец второго отсортированного диапазона
Comp: объект функции сравнения, который возвращается истинным, если первый аргумент упорядочен перед вторым.
uninitialized, uninitialized_len: сырое хранилище, начинающееся на «uninitialized», способное удерживать элементы «uninitialized_len» типа iterator_traits::value_type. Максимальная производительность достигается, когда uninitialized_len является min (std::distance (первый, средний), std::distance (средний, последний)).

Бросает: Если комп бросает или двигает конструктор, переместить назначение или своп типа отменяемого RandIt бросает.

Сложность: Всегда K x O(N) сравнения и перемещения заданий/конструкторов/свопов. Постоянный фактор для сравнений и движения данных минимизируется, когда uninitialized_len является min (std::distance (первый, средний), std::distance (средний, последний)). Довольно хорошая производительность достигается, когда uninitialized_len является ceil(sqrt(std::distance(first, last)))*2.

Осторожно: Экспериментальная реализация, не готовая к производству.

Статья Function template adaptive_merge раздела The Boost C++ Libraries BoostBook Documentation Subset Reference может быть полезна для разработчиков на c++ и boost.