insert-ordered-map or keyed-vector?

[Tim H]

Is there an STL or similar container that behaves like a map (string
keys or tempate<Tkeykey s with template<Tvalva lues) 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

[Kai-Uwe Bux]

Tim H wrote:

Is there an STL or similar container that behaves like a map (string
keys or tempate<Tkeykey s with template<Tvalva lues) 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_t ype 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::iterato r P_map;

KM_map the_KM_map;
P_list the_P_list;
P_map the_P_map;

typename KM_map::iterato r
insert ( value_type const & value ) {
typename KM_map::iterato r iter = the_KM_map.inse rt( value ).first;
// FIXME: [should use boost::addresso f]
pointer ptr = &( *iter );
the_P_list.push _back( ptr );
the_P_map[ ptr ] = -- the_P_list.end( );
return ( iter );
}

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

};

typedef my_map<int,int> ::KM_map::value _type int_pair;

int main ( void ) {
my_map<int,inti m;
im.insert( int_pair( 4, 5 ) );
im.insert( int_pair( 2, 1 ) );
im.insert( int_pair( 3, 1 ) );
im.erase( im.the_KM_map.f ind( 2 ) );
for ( my_map<int,int> ::P_list::const _iterator iter =
im.the_P_list.b egin();
iter != im.the_P_list.e nd(); ++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