STL map class ordering

E

evlong

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.
 
S

Salt_Peter

evlong said:
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.
 
K

Kai-Uwe Bux

evlong said:
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,M> KM_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,int> im;
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
 
I

Ian Collins

evlong said:
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?
 
C

Clark S. Cox III

evlong said:
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.
 
D

Default User

Clark said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top