Container to sort on class member A but differentiate equal keys on class member B?

Question

I want to store this struct in a container:

struct Element
{
    int       _key;
    enum_type _type;
    double    _value;
};

_key is for sorting when inserted.

_type should differentiate if keys are identical values.

For example, say I have:

Element x(6, enum_type::A, 57.76);
Element y(7, enum_type::B, 104.29);

x would be first and y second because 6 < 7.

However, if the keys are identical:

Element x(6, enum_type::A, 57.76);
Element y(6, enum_type::B, 104.29);

The order doesn't matter, so long as the second-inserted does not over-write the first-inserted.

Which container be best to implement this (including Boost flat_set, flat_map etc)?

Notes:

• The ordering doesn't matter.... across elements with the same _key (and different _types) but ordering always matters when _keyss are different.

• If _key and _type are identical, it should follow typical associative behavior and over-write the existing element.

Answer 1

Caveats (when you should not use this answer)

Consistency is golden. You can eliminate a lot of complexity simply by being consistent. You've established that your container must be ordered with respect to _key. So order it with respect to _type as well. This does not violate "doesn't matter" and the result is fairly simple (as shown in another answer, so I won't go into more detail here).

However, it is conceivable that someone in an otherwise similar situation wants to prohibit using an order based on the secondary field (your _type). Maybe instead of an enumeration, the secondary field has a type that has no intrinsic order or that is expensive to order. Or maybe each primary field (your _key) will have a LOT of entries with different secondary fields, to the point where performance is a concern. In such a case, maybe it is worth being inconsistent.

Remember kids, over-engineering is fun, but don't overdo it. Unless you have to. And that brings us to:

Multi-index container from Boost

If you really need to combine sorted and unsorted semantics in one container, Boost.MultiIndex has what you need. In fact, one of the examples for that module is multiple sorts on a single set. One "sort" can use a hash to enforce uniqueness of the primary plus secondary fields, while the other sort can maintain the order by just the primary field. It's a rather powerful tool, but be warned that it can get complex. Here is the preliminary work I'd use before defining the container's type.
Note: I put this in its own code block so that those who want to can skip over it. It consists of headers and aliases, so you could skip it for now then refer back as needed.

#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>

namespace bmi = boost::multi_index;

// Aliases that represent fields within `Element`:
using BmiMemberElementKey = bmi::member<Element, int, &Element::_key>;
using BmiMemberElementType = bmi::member<Element, enum_type, &Element::_type>;
// The above template arguments are the class, the type of the field, and
// a pointer-to-member that matches the earlier arguments

// View data as unordered, not allowing multiples for a given `_key` and `_type`:
using UniqueElementByKeyAndType = bmi::hashed_unique<
    bmi::composite_key<Element, BmiMemberElementKey, BmiMemberElementType>>;

// View data as ordered by `_key`, allowing multiple entries:
using SortElementByKey = bmi::ordered_non_unique<BmiMemberElementKey>;

That is much more work than defining operator< on Element, isn't it? Still, if you need it, you need it. Once you get through these preliminaries, the container would be the following.

// Define the container with the two views:
using Container = bmi::multi_index_container<
    Element,                                                     // <-- Value type
    bmi::indexed_by<UniqueElementByKeyAndType, SortElementByKey> // <-- Sorts/views
>;

The direct API for this container mostly mirrors whatever corresponds to the first thing listed in indexed_by; in this case the correspondence is to std::unordered_set. If you rarely need this interface, or just more often need the sorted view (corresponding to std::set), you could reverse the arguments to indexed_by. When you need to access the view that is not first, use the member function get<1>(). More generally, get<0>() accesses the view corresponding to the first argument to indexed_by (which is also the default view), get<1>() the second, etc. The value returned by these functions must be stored in a reference, as in

auto& view = container.get<1>();

Overwriting

Since the API mirrors that of standard containers, the MultiIndex container has the typical (associative or otherwise) behavior of not overwriting an existing element when inserting. So a helper function might be useful. Note that the below helper makes a copy of the Element if there is nothing to overwrite, so use caution if your class is expensive to copy (the question's Element is not expensive to copy).

// Inserts or replaces an element, returning an iterator to the entry.
auto insert_or_replace(Container& data, Element entry) {
    auto [position, success] = data.insert(entry);
    if (!success)
        data.replace(position, std::move(entry));
    return position;
}