Map which maintains order of creation

I once needed an unordered map where the order of insertion was the the order of iteration, and it was suggested to me to use a std::vector of std::map::iterators. Now I have a bunch of code prewritten (thankfully using typedefs) and unfortunately it would be a huge pain to change all of that code. I don't care for efficiency as much as I care for behavior. I have this solution but I am wondering if there is an easier way while still using std::map?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <string>
#include <map>

class IDString : public std::string
{
	unsigned long ID;
	static unsigned long NextID;
public:
	IDString() : ID(NextID++), std::string() {}
	IDString(const IDString &s) : ID(NextID++), std::string(s) {}
	IDString(const std::string &s) : ID(NextID++), std::string(s) {}
	IDString(const char *s) : ID(NextID++), std::string(s) {}
	IDString &operator=(const IDString &s){ std::string::operator=(s); return*this; }
	IDString &operator=(const std::string &s){ std::string::operator=(s); return*this; }
	IDString &operator=(const char *s){ std::string::operator=(s); return*this; }
	bool operator<(const IDString &s) const
	{
		if(*this == s) return std::string(*this) < std::string(s);
		return ID < s.ID;
	}
};
unsigned long IDString::NextID = 0;

int main()
{
	std::map<IDString, int> m;
	m["b"] = 1;
	m["a"] = 2;
	m["b"] = 3;
	for(std::map<IDString, int>::iterator it = m.begin(); it != m.end(); ++it)
	{
		std::cout << it->first << "=" << it->second << std::endl;
	}
	std::cin.ignore();
}
I don't have a C++11 compiler so I can't use std::unordered_map (I tried VC++'s tr1::unordered_map but it sorted in reverse alphabetical order o_o) and using the aforementioned solution of a vector of iterators would involve changing a crapload of code.

The above solution works as I want it to, but I am wondering only if there is something I can fix or if there was a better way to do this with std::map and without having to change too much code?

FYI removing line 19 makes line 30 create a duplicate.
Last edited on
unordered map is, by definition, *unordered*. Any order you may happen to see while iterating through it is a fluke of the implementation and may change without notice.

So yes, if your goal is an associative container which also remembers the order of insertion, your best bet is a map coupled with a sequential container (e.g. vector) of iterators.

Or you could use the boost.multi_index library, something like
1
2
3
4
5
6
7
typedef multi_index_container<
  std::string,
  indexed_by<
    sequenced<>,
    ordered_unique<identity<std::string> >
  >
> text_container;
as in this tutorial example http://www.boost.org/doc/libs/release/libs/multi_index/example/sequenced.cpp
Last edited on
I explicitly specified that I can't change containers.
Your code doesn't work
1
2
3
4
5
6
	bool operator<(const IDString &s) const
	{
		//if(*this == s) return std::string(*this) < std::string(s);
		if( *this==s ) return false; //equivalent
		return ID < s.ID;
	}
So you are indexing by ID.
When you do m["?"]; you create a new IDString that has the biggest ID.
Assumming a binary tree, it will always take the right branch. If you don't happen to cross with the previously inserted, it will create a duplicate.
Aw, you're exactly right. Well, I'm tired of this so I'm just going to go through and fix the code that needs to be fixed to use the vector<iterator> method.

Thanks guys!
A generalized map implementation where one can also iterate in the order of insertion (C++98, does not require code changes other than iterator=>sequence_iterator, begin()=>seq_begin() and end()=>seq.end() ):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <map>
#include <string>
#include <vector>
#include <iostream>

template< typename KEY_TYPE, typename MAPPED_TYPE,
          typename KEY_COMP = std::less<KEY_TYPE>,
          typename ALLOCATOR_TYPE = std::allocator< std::pair<const KEY_TYPE,MAPPED_TYPE> > >
struct mapx : public std::map< KEY_TYPE, MAPPED_TYPE, KEY_COMP, ALLOCATOR_TYPE >
{
   typedef std::map< KEY_TYPE, MAPPED_TYPE, KEY_COMP, ALLOCATOR_TYPE > base ;
   typedef typename base::key_type key_type ;
   typedef typename base::mapped_type mapped_type ;
   typedef typename base::value_type value_type ;
   typedef typename base::iterator iterator ;
   typedef typename base::size_type size_type ;
   // TODO: other typedefs

   // TODO: 3 constructors

   mapped_type& operator[] ( const key_type& key )
   {
       iterator iter = base::find(key) ;
       if( iter != base::end() ) return iter->second ;
       std::pair<iterator,bool> pair = insert( std::make_pair( key, mapped_type() ) ) ;
       return pair.first->second ;
   }

   std::pair<iterator,bool> insert( const value_type& v )
   {
       std::pair<iterator,bool> pair = base::insert(v) ;
       sequence.push_back( pair.first ) ;
       return pair ;
   }

   // TODO: implement
   // template< typename ITERATOR > void insert( ITERATOR begin, ITERATOR end ) ;
   // iterator erase( iterator iter ) ;
   // size_type erase( const key_type& key ) ;
   // void erase( iterator from, iterator till ) ;

   std::vector<iterator> sequence ;

   struct sequence_iterator : std::iterator< std::forward_iterator_tag, mapx::value_type >
   {
       typedef typename std::vector<mapx::iterator>::iterator iterator_base ;

       explicit sequence_iterator( iterator_base i ) : base_iter(i) {}

       value_type& operator* () { return **base_iter ; }
       value_type* operator-> () { return &**this ; }

       sequence_iterator& operator++ () { ++base_iter ; return *this ; }
       sequence_iterator operator++ ( int )
       { sequence_iterator temp = *this ; ++*this ; return temp ; }

       bool operator== ( const sequence_iterator& that ) const
       { return base_iter == that.base_iter ; }
       bool operator!= ( const sequence_iterator& that ) const
       { return !( *this == that ) ; }

       iterator_base base_iter ;
   };

   sequence_iterator seq_begin() { return sequence_iterator( sequence.begin() ) ; }
   sequence_iterator seq_end() { return sequence_iterator( sequence.end() ) ; }

   // TODO: const_sequence_iterator, reverse_sequence_iterator, const_reverse_sequence_iterator
};

int main()
{
    mapx<std::string,int> map ;

    map[ "xyz" ] = 1 ;
    map[ "zzz" ] = 2 ;
    map[ "abc" ] = 3 ;
    map[ "xyz" ] = 4 ;
    map.insert( std::make_pair( "ABCD", 5 ) ) ;
    map[ "pqr" ] = 6 ;
    map.insert( std::make_pair( "ddd", 7 ) ) ;
    map[ "abc" ] = 8 ;

    for( mapx<std::string,int>::sequence_iterator iter = map.seq_begin() ;
         iter != map.seq_end() ; ++iter )
             std::cout << iter->first << ' ' << iter->second << '\n' ;
}

Last edited on
Topic archived. No new replies allowed.