Алгоритм для нахождения преобладающего элемента в последовательности

[apolukhin]

Перенос предложения: голоса +10, -1 Автор идеи: progzdeveloper

Предлагается добавить в STL реализацию алгоритма для нахождения преобладающего элемента в последовательности.

Под преобладающим элементом подразумевается элемент который встречается больше n/2 раз в массиве длины n. Поиск может быть выполнен за линейное время с использованием O(1) памяти.

Этот алгоритм хорошо известен и имеет широкое применение.

Сигнатуры функций, реализующих алгоритм, могут выглядеть так:

template <class _FwdIt>
_FwdIt majority_element(_FwdIt begin, _FwdIt end);

template <class _FwdIt, class _Comp>
_FwdIt majority_element(_FwdIt begin, _FwdIt end, _Comp comp);

Тип _FwdIt должен удовлетворять концепту forward-only итератора. Функции должны принимать диапазон [first, last), и возвращать итератор, указывающий на преобладающий элемент, если таковой имеется, иначе - last. Второй вариант функции принимает пользовательский функтор сравнения элементов, как это принято в STL.

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

template <class _FwdIt, class _Value>
bool is_majority_element(_FwdIt begin, _FwdIt end, const _Value& x);

template <class _FwdIt, class _Value, class _Comp>
bool is_majority_element(_FwdIt begin, _FwdIt end, const _Value& x, _Comp comp);

В целом семантика этих функций схожа с предыдущими. Функции должны принимать диапазон [first, last) и проверяемый элемент x. Возвращаемое значение: true - если элемент x является преобладающим, иначе - false.

Draft-реализация алгоритмов доступна на github.

[apolukhin]

zamazan4ik@tut.by, 24 апреля 2018, 12:02 Мне идея нравится. Я готов взяться за написание пропозала насчёт этого алгоритма.

Также предлагаю добавить этот алгоритм в Boost.Algorithm (с этим тоже могу помочь). Если Вы не знаете, как это сделать - я могу сделать это за Вас.

[apolukhin]

Алгоритм полезный, предложение ещё никто не написал.

Учтите, что придётся писать ещё и алгоритм для std::ranges