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

progzdeveloper
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.

8
рейтинг
1 комментарий
zamazan4ik@tut.by

Мне идея нравится. Я готов взяться за написание пропозала насчёт этого алгоритма. 

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

zamazan4ik@tut.by
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).
Все предложения