Search code examples
pythonc++hashsetunordered

C++ Comparison operators for std::unordered_set

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?

Solution

  • 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);