CODEWITHSUNDEEP
c++stl
ronan
ronan

Reputation: 4672

Sort Order in STL map and set

How are the user defined objects sorted in map and set? As far as I know, map/set are Sorted Associative Containers: the elements being inserted are sorted based on the key that it holds.

But map and set internally use operator > to sort their elements.

From the SGI site, I have the following examples:

struct ltstr
{
    bool operator()(const char* s1, const char* s2) const
    {
        return strcmp(s1, s2) < 0;
    }
};

int main()
{
    map<const char*, int, ltstr> months;

    months["january"] = 31;
    months["february"] = 28;
    months["march"] = 31;
    months["april"] = 30;
    months["may"] = 31;
    months["june"] = 30;
    months["july"] = 31;
    months["august"] = 31;
    months["september"] = 30;
    months["october"] = 31;
    months["november"] = 30;
    months["december"] = 31;

    cout << "june -> " << months["june"] << endl;

    map<const char*, int, ltstr>::iterator cur  = months.find("june");
    map<const char*, int, ltstr>::iterator prev = cur;
    map<const char*, int, ltstr>::iterator next = cur;

    ++next;
    --prev;

    cout << "Previous (in alphabetical order) is " << (*prev).first << endl;
    cout << "Next (in alphabetical order) is " << (*next).first << endl;
}

In the above example, how are the values sorted?

Edit: Code moved from comment:

typedef map <string, int> Mint ;

int main() 
{
    string Name ;
    int Marks;
    Mint Grade;
    for (int i = 0; i<4; i++) 
    {
        cin>> Name ; 
        cin >> Marks; 
        Grade [Name] = Marks ; 
    } 
    Mint :: iterator iter; 
    for( iter = Grade.begin(); iter != Grade.end(); iter++)
        cout<< (*iter).first<<“ \t ” <<(*iter).second<<“\n” ; 
    return 0; 

}

How would the values get sorted?

Upvotes: 8

Views: 19685

Answers (2)

Kirill V. Lyadvinsky
Kirill V. Lyadvinsky

Reputation: 99605

std::map uses a functor to sort elements. By default is it std::less<Key> which uses operator<. In your sample there is an user defined functor ltstr which will help to sort elements according to its keys in alphabetical order.

Upvotes: 10

Naveen
Naveen

Reputation: 73443

First of all operator< is used by default and not operator>. In your case, you are passing a custom comparison function by passing the third template parameter while creating the map object. While inserting each element to the map, this comparison functor is used to determine the relative ordering of the object in the map i.e. it is used to compare the keys. For example, when you do months["february"] = 28;, map compares the the keys "january" and "february". Since we are doing a string compare, this comparison returns a value greater than 0. This value is used to determine the position of the key "february" in relation to "january".

Upvotes: 3

Related Questions