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