介于多重映射和向量之间的数据结构

Question

可能的重复：
一个 std::map 跟踪顺序插入？

我正在寻找一个像 std::multimap 一样工作的 STL 容器，但我可以像向量一样按插入顺序访问成员。

例如：

  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;

输出：

a => 100个

=> 75

b => 75

z => 150

预期输出：

a => 100z

=> 150

b => 75

一个=> 75

谢谢。

Answer 1

您可以使用 std::vector; > 为此。另外，您可以使用 std::make_pair 函数来创建配对。这是示例代码：

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

boost 库有一个灵活的多索引容器，可以执行您想要的操作以及更多操作： http://www.boost.org/doc/libs/1_43_0/libs/multi_index/doc/index.html

你可以构建可以顺序访问但也允许 O(log (N)) 快速查找。一开始语法有点不透明，但是一旦你得到了一些东西，这是一项值得的投资，因为该实现将经过 boost 人员和大量普通用户的彻底测试。

Answer 3

除了 std::vector 之外> 正如已经建议的，也许 boost::bimap 对您来说是一个很好的解决方案。

Answer 4

您可以将 multimap 与 list 结合起来。

下面是一个可以执行您想要的操作的容器。对象存储在 multimap 中，附加的 list 存储 multimap 迭代器（只要指向的元素位于容器中，它们就保持有效）。所有操作都具有与 multimap 中相同的复杂性，但 erase 方法除外，该方法的复杂度为 O(n*m)，其中 n是所有元素的数量，m 是删除的元素数量。

#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();
}

如果按插入顺序迭代元素比按键查找更频繁地使用，那么“镜像”这个想法会更优化：将键/值对存储在 list 中（这样我们就可以在插入中迭代order）并具有额外的包含 list 元素迭代器的 multiset（用于按键查找目的）。