C++ Comparison operators for std::unordered_set

Question

This post raised a question of the absence of >, < .. comparison operators for unordered containers in C++. From the reply it looks meaningless to have those.

However, I checked Python and see that set type supports subset and superset operations. Python set is a hash table. We can easily do:

{'1', '6',  't', 'j'} > {'1', '6', 'j'}   # superset
True
{'1', '6', 'j', 't'} < {'1', '6', 'j'}    # subset
False

How to implement comparison operators in C++ for hash table (std::unordered_set)? Or we do have to stick to std::set for any comparison other than equality?

You still have the option to define your own custom relations according to your needs. — Scheff's Cat, Sep 29 '20 at 08:07
You cannot add operator overload for `std` types, because ADL will not find them (and you are not allowed to add anything to namespace `std`). You can implement a function or function object tho. — Yksisarvinen, Sep 29 '20 at 08:08
The [`std::set` uses lexicographic comparison](https://en.cppreference.com/w/cpp/container/set/operator_cmp). You could look into using [`std::lexicographical_compare`](https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare)` to achieve the same with a `std::unordered_set`. — JHBonarius, Sep 29 '20 at 08:15

score 2 · Accepted Answer · answered Sep 29 '20 at 08:44

Python's sets have a partial order, not a total order, based on the subset relation. E.g. neither { 1, 2, 3 } < { 2, 3, 4 } nor { 1, 2, 3 } > { 2, 3, 4 } are true, but { 1, 2, 3 } == { 2, 3, 4 } is false.

You can write a < that behaves like that, but as noted in the comments, you can't put it in namespace std, so it won't be found in some contexts.

I'd advise instead making a free function

template<typename UnorderedContainer>
bool is_proper_subset(const UnorderedContainer & lhs, const UnorderedContainer & rhs);

You could also make variations for <=, > and >= (respectively)

template<typename UnorderedContainer>
bool is_subset(const UnorderedContainer & lhs, const UnorderedContainer & rhs);

template<typename UnorderedContainer>
bool is_proper_superset(const UnorderedContainer & lhs, const UnorderedContainer & rhs);

template<typename UnorderedContainer>
bool is_superset(const UnorderedContainer & lhs, const UnorderedContainer & rhs);

C++ Comparison operators for std::unordered_set

1 Answers1