Kai-Uwe Bux wrote:
Naveen wrote:
>I am trying to write a conatiner which has std::map like methods but
preserves the order of insertion.
Try using a map and a vector of iterators into the map. The map does its
thing and after inserting an element into the map, you append its location
to the vector, which then keeps track of the order of insertion. This will
allow you, by adding one level of indirection, to traverse the map in the
order the entries were inserted.
I should remark that this makes deletions a little costly: you need a linear
search in the vector to find the iterator and remove it. Here is an idea
that should to logarithmic time:
#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';
}
}
It's just a proof of concept. Hope it helps.
Best
Kai-Uwe Bux