Multimap

multimap 是支持重复元素的map。multimap 内部同样是使用红黑树实现。对元素的搜索、插入和删除具有时间复杂度\(O(log{}N)\)。

与map相比在使用上的不同

multimap<int, int> mltmap1;
mltmap1.emplace(1, 2);
mltmap1.emplace(1, 2);
mltmap1.emplace(3, 4);
mltmap1.emplace(3, 4);
mltmap1.emplace(5, 6);
mltmap1.emplace(5, 6);

// multimap 不支持下标访问，以及 at 成员函数
// multimap 只可以通过迭代器遍历访问
for (auto it = mltmap1.begin(); it != mltmap1.end(); it++) {
    printf("(%d, %d) ", it->first, it->second);
}
printf("\n");

// 对于删除操作
// erase() 传入 key 会删除所有元素
mltmap1.erase(1);
// erase() 传入 find 找到的第一个元素的迭代器指针
auto pos1 = mltmap1.find(3);
if (pos1 != mltmap1.end()) {
    mltmap1.erase(pos1);
}
// 对pos1所指元素实施erase()，会使pos1不再成为一个有效的迭代器，
// 如果此后未对pos重新设值就继续使用pos1，会出现异常。
for (auto pos = mltmap1.begin(); pos != mltmap1.end(); ) {
   if (pos->second == 6) {
       mltmap1.erase(pos);
       pos++; // <---
   } else {
       ++pos;
   }
}


// 返回包含容器中具有给定key的所有元素的范围。
// return-type: pair<const_iterator, const_iterator>
// first: begin, second: end
auto range = map1.equal_range(3);
for (auto it3 = range.first; it3 != range.second; ++it3) {
    printf("it3 (%d, %d)\n", it2->first, it2->second);
}