By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,420 Members | 1,133 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,420 IT Pros & Developers. It's quick & easy.

STL map class ordering

P: n/a
My question is about the STL map class and how it sorts data that it
stores. By default (as far as I know) it sorts keys in ascending order
or lexicographically.

If I were to do something like this:

ages["z"] = 1;
ages["a"] = 5;
ages["x"] = 1;

for( map<string, int>::iterator iter = ages.begin(); iter !=
ages.end(); iter++ ) {
cout << iter->first << " is " << (*iter).second << endl;
}

It would output

a is 5
x is 1
z is 1

Is there a way to tell map not to sort by keys or by value but to leave
them in the order in which they were created in the list? Or is there a
way to iterate through a map in the same order they were added to the
map?

Thanks in advance.

Nov 7 '06 #1
Share this Question
Share on Google+
5 Replies


P: n/a

evlong wrote:
My question is about the STL map class and how it sorts data that it
stores. By default (as far as I know) it sorts keys in ascending order
or lexicographically.

If I were to do something like this:

ages["z"] = 1;
ages["a"] = 5;
ages["x"] = 1;

for( map<string, int>::iterator iter = ages.begin(); iter !=
ages.end(); iter++ ) {
cout << iter->first << " is " << (*iter).second << endl;
}

It would output

a is 5
x is 1
z is 1

Is there a way to tell map not to sort by keys or by value but to leave
them in the order in which they were created in the list? Or is there a
way to iterate through a map in the same order they were added to the
map?

Thanks in advance.
No there isn't. A std::map that ceases to order its elements according
to its predicate is undefined behaviour. You could use an incrementing
index key paired with each new element and therefore order the elements
using their insertion order. What you can't do is defeat the
container's purpose.

Which begs the question: why don't you simply use a vector, list or
deque to store elemennts or std::pairs? Sequenced containers do not
order using a predicate.

Nov 7 '06 #2

P: n/a
evlong wrote:
My question is about the STL map class and how it sorts data that it
stores. By default (as far as I know) it sorts keys in ascending order
or lexicographically.

If I were to do something like this:

ages["z"] = 1;
ages["a"] = 5;
ages["x"] = 1;

for( map<string, int>::iterator iter = ages.begin(); iter !=
ages.end(); iter++ ) {
cout << iter->first << " is " << (*iter).second << endl;
}

It would output

a is 5
x is 1
z is 1

Is there a way to tell map not to sort by keys or by value but to leave
them in the order in which they were created in the list?
No.
Or is there a way to iterate through a map in the same order they were
added to the map?
You can play around with the following:

#include <map>
#include <list>
#include <iostream>

template < typename K, typename M >
struct my_map {

typedef std::map<K,MKM_map;
typedef typename KM_map::value_type value_type;
typedef value_type * pointer;
typedef value_type const * const_pointer;
typedef std::list< pointer P_list;
typedef std::map< pointer, typename P_list::iterator P_map;

KM_map the_KM_map;
P_list the_P_list;
P_map the_P_map;
typename KM_map::iterator
insert ( value_type const & value ) {
typename KM_map::iterator iter = the_KM_map.insert( value ).first;
// FIXME: [should use address_of]
pointer ptr = &( *iter );
the_P_list.push_back( ptr );
the_P_map[ ptr ] = -- the_P_list.end();
return ( iter );
}

void erase ( typename KM_map::iterator where ) {
// FIXME: [should use address_of]
pointer ptr = &( *where );
typename P_map::iterator pm_iter = the_P_map.find( ptr );
typename P_list::iterator pl_iter = pm_iter->second;
the_P_list.erase( pl_iter );
the_P_map.erase( pm_iter );
the_KM_map.erase( where );
}

};

typedef my_map<int,int>::KM_map::value_type int_pair;

int main ( void ) {
my_map<int,intim;
im.insert( int_pair( 4, 5 ) );
im.insert( int_pair( 2, 1 ) );
im.insert( int_pair( 3, 1 ) );
im.erase( im.the_KM_map.find( 2 ) );
for ( my_map<int,int>::P_list::const_iterator iter =
im.the_P_list.begin();
iter != im.the_P_list.end(); ++iter ) {
std::cout << (*iter)->first << " " << (*iter)->second << '\n';
}
}
Of course, this is just a proof of concept. You would need to polish the
my_map template so that the internals are hidden and so that it presents a
nice interface.
Best

Kai-Uwe Bux
Nov 7 '06 #3

P: n/a
evlong wrote:
>
Is there a way to tell map not to sort by keys or by value but to leave
them in the order in which they were created in the list? Or is there a
way to iterate through a map in the same order they were added to the
map?
No.

If you don't want sorted data, why not use a std::vector?

--
Ian Collins.
Nov 7 '06 #4

P: n/a
evlong wrote:
Is there a way to tell map not to sort by keys or by value but to leave
them in the order in which they were created in the list? Or is there a
way to iterate through a map in the same order they were added to the
map?
No. If that's what you want, you can use a vector or list of pairs.
--
Clark S. Cox III
cl*******@gmail.com
Nov 7 '06 #5

P: n/a
Clark S. Cox III wrote:
evlong wrote:
Is there a way to tell map not to sort by keys or by value but to
leave them in the order in which they were created in the list? Or
is there a way to iterate through a map in the same order they were
added to the map?

No. If that's what you want, you can use a vector or list of pairs.
That wouldn't really allow you to use it like an associative array,
which is what I gather the OP is after.

Brian
Nov 7 '06 #6

This discussion thread is closed

Replies have been disabled for this discussion.