C++ multimap

template < class Key,                                     // multimap::key_type
           class T,                                       // multimap::mapped_type
           class Compare = less<Key>,                     // multimap::key_compare
           class Alloc = allocator<pair<const Key,T> >    // multimap::allocator_type
           > class multimap;

multimap 是关联型容器, 保存<key, value>键值对, 多个value可以由相同的key.
map中的元素根据key和比较器排序.
在对单个元素索引时, 会比unordered_multimap要慢一些.
但是multimap允许按照顺序查找一个子集.

特性

• 关联 Associative: Elements in associative containers are referenced by their key and not by their absolute position in the container.
• 排序 Ordered: The elements in the container follow a strict order at all times.All inserted elements are given a position in this order.
• 键值对 Map: Each element associates a key to a mapped value: Keys are meant to identify the elements whose main content is the mapped value.
• 允许相同键 Multiple equivalent keys: Multiple elements in the container can have equivalent keys.
• Allocator-aware: The container uses an allocator object to dynamically handle its storage needs.

关键成员函数

insert

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
    // type of the collection
    typedef multimap<int,string> IntStringMMap;

    IntStringMMap coll;        // set container for int/string values

    // insert some elements in arbitrary order
    // - a value with key 1 gets inserted twice
    coll.insert(make_pair(5,"tagged"));
    coll.insert(make_pair(2,"a"));
    coll.insert(make_pair(1,"this"));
    coll.insert(make_pair(4,"of"));
    coll.insert(make_pair(6,"strings"));
    coll.insert(make_pair(1,"is"));
    coll.insert(make_pair(3,"multimap"));

    /* print all element values
     * - iterate over all elements
     * - element member second is the value
     */
    IntStringMMap::iterator pos;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        cout << pos->first <<":\t" << pos->second << std::endl;
    }   
    cout << endl;
}  

output

1:  this
1:  is
2:  a
3:  multimap
4:  of
5:  tagged
6:  strings

find

如果一个key对应多个value, 官方文档中并没有指明会按照什么规则返回哪一个value.

// multimap::find
#include <iostream>
#include <map>

int main ()
{
  std::multimap<char,int> mymm;

  mymm.insert (std::make_pair('x',10));
  mymm.insert (std::make_pair('y',20));
  mymm.insert (std::make_pair('z',30));
  mymm.insert (std::make_pair('z',40));

  std::multimap<char,int>::iterator it = mymm.find('x');
  mymm.erase (it);
  mymm.erase (mymm.find('z'));

  // print content:
  std::cout << "elements in mymm:" << '\n';
  std::cout << "y => " << mymm.find('y')->second << '\n';
  std::cout << "z => " << mymm.find('z')->second << '\n';

  return 0;
}

output:

elements in mymm:
y => 20
z => 40

equal_range

pair<const_iterator,const_iterator> equal_range (const key_type& k) const;
pair<iterator,iterator>             equal_range (const key_type& k);

返回key对应的所有元素的起始和结束迭代器.
The function returns a pair, whose member pair::first
is the lower bound of the range (the same as lower_bound), andpair::second
is the upper bound (the same as upper_bound).

区间为上闭下开, 如果没有找到对应的key, 则返回的pair::first和pair::second都指向第一个元素, 此时对应的range的长度为0.

// multimap::equal_range
#include <iostream>
#include <map>

int main ()
{
  std::multimap<char,int> mymm;

  mymm.insert(std::pair<char,int>('a',10));
  mymm.insert(std::pair<char,int>('b',20));
  mymm.insert(std::pair<char,int>('b',30));
  mymm.insert(std::pair<char,int>('b',40));
  mymm.insert(std::pair<char,int>('c',50));
  mymm.insert(std::pair<char,int>('c',60));
  mymm.insert(std::pair<char,int>('d',60));

  std::cout << "mymm contains:\n";
  for (char ch='a'; ch<='d'; ch++)
  {
    std::pair <std::multimap<char,int>::iterator, std::multimap<char,int>::iterator> ret;
    ret = mymm.equal_range(ch);
    std::cout << ch << " =>";
    for (std::multimap<char,int>::iterator it=ret.first; it!=ret.second; ++it)
      std::cout << ' ' << it->second;
    std::cout << '\n';
  }

  return 0;
}

output

mymm contains:
a => 10
b => 20 30 40
c => 50 60
d => 60

更多细节和方法请参考官方文档