0

So maps need you to implement the operator < if you want to use custom objects as keys.

struct example{
    example( int id, String stuff);
    int id;
    String stuff;
    bool operator<( const example& rhs ) const;
}

bool example::operator<( const example& rhs ) const
{
    if( id< rhs.id ) return true;
    if( rhs.id< id) return false;
    if( stuff< rhs.stuff) return true;
    if( rhs.stuff< stuff) return false;
    return false;
}

From the examples I have seen (see discussion: Why std::map overloaded operator < does not use the Compare ) just return true if the lhs < rhs...

  1. Why does map require you to implement the < operator? Is it because maps are doing binary search in the background to find if the key matched?
  2. Even if it is doing binary search it will still have to compare if the objects are equal at the end right?
example example1 = example(1,"a");
example example2 = example(2,"b");

map<example, String> mymap; 
mymap.insert({example1,"hello"});
mymap.insert({example2,"world"});

cout << mymap[example(1,"a")] << endl;

It never asks for an implementation of the operator= so how does it know the new object I have created is the same as the first entry of the map. Would it print "hello"?

GSerg
  • 76,472
  • 17
  • 159
  • 346
theBigCheese88
  • 442
  • 4
  • 16
  • `Why does map require you` - https://stackoverflow.com/a/6573303/11683? – GSerg Nov 19 '19 at 11:21
  • Because weak order key comparison says so. Think of it this way, if `(a < b)` is false, *and* `(b < a)` is also false, what can you tell me about the equivalence of `a` and `b` ? And, related, you don't need to implement `operator <` to unilaterally use `std::map`, you can implement a ground up comparator type. `operator <` comes into play if you *don't* provide a custom comparator type, opting instead for the library default, `std::less`, which (drumroll) internally uses `operator <`. The choice if yours where to provide strict weak comparison semantics. – WhozCraig Nov 19 '19 at 11:22
  • `!((a < b) || (b < a))` is the same as `a == b`, so `operator<` is sufficient. – mch Nov 19 '19 at 11:23
  • [`std::map`](https://en.cppreference.com/w/cpp/container/map) is an ordered map, keys are sorted according to the given comparison criteria. It does not matter how this is implemented internally (which is generally not through binary searches as such, but with some kind of binary tree), it needs the comparison because the abstract data structure requires it. You can use [`std::unordered_map`](https://en.cppreference.com/w/cpp/container/unordered_map) if you do not need sorted keys. – jdehesa Nov 19 '19 at 11:23
  • Map is ordered so it needs the operator to determine that order. Switch to ``unordered_map`` if it doesn't matter to you. Lookup is faster when unordered as well. – Pickle Rick Nov 19 '19 at 11:24
  • @jdehesa Beat me by 20 seconds. lol – Pickle Rick Nov 19 '19 at 11:24
  • @PickleRick You still make a good point that lookup is also faster in `unordered_map`. – jdehesa Nov 19 '19 at 11:25
  • I have a feeling that you mix two different things, namely, _comparison of keys from a single map_, and _comparison of two different maps_. The question you linked is about the latter, while in your code, you have only a single map. – Daniel Langr Nov 19 '19 at 11:31

1 Answers1

1

It stores values in a balanced binary tree, red black tree as usual, so comparison operator is required for this tree

also keep in mind that if a < b == false and b < a == false it is considered that a is equal to b

jrok
  • 54,456
  • 9
  • 109
  • 141
bobra
  • 615
  • 3
  • 18
  • 2
    _It stores values in a red black tree_ — this is, generally, not correct. The underlying data structure is implementation-defined. _operator < is required for this tree_ — also incorrect, you can pass any functor as a comparator template argument. – Daniel Langr Nov 19 '19 at 11:27