std::map with custom key

Question

I would like to use a standard map with the following custom key:

struct ParserKey{
    ParserKey(uint16_t compno,
             uint8_t resno,
             uint64_t precinctIndex) : compno_(compno),
                                       resno_(resno),
                                       precinctIndex_(precinctIndex)
    {
    }
     uint16_t compno_;
     uint8_t resno_;
     uint64_t precinctIndex_;
};

There's no obvious way of ordering the keys, though. Can these keys be ordered, or do I need a different associative collection ?

If the order doesn't matter, then you could use an unordered_map, but then you'd have to provide a way to hash it. If you don't want to do that, and the order doesn't matter, then just sort them based on their 3 values. — ChrisMM, May 30 '22 at 18:27
"*There's no obvious way of ordering the keys, though*" - in principle? There may not be, but what is stopping you from simply ordering by `compno_` first, by `resno_` second and by `precinctIndex_` third? All things considered, you may not even seek ordering at all. In that case, you may find `std::unordered_map` useful. — Fureeish, May 30 '22 at 18:28
Regarding the term "stl" you should read [What's the difference between "STL" and "C++ Standard Library"?](https://stackoverflow.com/questions/5205491/whats-the-difference-between-stl-and-c-standard-library). — François Andrieux, May 30 '22 at 19:13

score 6 · Accepted Answer · answered May 30 '22 at 18:33

6

If you don't care about the specific order and just want to satisfy the requirements for sorting, a common and simple pattern is to use std::tie with all of the class members of the compared instances, and compare those results instead.

std::tie creates a std::tuple of references to the members, and std::tuple implements operator< which compares its elements (the members of the object in this case) lexicographically.

In your case, using member operator< :

bool operator<(const ParserKey & other) const
{
    return std::tie(compno_, resno_, precinctIndex_) < 
        std::tie(other.compno_, other.resno_, other.precinctIndex_);
}

Live example https://godbolt.org/z/v433v54jz

answered May 30 '22 at 18:33

François Andrieux

28,148
6
56
87

This is a better answer than mine. But why use `std::tie` instead of `std::tuple` directly? Grabbing the reference seems unnecessary. Copying the int should be fine. – bitmask May 30 '22 at 18:37
1

@bitmask Using `std::tie` is more generic, it will work as expected with class types. This is what `std::tie` is meant for, bundling several heterogeneous objects that already exist to allow handling them as a single set. If the cost of dererencing isn't optimized out, it is still probably not significant. Until a profile shows `std::tie` is a problem for an application, I would consider using `std::tuple` a premature optimization. Remember that this answer introduces a pattern that can be applied to other use cases, not just an answer specifically for the code shown in the question. – François Andrieux May 30 '22 at 18:43
I find it surprising that comparison of std::tuple pairs is defined because hashing a tuple is not ... has comparison of tuples always been defined? – jwezorek May 30 '22 at 18:47
@jwezorek It has been defined since c++11 which introduced `std::tuple`. It shouldn't be surprising, most container and container-like standard types provide all the comparison operators, but very few come with support for `std::hash`. This is more of a problem with `std::hash` than `std::tuple` specifically. – François Andrieux May 30 '22 at 18:53
Yeah, i just feel like since tuples are value types it is natural to want to use them as keys to unordered maps and well as ordered maps – jwezorek May 30 '22 at 19:00

bitmask · Answer 2 · 2022-05-30T18:31:48.850

4

You can just impose any arbitrary total order on these integers in the same style as std::lexicographical_compare does.

So, the lazy approach is:

// inside ParserKey ...

std::array<std::uint16_t,3> to_array() const {
  return {compno_, resno_, precinctIndex_};
}

friend bool operator<(ParserKey const& lhs, ParserKey const& rhs) {
  auto const l = lhs.to_array();
  auto const r = rhs.to_array();
  return std::lexicographical_compare(begin(l),end(l), begin(r), end(r));
}

But it carries the overhead of pressing your members into an iterable container. If you don't want that, you might have to reimplement a lexicographical compare yourself.

edited May 30 '22 at 18:31

answered May 30 '22 at 18:26

bitmask

32,434
14
99
159

`operator<=>` will do that automatically. No need to turn the fields into an iterable container. That requires C++20 though. – Fureeish May 30 '22 at 18:32
@Fureeish Really?! Huh. Well, my brain isn't used to the spaceship, yet. – bitmask May 30 '22 at 18:33
1

Really :) `auto operator<=>(ParserKey const&) const = default;` will generate `<`, `<=`, `>` and `>=` with respect to the fields in their order of declaration. It's great! – Fureeish May 30 '22 at 18:34

score 3 · Answer 3 · answered May 30 '22 at 19:26

In C++20 you can do this: (at class scope)

friend auto operator<=>(const ParserKey &, const ParserKey &) = default;

Don't forget to #include <compare>.

This will give you all 6 relational operators: ==, !=, <, <=, >, >=, performing lexicographical comparison (same as in @FrançoisAndrieux's answer).

std::map with custom key

3 Answers3