C++ Unordered Pair Type

Question

I'd like to create an unordered pair type in c++, that is, an unordered_set guaranteed to have exactly two elements. Here's what I've come up with, but the problem is if I use this approach, there's a heck of a lot more I have to override - each of the comparison operators, and so on. Is there a simpler way?

class unordered_pair : public std::pair<t, u>
{
public:
    unordered_pair(t x, u y) : std::pair<t, u>(x,y) {};
    bool operator ==(const unordered_pair<t,u>& rhs)
    {
        if ((this->first < this->second) ^ (rhs.first < rhs.second))
        {
            return this->second == rhs.first && this->first == rhs.second;
        }
        else
        {
            return this->first == rhs.first && this->second == rhs.second;
        }
    }
};

Answer 1

I would do something like

struct unordered_pair : std::pair<t, u>
{
    bool swapped;

    unordered_pair(t x, u y) : 
        std::pair<t, u>(x,y),
        swapped(false);
    {
        sort();
    }

    void sort() {
        swapped = first > second;
        if (swapped)
            std::swap(first, second);
    }

    std::pair<t, u> getOrig() {
        if (swapped)
            return std::pair<t,u>(second, first);
        return std::pair<t, u>(first, second);
    }
}

Then you just call sort() every time you change first or second; and all the comparison operators are obtained from the std::pair for free!

The motivation is that if you don't care about the ordering for comparisons, then you won't care about the ordering most of the time; Which will mean most of the time, you won't need to get the original item.

Edit: You state in the comments that we can assume t==u ... in that case I would suggest getting rid of t or u - and make it just std::pair<t, t>

Answer 2

Aside: I'm assuming that you meant

template<typename t>
class unordered_pair : public std::pair<t, t>

since it doesn't make sense for the members to be of different types if they should be interchangeable.

---

You could write a simple sorted() method, to ease writing these overloads:

private:
    std::tuple<t const&, t const&> ordered() const noexcept
    {
        return (this->first < this->second)
            ? std::tie(this->first, this->second)
            : std::tie(this->second, this->first);
    }
};

Then implement == and < using that:

bool operator ==(const unordered_pair<t>& rhs) const noexcept
{
    return ordered() == rhs.ordered();
}
bool operator <(const unordered_pair<t>& rhs) const noexcept
{
    return ordered() < rhs.ordered();
}

and the other operators in terms of those:

bool operator !=(const unordered_pair<t>& rhs) const noexcept
{
    return !(*this == rhs);
}

bool operator >(const unordered_pair<t>& rhs) const noexcept
{
    return rhs < *this;
}

bool operator <=(const unordered_pair<t>& rhs) const noexcept
{
    return !(rhs < *this);
}

bool operator >=(const unordered_pair<t>& rhs) const noexcept
{
    return !(*this < rhs);
}

---

Alternatively, if you have C++20, then implement <=> instead:

template<typename T>
class unordered_pair : public std::pair<T, T>
{
public:
    unordered_pair(T x, T y)
        : std::pair<T, T>(x,y)
    {}

    std::strong_ordering operator<=>(const unordered_pair<T>& other)
    {
        return ordered() <=> other.ordered();
    }

private:
    std::tuple<T const&, T const&> ordered() const noexcept
    {
        return (this->first < this->second)
            ? std::tie(this->first, this->second)
            : std::tie(this->second, this->first);
    }
};

Or even absorb the helper into the operator:

std::strong_ordering operator<=>(const unordered_pair<T>& other)
{
    auto ordered = [](unordered_pair<T> const& t) {
        return (t.first < t.second)
        ? std::tie(t.first, t.second)
        : std::tie(t.second, t.first);
    };

    return ordered(*this) <=> ordered(other);
}

---

Whichever approach you take, you'll want to be careful not to compare through base-class pointers, or you'll get inconsistent behaviour.

Answer 3

Let's fill in some types into this template (which you omitted the template, there is no declaration of t or u), and see what it tries to instantiate

unordered_pair<int, std::string> pair, pair2;

bool operator ==(const unordered_pair<t,u>& rhs)
{
    if ((this->first < this->second) ^ (rhs.first < rhs.second))

This is bool operator <(int, std::string) and bool operator <(std::string, int). These don't exist.

    {
        return this->second == rhs.first && this->first == rhs.second;
    }

This is bool operator ==(int, std::string) and bool operator ==(std::string, int). These also don't exist.

    else
    {
        return this->first == rhs.first && this->second == rhs.second;
    }
}

You instead want one template type parameter. Try something like this

class bad_unordered_pair : public std::exception
{
    const char * what() const { return "unordered_pair must have exactly two distinct values"; }
}

template <typename T>
std::pair<T, T> make_unordered_pair(T first, T second)
{
    std::hash<T> hash;
    if (first == second) throw bad_unordered_pair{};
    if (hash(first) < hash(second)) return unordered_pair(first, second);
    return unordered_pair(second, first);
}