CODEWITHSUNDEEP
c++dictionary
theBigCheese88
theBigCheese88

Reputation: 452

Why maps need to implement the 'operator<' and how are the objects then compared?

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"?

Upvotes: 0

Views: 349

Answers (1)

bobra
bobra

Reputation: 625

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

Upvotes: 1

Related Questions