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.
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.
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:
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>();
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;
}
All the ordered standard containers return pair<iterator, bool> with the bool==false when the insertion didn't happen because of unique key existing. You have to manually force an update if you wanted to overwrite, so just... don't
You can use any ordered container with a suitable comparison. To make your life easy:
struct Element {
int _key;
enum_type _type;
double _value;
bool operator<(const Element& other) const {
return std::tie(_key,_type) < std::tie(other._key,other._type);
}
};
int main() {
std::set<Element> elements { { 1, TYPE1, 1.0 }, { 1, TYPE2, 2.0 }, { 3, TYPE1, 3.0 } };
fmt::print("elements: {}\n", elements);
}
See it Live On Coliru printing
elements: {{ key: 1, type: 1, value: 1 }, { key: 1, type: 2, value: 2 }, { key: 3, type: 1, value: 3 }}
The key/value separation suggests you should make it a true associative container:
using Value = double;
struct Key {
int _key;
enum_type _type;
auto operator<=>(Key const&) const = default;
};
int main() {
std::map<Key, Value> elements{
{{1, TYPE1}, 1.0},
{{1, TYPE2}, 2.0},
{{3, TYPE1}, 3.0},
};
fmt::print("elements: {}\n", elements);
}
Printing, Live On Coliru:
elements: {{ key: 1, type: 1 }: 1, { key: 1, type: 2 }: 2, { key: 3, type: 1 }: 3}
This gives you much more natural syntax, like
elements[{1, TYPE3}] += 42;
As commented, you have the classic idiom:
bool insert_or_update(auto& c, Key k, Value v) {
auto [it, inserted] = c.emplace(k, v);
if (!inserted) {
fmt::print("updating value for key: {} from {} to {}\n", k, it->second, v);
it->second = v;
}
return inserted;
}
As you can see Live On Coliru
In c++17 insert_or_assign was invented for the purpose:
c.insert_or_assign( {2, TYPE1}, 10.0);
fmt::print("elements: {}\n", c);
c.insert_or_assign({2, TYPE1}, 42.0);
fmt::print("elements: {}\n", c);
See that Live On Coliru too
You need std::multiset<Element, CustomComparator> where CustomComparator only compares Element::_key:
struct CustomComparator
{
bool operator<( const Element& lhs, const Element& rhs) const
{
return lhs._key < rhs._key;
}
};
Unlike std::set which ensures the uniqueness of its elements, std::multiset allows having multiple equivalent elements.
Edit: I wrote this answer before OP's edit, where they added the requirement of overwriting if both _key and _type match. Using std::multiset does not satisfy this requirement.
_keyand_typeare the same? – JaMiT Commented Feb 4 at 0:59std::set(sets are associative containers), the behavior is not overwriting an existing element. Are you thinking specifically of a map'soperator[]combined with assignment? If so, there is always an overwrite; it's just that if the key does not exist,operator[]will insert a default-constructed entry for the assignment to overwrite. A line of code showing the insertion might clear this up. – JaMiT Commented Feb 4 at 2:24