CODEWITHSUNDEEP
c++iteratorstdmap
Martin G
Martin G

Reputation: 18129

The ordering of an std::map

For an std::map, can i always trust begin() to return the element with the smallest key according to comparison operators for the type, when iterating?

In other words...

Will std::map<Key, SomeClass>::iterator smallestKeyIt = someMap.begin(); give me the pair in the map with the smallest key?

Is this the ordering that is quaranteed for an std::map or can i configure it somehow? My understanding is that the underlaying tree structure is kept ordered when performing operations such as adding and removing elements.

Upvotes: 1

Views: 1392

Answers (2)

songyuanyao
songyuanyao

Reputation: 173044

can i always trust begin() to return the element with the smallest key according to comparison operators for the type?

Yes.

Is this the ordering that is quaranteed for an std::map or can i configure it somehow?

Yes. And you can configure the behaviour of comparing by specify the comparator. (The default one is std::less.)

From cppreference:

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.

Upvotes: 3

R Sahu
R Sahu

Reputation: 206737

std::map is defined as:

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

You can use your specialized Compare to configure how the entries of a map are ordered. For example, if you use:

std::map<int, double, std::greater<int>> myMap;

then, the first entry in myMap will have the largest key.

Upvotes: 3

Related Questions