a data structure between multimap and vector

Question

Possible Duplicate:
A std::map that keep track of the order of insertion?

I'm looking for a STL container that works like std::multimap but i can access the members in order of insertion like vector.

for example:

  multimap<char,int> mymultimap;
  multimap<char,int>::iterator it;

  mymultimap.insert ( pair<char,int>('a',100) );
  mymultimap.insert ( pair<char,int>('z',150) ); 
  mymultimap.insert ( pair<char,int>('b',75) );
  mymultimap.insert ( pair<char,int>('a',75) );

  for ( it=mymultimap.begin() ; it != mymultimap.end(); it++ )
    cout << (*it).first << " => " << (*it).second << endl;

output:

a => 100

a => 75

b => 75

z => 150

expected output:

a => 100

z => 150

b => 75

a => 75

thanks.

Answer 1

You can use std::vector<std::pair<char,int> > for this. Also, you can use std::make_pair function to create a pair. Here is the sample code:

vector<pair<char,int> > v;
    vector<pair<char,int> >::iterator it;

  v.push_back ( make_pair('a',100) );
  v.push_back ( make_pair('z',150) ); 
  v.push_back ( make_pair('b',75) );
  v.push_back ( make_pair('a',75) );

  for ( it=v.begin() ; it != v.end(); it++ )
    cout << (*it).first << " => " << (*it).second << endl;

Answer 2

Other than a std::vector<std::pair<char,int> > as already suggested, maybe boost::bimap would be a good solution for you.

Answer 3

You can combine multimap with list.

Below is a container that do what you want. Objects are stored in a multimap and additional list stores multimap iterators (they stay valid as long as pointed element is in the container). All operations have the same complexity like in multimap except erase methods which are O(n*m) where n is number of all elements and m is number of elements removed.

#include <map>
#include <list>
#include <algorithm>

template <class Key, class T>
class my_map : public std::multimap<Key, T> {
public:
    typedef typename std::multimap<Key, T> multimap_type;

    typedef typename multimap_type::key_type   key_type;
    typedef typename multimap_type::value_type value_type;
    typedef typename multimap_type::size_type  size_type;
    typedef typename multimap_type::iterator   iterator;

    struct order_iterator : std::list<typename multimap_type::iterator>::iterator {
        typedef typename std::list<typename multimap_type::iterator>::iterator iterator_t;

        order_iterator() {}
        order_iterator(const iterator_t &iterator) : iterator_t(iterator) { }

        const std::pair<const Key, T>& operator *  () const { return ***(const iterator_t*)this; }
              std::pair<const Key, T>& operator *  ()       { return ***(      iterator_t*)this; }
        const std::pair<const Key, T>* operator -> () const { return &**this; }
              std::pair<const Key, T>* operator -> ()       { return &**this; }
    };

private:
    std::list<typename multimap_type::iterator> list;
    multimap_type *base() { return this; }

public:
    order_iterator order_begin() { return this->list.begin(); }
    order_iterator order_end() { return this->list.end(); }

    iterator insert(const value_type& x)
    {
        iterator ret = this->base()->insert(x);
        this->list.push_back(ret);
        return ret;
    }

    iterator insert(iterator position, const value_type& x)
    {
        iterator ret = this->base()->insert(position, x);
        this->list.push_back(ret);
        return ret;
    }

    template <class InputIterator>
    void insert(InputIterator first, InputIterator last)
    {
        while (last != first) this->insert(first++);
    }

    void erase(iterator first, iterator last)
    {
        if (first == this->end()) return;

        for (iterator it = first; it != last; ++it) {
            this->list.erase(std::find(this->list.begin(), this->list.end(), it));
        }
    }

    void erase(iterator position)
    {
        iterator last = position;
        this->erase(position, ++last);
    }

    size_type erase (const key_type& x)
    {
        iterator range_begin = this->lower_bound(x);
        if (range_begin == this->end()) return 0;

        size_type ret = 0;
        iterator range_end = range_begin;
        do range_end++, ret++; while (range_end != this->end() && range_end->first == x);

        this->base()->erase(range_begin, range_end);
        for (; range_begin != range_end; range_begin++) {
            this->list.erase(std::find(this->list.begin(), this->list.end(), range_begin));
        }

        return ret;
    }

    void clear()
    {
        this->list.clear();
        this->base()->clear();
    }
};

#include <iostream>
using namespace std;

my_map<char,int> mymultimap;

void dump()
{
    cout << "by insert:\n";
    for (
        my_map<char,int>::order_iterator it = mymultimap.order_begin();
        it != mymultimap.order_end();
        it++
    ) {
        cout << (*it).first << " => " << (*it).second << endl;
    }

    cout << "by key:\n";
    for (
        my_map<char,int>::iterator it = mymultimap.begin();
        it != mymultimap.end();
        it++
    ) {
        cout << (*it).first << " => " << (*it).second << endl;
    }

    cout << endl;
}

int main()
{
    mymultimap.insert(make_pair('a',100));
    mymultimap.insert(make_pair('z',150));
    mymultimap.insert(make_pair('b',75));
    mymultimap.insert(make_pair('a',75));
    dump();

    mymultimap.erase('a');
    dump();
}

If iterating elements in insertion order is more intensively used then lookup by a key then it would be more optimal to "mirror" the idea: store key/value pairs in a list (so we can iterate in insertion order) and have additional multiset containing iterators to list elements (for by-key-lookup purposes).

Answer 4

The boost libraries have a flexible multiple index container that does what you want and more: http://www.boost.org/doc/libs/1_43_0/libs/multi_index/doc/index.html

You can construct multi_index containers that can be accessed sequentially but also allow O(log(N)) fast lookup. The syntax is a little opaque to start off with, but once you get something working it's a worthwhile investment as the implementation will have been thoroughly tested by the boost guys and a large number of general users.