Перенос предложения: голоса +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.
Перенос предложения: голоса +10, -1
Автор идеи: progzdeveloper
Предлагается добавить в STL реализацию алгоритма для нахождения преобладающего элемента в последовательности.
Под преобладающим элементом подразумевается элемент который встречается больше n/2 раз в массиве длины n. Поиск может быть выполнен за линейное время с использованием O(1) памяти.
Этот алгоритм хорошо известен и имеет широкое применение.
Сигнатуры функций, реализующих алгоритм, могут выглядеть так:
Тип _FwdIt должен удовлетворять концепту forward-only итератора.
Функции должны принимать диапазон [first, last), и возвращать итератор, указывающий на преобладающий элемент, если таковой имеется, иначе - last.
Второй вариант функции принимает пользовательский функтор сравнения элементов, как это принято в STL.
В пару к представленным функциям, предлагаются также функции проверки - является ли некоторое значение преобладающим элементом:
В целом семантика этих функций схожа с предыдущими. Функции должны принимать диапазон [first, last) и проверяемый элемент x. Возвращаемое значение: true - если элемент x является преобладающим, иначе - false.
Draft-реализация алгоритмов доступна на github.