C++: std::map sorting

Question

I am a newbie to C++, and this question may seem obvious to a lot of people.

If I write something like

std::map<int, double> m;

• Is m guaranteed to be sorted according to int order?
• Is it necessary to define a comparitor class to enforce the sorting?

For example,

class own_int_less : public binary_function<int, int, bool>
{
public:
    bool operator()( const double &left, const double &right  ) const
    {
        return (abs(left - right) > epsilon) && (left < right);
    };
    double epsilon;
};

• When is the sorting actually occurred? I mean does the sorting function get called every time I insert something into the map? Or does it get called before I iteration through the map?

Thanks.

Answer 1

Is m guaranteed to be sorted according to int order?

Yes. The default comparator is std::less<Key>, which in your case is std::less<int>, which just uses < as expected.

Is it necessary to define a comparitor class to enforce the sorting?

No, because the previous answer was "yes"!

When is the sorting actually occurred?

A typical map implementation uses the comparator to insert a new element into the correct location. The comparator is also used when doing a lookup.