Specification:
Given
first, last
(which areForwardIterator
s, and whosestd::iterator_trais::value_type
isLessThanComparable
), find the most frequent element in the sequence and return pair of iterator to the last occurrence of the element and frequency count. When using overload withcomparator
(which isCompare
), the restriction on value type of iterators is lifted.
Usage guidelines:
Should be used when the elements in the sequence are non copyable or too expensive to copy. Should be avoided when entropy of the sequence is very high, most of the values in the sequence are distinct, size of value type of iterators is within range of a few integers and the sequence is very large.
Code:
#ifndef AREA51_ALGORITHM_HPP
#define AREA51_ALGORITHM_HPP
#include <utility>
#include <map>
#include <iterator>
#include <cstddef>
template <typename ForwardIterator, typename Comparator>
std::pair<ForwardIterator, std::size_t> most_frequent(ForwardIterator first,
ForwardIterator last, Comparator comparator)
{
auto comp = [&comparator](const auto& lhs, const auto& rhs)
{
return comparator(lhs.get(), rhs.get());
};
std::map<std::reference_wrapper<typename std::iterator_traits<ForwardIterator>::value_type>,
std::size_t, decltype(comp)> counts(comp);
std::size_t frequency = 0;
auto most_freq = first;
while (first != last)
{
std::size_t current = ++counts[*first];
if (current > frequency)
{
frequency = current;
most_freq = first;
}
++first;
}
return std::make_pair(most_freq, frequency);
}
template <typename ForwardIterator>
std::pair<ForwardIterator, std::size_t> most_frequent(ForwardIterator first, ForwardIterator last)
{
return most_frequent(first, last, std::less<>{});
}
#endif //AREA51_ALGORITHM_HPP
It took roughly 3 milliseconds to find the most frequent integer in sequence of 100'000 integers that varies from 0 to 100 (release build, still faster than human reaction). The benchmark was very simplistic, so in the real world scenario performance can be different. Some further twisting of input (still simple tests) showed that range of the input (e.g. how many distinct elements are in the sequence) gives algorithmic performance degradation. Usage:
#include <iostream>
#include <string>
struct integer
{
int x;
integer(int y):
x(y)
{}
integer(const integer& other) = delete; //non copyable
integer& operator=(const integer& other) = delete;
};
bool operator<(const integer& lhs, const integer& rhs)
{
return lhs.x < rhs.x;
}
std::ostream& operator<<(std::ostream& os, const integer& x)
{
return os << x.x;
}
int main()
{
int arr[] = {1, 2, 3, 4 , 5, 1};
std::string names[] = {"Olzhas", "Erasyl", "Aigerym", "Akbota", "Akbota", "Erasyl", "Olzhas", "Olzhas"};
auto answer = most_frequent(std::begin(arr), std::end(arr));
std::cout << "The most frequent integer is " <<
*answer.first << " which occured " <<
answer.second << " times\n";
auto most_frequent_name = most_frequent(std::begin(names), std::end(names));
std::cout << "The most frequent name is " <<
*most_frequent_name.first << " which occured " <<
most_frequent_name.second << " times\n";
integer weird_integers[] = {0, 1, 2, 3, 4, 5, 6, 1};
auto most_frequent_integer = most_frequent(std::begin(weird_integers), std::end(weird_integers));
std::cout << "The most frequent weird integer is " <<
*most_frequent_integer.first << " which occured " <<
most_frequent_integer.second << " times\n";
}
The code executes in time faster than human reaction, so I think for the first version this should be enough.
I'm interested in naming (I believe most_frequent
doesn't really match the algorithm), readability and conformance to specification (from the transform_iterator
, I found that it is quite hard to conform it, though it works for my needs). I also thought about std::unordered_map
, but then I would specify too many input variables and types.
By the way, the names are kazakh names :)