What Requirements Must Std::Map Key Classes Meet to Be Valid Keys

What requirements must std::map key classes meet to be valid keys?

All that is required of the key is that it be copiable and assignable.
The ordering within the map is defined by the third argument to the
template (and the argument to the constructor, if used). This
defaults to std::less<KeyType>, which defaults to the < operator,
but there's no requirement to use the defaults. Just write a comparison
operator (preferably as a functional object):

struct CmpMyType
{
    bool operator()( MyType const& lhs, MyType const& rhs ) const
    {
        //  ...
    }
};

Note that it must define a strict ordering, i.e. if CmpMyType()( a, b
) returns true, then CmpMyType()( b, a ) must return false, and if
both return false, the elements are considered equal (members of the
same equivalence class).

std::map Requirements for Keys (Design Decision)

operator== is inevitable for std::map::find()

This is where you go badly wrong. map does not use operator== at all, it is not "inevitable". Two keys x and y are considered equivalent for the purposes of the map if !(x < y) && !(y < x).

map doesn't know or care whether you've implemented operator==. Even if you have, it need not be the case that all equivalent keys in the order are equal according to operator==.

The reason for all this is that wherever C++ relies on orders (sorting, maps, sets, binary searches), it bases everything it does on the well-understood mathematical concept of a "strict weak order", which is also defined in the standard. There's no particular need for operator==, and if you look at the code for these standard functions you won't very often see anything like if (!(x < y) && !(y < x)) that does both tests close together.

Additionally, none of this is necessarily based on operator<. The default comparator for map is std::less<KeyType>, and that by default uses operator<. But if you've specialized std::less for KeyType then you needn't define operator<, and if you specify a different comparator for the map then it may or may not have anything to do with operator< or std::less<KeyType>. So where I've said x < y above, really it's cmp(x,y), where cmp is the strict weak order.

This flexibility is another reason why not to drag operator== into it. Suppose KeyType is std::string, and you specify your own comparator that implements some kind of locale-specific, case-insensitive collation rules. If map used operator== some of the time, then that would completely ignore the fact that strings differing only by case should count as the same key (or in some languages: with other differences that are considered not to matter for collation purposes). So the equality comparison would also have to be configurable, but there would only be one "correct" answer that the programmer could provide. This isn't a good situation, you never want your API to offer something that looks like a point of customization but really isn't.

Besides, the concept is that once you've ruled out the section of the tree that's less than the key you're searching for, and the section of the tree for which the key is less than it, what's left either is empty (no match found) or else has a key in it (match found). So, you've already used current < key then key < current, leaving no other option but equivalence. The situation is exactly:

if (search_key < current_element)
    go_left();
else if (current_element < search_key)
    go_right();
else
    declare_equivalent();

and what you're suggesting is:

if (search_key < current_element)
    go_left();
else if (current_element < search_key)
    go_right();
else if (current_element == search_key)
    declare_equivalent();

which is obviously not needed. In fact, it's your suggestion that's less efficient!

Using class member as key in a std::map of said class

Lets consider the key features of the map

• unique keys
• ordererd with respect to keys
• keys are const, values not
• key are stored seperately from the mapped values

Your requirement is in contrast with the last bullet so now you can consider what compromise you can make with the others.

• std::set<A,CustomComparator>

With a custom comparator you can ensure unique keys that can be stored in the values and sorting can be the same as with the map. But elements are const. You could use mutable but this bypasses const-correctness and should be used with care.

• std::vector<A>

This is the most flexible but you need to take care of almost everything you got from the map manually. It can be feasible if you populate the vector only once and then only access elements, because then you need to check for uniqueness and sort the elements only once.

• some non-std container

Jarod42 suggested boosts intrusive set. There might be other non-standard containers that fit your needs.

• just stay with std::map<A::type,A>

If the key is only a single enum value, then storing the keys twice is an easy solution that has some cost, but allows you to use a map when that is the container you want to use.

• Not store the keys in the mapped_values in the first place

This is actually the cleanest solution when the mapped_values are only stored in the map and not used outside of the map. And when you still need the mapped_values together with the keys outside of the map you can use std::pair<type::A,A>.

Do I need a full ordering on class K to use std::map<K, L>

Yes, you need a way to compare elements (operator<) in order to use the std::map. One of the features of map is that it keeps its contents in sorted order, but to achieve this its need to know how to compare items.

You have three options to implement a comparison method:

1. Add operator< definition in K

2. Make a comp functor that know to how to compare two K elements and add this as a template parametermap<K, float, comp> m;

   struct comp {
       bool operator()(const K& first, const K& second) {
           /*****/
       }
   };
   

3. You can define the std::less specialization for K

   template<>  struct less<K>
   {
       bool operator()(const K& first, const K& second) {
           /*****/
       }
   };
   

And simple use map<K, float> m;

This works because by the template definition for map has the compare function set to std::less.

template < class Key, class T, class Compare = less,
class Allocator = allocator > > class map

in c++ std library, assigning to a map element at index -1

It's doing what it says: Assigning the string "input" to the map entry whose key is -1.

There's no concept of a default value with std::map.

Remember, the key of a std::map doesn't have to be an int (let alone, positive ints) - it can be pretty much any type. std::map isn't a vector.

What requirements must std::map key classes meet to be valid keys?

Custom Key for std::map<>

The index operator (the "[]") is a non-const member function of std::map. Whereas, you have clearly indicated that keysBoundTo is a const member.

Rewrite keysBoundTo as

std::set<sf::Keyboard::Key> InputManager::keysBoundTo(ActionId action) const
{
    auto it = keyBindigs_.find(action);
    if ( it == keyBindings_.end() )
        return std::set<sf::Keyboard::Key>();
    else
        return it->second;
}

Notice that I renamed your member variable to have a trailing underscore. Do not use identifiers with leading underscores.

---

Related Topics