Is a std::map<> ordered?

[FFMG]

Hi,

If I have something like :

std::map<int, int> myMap;
myMap[200] = 1;
myMap[100] = 2;
myMap[300] = 3;
myMap[150] = 4;

What does the standard say that the output must be if I iterate thru
the map?

for( std::map< int, int>::const_iterator it = myMap.begin(); it !=
myMap.end(); ++it )
{
// output it->first
}

Is the output...
// 100
// 150
// 200
// 300

Or is it
// 200
// 100
// 300
// 150

Or can it be anything at all and I have no real guarantees ...

What I want to do is iterate though the map from the lowest integer to
the largest, do I need to re-order it first or do anything special.

How can I get the map in the right 'order'

Many thanks

FFMG

 

[Thomas J. Gritzan]

Hi,

If I have something like :

std::map<int, int> myMap;
myMap[200] = 1;
myMap[100] = 2;
myMap[300] = 3;
myMap[150] = 4;

What does the standard say that the output must be if I iterate thru
the map?

A map is always ordered by the key. So the order would be 100, 150, 200,
300 with the corresponding values.

[...]

What I want to do is iterate though the map from the lowest integer to
the largest, do I need to re-order it first or do anything special.

How can I get the map in the right 'order'

You can't reorder a map. A std::map (and std::set) is always ordered by
the key, using the given predicate function, which is std::less by default.

 

[maverik]

What does the standard say that the output must be if I iterate thru
the map?

According to the Bjarne map values is sorted by keys (17.4.1)

How can I get the map in the right 'order'

Use sort()

 

[joseph cook]

  According to the Bjarne map values is sorted by keys (17.4.1)


  Use sort()

No, this is incorrect. A map is always sorted using std::less on the
key (not the value).

It cannot be reordered.

Joe Cook

 

[maverik]

No, this is incorrect.   A map is always sorted using std::less on the
key (not the value).

Hmmm. I mean map values are sorted by keys. Of course, I mistyped
with "is", but where I said about values?

It cannot be reordered.

Ya, you are right. When read FFMG's last question I think that he
wants to sort map. Of course, map elements order cannot be changed.

 

[Juha Nieminen]

A map is always sorted using std::less

Not always. By default, yes, but you can specify other comparators, eg:

std::map<int, int, std::greater> reversedMap;

 

[FFMG]

A map is always ordered by the key. So the order would be 100, 150, 200,
300 with the corresponding values.

Thanks for all the replies.
I just wanted to make sure that the map was always ordered by key.

You can't reorder a map. A std::map (and std::set) is always ordered by
the key, using the given predicate function, which is std::less by default.

What I was trying to say was, 'if the map is not ordered by key how
can I get the map in the right order'.
But seen that it is ordered it does not matter.

Thomas

Thanks again

FFMG

 

[acehreli]

  Not always. By default, yes, but you can specify other comparators, eg:

std::map<int, int, std::greater> reversedMap;

Or at runtime:

std::map<int, int> myMap(myPredicate);

Ali

 

[Rolf Magnus]

Not really. There's a third type argument to std::map which specifies
the map's predicate type, with a default of std::less<T>. This
constructor takes an argument with the same type as the template's
predicate argument, so you can't pass arbitrary predicate objects. This
constructor is only useful with a user-defined predicate type that can
be initialized with something other than its default constructor.

Well, basically that just does mean that it depends on a runtime value.
Otherwise, you wouldn't need those constructor arguments in the first place.

 

[Juha Nieminen]

std::map<int, int> myMap(myPredicate);

I don't think you can do that because the comparator template
parameter is set by default to std::less, and unless myPredicate casts
implicitly to type std::less, that won't work. You have to do it like:

std::map<int, int, MyPredicateType> myMap(myPredicate);

If 'myPredicate' is a function, the syntax becomes awkward:

std::map<int, int, bool(*)(int, int)> myMap(myPredicate);

This becomes even more awkward if the key and data types of the map
are something more complicated than int.

The next standard will offer a tool to alleviate the problem:

std::map<int, int, decltype(myPredicate)> myMap(myPredicate);