Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
template <
typename LhsForwardIterator,
typename RhsForwardIterator,
typename Equal = std::equal_to<typename LhsForwardIterator::value_type>,
typename Hash = std::hash<typename LhsForwardIterator::value_type>
>
bool is_permutation_hash_2(
LhsForwardIterator lhs_first, LhsForwardIterator lhs_last,
RhsForwardIterator rhs_first, RhsForwardIterator rhs_last,
Equal equal = Equal(),
Hash hash = Hash())
{
auto lhs_size = std::distance(lhs_first, lhs_last);
if (lhs_size != std::distance(rhs_first, rhs_last))
return false;
using value_type = typename LhsForwardIterator::value_type;
std::unordered_map<value_type, int, Hash, Equal> frequencies;
frequencies.reserve(lhs_size);
for (; lhs_first != lhs_last; ++lhs_first) frequencies[*lhs_first] += 1;
for (; rhs_first != rhs_last; ++rhs_first)
{
auto where = frequencies.find(*rhs_first);
if (where == frequencies.end()) return false;
--where->second;
}
return std::all_of(begin(frequencies), end(frequencies),
[](auto const& p) { return p.second == 0; });
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.