Re: insert-ordered-map or keyed-vector?

Tim H wrote:


I don't know of any. Did you check Boost?


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,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 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,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';
  }

}

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