multimap的三种遍历方式

2020年5月17日下午5:46

总结：

有些统计类型的题目，key->value是一对多的，这时需要使用multimap，关于multimap我总结了三种可能会用到的遍历方式：
1. 对所有元素的遍历，和map效果一样
2. 对包含指定key的元素遍历
3. 结合上面的1和2，对multimap中的所有元素按key进行遍历
这里关键灵活使用multimap的成员函数：
1. equal_range
  1. 返回容器中所有拥有给定关键的元素范围。范围以二个迭代器定义，一个指向首个不小于 key 的元素，另一个指向首个大于 key 的元素。首个迭代器可以换用 lower_bound() 获得，而第二迭代器可换用 upper_bound() 获得。
2. lower_bound()
3. upper_bound()


int main()
{
    std::multimap<int, char> dict {
            {1, 'A'},
            {2, 'B'},
            {2, 'C'},
            {2, 'D'},
            {4, 'E'},
            {3, 'F'}
    };
    // 1.每个元素遍历输出
    cout << "第一种：每个元素遍历输出" << endl;
    for(auto pair : dict) {
        cout << pair.first << " " << pair.second  << endl;
    }

    // 2.指定key，进行遍历
    cout << "第二种:指定key，进行遍历" << endl;
    auto range = dict.equal_range(2); // range的类型是一个pair
    for (auto i = range.first; i != range.second; ++i)
    {
        std::cout << i->first << ": " << i->second << '\n';
    }

    // 3.对multimap中的所有元素按key进行遍历
    cout << "第三种：对multimap中的所有元素按key进行遍历" << endl;
    for(auto it = dict.begin(); it != dict.end(); it = dict.upper_bound(it->first))
    {
        auto range = dict.equal_range(it->first);
        cout << it->first << ":" << endl;
        while(range.first != range.second)
        {
            cout << "   " << range.first->second << endl;
            ++range.first;
        }
    }
}

输出：
第一种：每个元素遍历输出
1 A
2 B
2 C
2 D
3 F
4 E
第二种:指定key，进行遍历
2: B
2: C
2: D
第三种：对multimap中的所有元素按key进行遍历
1:
   A
2:
   B
   C
   D
3:
   F
4:
   E

参考：