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

insert-ordered-map or keyed-vector?

P: n/a
Is there an STL or similar container that behaves like a map (string
keys or tempate<Tkeykeys with template<Tvalvalues) but can be
iterated in insert order?

I whipped up a keyed-vector as a wrapper around vector, but I can't
help think there's a better answer already implemented...

Tim

Mar 17 '07 #1
Share this Question
Share on Google+
1 Reply


P: n/a
Tim H wrote:
Is there an STL or similar container that behaves like a map (string
keys or tempate<Tkeykeys with template<Tvalvalues) but can be
iterated in insert order?
I don't know of any. Did you check Boost?

I whipped up a keyed-vector as a wrapper around vector, but I can't
help think there's a better answer already implemented...
I once posted this proof of concept when a similar question was asked.
Maybe, it can serve as a starting point for you. One would need to turn
this into a little container:

#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 boost::addressof]
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 boost::addressof]
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';
}

}

I should remark that if you don't have to deal with erase(), then a simpler
implementation is better: you can just use a list of iterators into the map
to keep track of the insertion order. The detour via pointers and an
additional mapping from pointers to list-iterators is to speed up
deletions.

Best

Kai-Uwe Bux

Mar 17 '07 #2

This discussion thread is closed

Replies have been disabled for this discussion.