Is a std::map<> ordered?
FFMG
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.
--
Thomas
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
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
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.
>
> > 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.
>
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
aceh...@gmail.com
Or at runtime:
std::map<int, int> myMap(myPredicate);
Ali
Pete Becker
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.
--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)
Rolf Magnus
> On 2008-11-20 14:40:19 -0500, aceh...@gmail.com said:
>
>> On Nov 20, 7:48 am, Juha Nieminen <nos...@thanks.invalid> wrote:
>>> joseph cook wrote:
>>>> A map is always sorted using std::less
>>>
>>> Not always. By default, yes, but you can specify other comparators, e
>> g:
>>>
>>> std::map<int, int, std::greater> reversedMap;
>>
>> Or at runtime:
>>
>> std::map<int, int> myMap(myPredicate);
>>
>
> 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);
Pete Becker
It means that std::map<int, int> myMap(myPredicate) is an error unless
the type of myPredicate is std::less<int>, in which cast it's
irrelevant. In particular, it is not a runtime replacement for
std::map<int, int, std::greater<int>>.
Pete Becker
> aceh...@gmail.com wrote:
>> 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);
Well, yes, and as we've seen in many Ginsu knife commercials, a normal
knife can't slice a tomato. The way to write this code is, of course,
with appropriate typedefs:
typedef bool (*pred)(int,int);
std::map<int, int, pred> myMap(myPredicate);
>
> This becomes even more awkward if the key and data types of the map
> are something more complicated than int.
Not at all. Again, typedefs.