Ordered associative containers with identity-based equality

Question

I am writing a template function, with template argument X. Inside that function, I want to create std::set<std::pair<int, X>> such that:

• objects in that set are sorted by the first (int) field of the pair (I don't care about how ties are broken)
• I can add multiple objects with the same .first to the set, as long as their .second are not identical

If I knew that template argument X always has < defined, the most basic std::set<std::pair<int, X> (with the default comparator) would have worked perfectly fine. Unfortunately, I cannot assume anything about X.

I was thinking to "cheat" and use pointer-based comparison for the X field:

template <typename X>
struct DistCmp {
    bool operator()(const std::pair<int, X>& lhs, const std::pair<int, X>& rhs) const {
        return lhs.first < rhs.first || lhs.first == rhs.first && &lhs.second < &rhs.second;
    }
};

template <typename X>
void f() {
    std::set<std::pair<int, X>, DistCmp<X>> s{};
    // ...
}

(After all, I don't really care how the .second is compared, as long as it's not compared equally for non-identical objects.)

Unfortunately, I don't think it's correct. Partly because of the quote from C++ standard here (it suggests that pointer comparison, in general, is unspecified, so I can't rely on them being unequal for non-identical objects). And partly I just feel it's suspicious/hacky.

Is there any clean/portable solution for this issue?

Update:

One approach I thought about was to use == for the comparison of pointers instead of <. However, this is no good because it will cause pair<1, x> < pair<1, y> && pair<1, y> < pair<1, x> to be true. This violates the requirement of strict weak ordering and may cause stuff to break.

Answer 1

Short answer: use std::multiset and sidestep whole issue - multiset allows multiple keys, so just compare on first element of pair.

Note, that if you want to disallow the same VALUE of X in your map, you've to add requirement to X, so it were at least EqualityComparable. Otherwise you can't even detect, when values of X are the same and when are different.

Longer answer: Your code won't produce the result you're hoping for. Consider adding new pair <0, x> to map with <0, x>. std::map will try to find existence of <0, x> using temporary copy of <0, x>. It will use address of x (temporary!), it will compare false to everything, that is inside in map and std::map will find a place to insert based on address of x (temporary!). Then it will COPY x, thus changing address and possibly breaking its own ordering.

Answer 2

I think ::std::map< int, ::std::set< X > > satisfies both of your criteria.

Update: since there might be no < operator to compare X instance you may want to write a template with specialization:

#include <map>
#include <set>
#include <vector>
#include <type_traits>
#include <algorithm>
#include <utility>

//  Default implementation is used when there is no < operator to compare T instances,
//  but there is == operator.
template< typename T, typename TDummy = void >
t_FancyContainerHelper final
{
    public: using
    t_Values = ::std::vector< T >;

    public: using
    t_IntToValues = ::std::map< int, t_Values >;

    public: static void
    Insert(t_IntToValues & int_to_values, int const key, T const & value)
    {
        auto p_pair{int_to_values.find(key)};
        if(int_to_values.end() != p_pair)
        (
            auto const & values(p_pair->second);
            if(values.end() != ::std::find(values.begin(), values.end(), value))
            {
                return;
            }
        }
        else
        {
            p_pair = int_to_values.emplace
            (
                ::std::piecewise_construct
            ,   ::std::forward_as_tuple(key)
            ,   ::std::forward_as_tuple()
            ).second;
        }
        auto & values(p_pair->second);
        values.emplace(value);
    }
};

//  This specialization is used when there is < operator to compare T instances.
template< typename T > class
t_FancyContainerHelper
<
    T
,   ::std::enable_if_t
    <
        ::std::is_same
        <
            bool
        ,   decltype
            (
                ::std::declval< T const & >()
                <
                ::std::declval< T const & >()
            )
        >
    >
> final
{
    public: using
    t_Values = ::std::set< T >;

    public: using
    t_IntToValues = ::std::map< int, t_Values >;

    public: static void
    Insert(t_IntToValues & int_to_values, int const key, T const & value)
    {
        auto p_pair{int_to_values.find(key)};
        if(int_to_values.end() != p_pair)
        (
            auto const & values(p_pair->second);
            if(values.end() != values.find(value))
            {
                return;
            }
        }
        else
        {
            p_pair = int_to_values.emplace
            (
                ::std::piecewise_construct
            ,   ::std::forward_as_tuple(key)
            ,   ::std::forward_as_tuple()
            ).second;
        }
        auto & values(p_pair->second);
        values.emplace(value);
    }
};