C++ Multimap

2025年8月29日 | 阅读11分钟

在 C++ 中，multimap 是 C++ STL（标准模板库）的一部分。Multimap 是像 map 一样的关联容器，它们存储排序的键值对，但与 map 不同的是，map 仅存储唯一的键，而 multimap 可以拥有重复的键。默认情况下，它使用 (<) 运算符来比较键。

例如：一个以员工年龄为键，员工姓名为值的 multimap 可以表示为

键	值
23	Alice
28	John
25	Deep
25	Brendon
23	Trump
27	Biden

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;  

参数

key：要在 multimap 中存储的键数据类型。
type：要在 multimap 中存储的值的数据类型。
compare：一个比较类，它接受两个相同类型的参数 bool 并返回一个值。此参数是可选的，默认值为 less<key>。
alloc：它代表分配器对象的类型。此参数是可选的，默认值为 allocator。

创建 multimap

在 C++ 中，可以使用以下语句轻松创建 multimap

此语法声明了一个名为 mymap 的 multimap，其中每个键的类型为 key_type，每个值的类型为 value_type。在 C++ 中，multimap 的键和对应的值总是作为 pair 插入。我们不能只插入一个键或一个值到 multimap 中。

C++ 创建 Multimap 的示例

让我们举一个例子来说明如何在 C++ 中创建 multimap。

示例

#include <iostream>  
#include <map>  
#include <string>  
  
using namespace std;   //using standard namespace
  
int main()   //main function
{  
    multimap<string, string> m = {  
            {"India","New Delhi"},  
            {"India", "Hyderabad"},  
            {"United Kingdom", "London"},  
            {"United States", "Washington D.C"}  
    };  
      
    cout << "Size of map m: " << m.size() <<endl;      
    cout << "Elements in m: " << endl;  
      
    for (multimap<string, string>::iterator it = m.begin(); it != m.end(); ++it)  
    {  
       cout << "  [" << (*it).first << ", " << (*it).second << "]" << endl;  
    }  
  
    return 0;  
}

编译并运行

输出

Size of map m: 4
Elements in m: 
  [India, New Delhi]
  [India, Hyderabad]
  [United Kingdom, London]
  [United States, Washington D.C]

说明

在此示例中，我们构造了一个国家-首都对的 multimap，其中同一个国家有多个条目。之后，它使用 size() 打印总元素数量，然后通过使用迭代器遍历 multimap 来打印所有键值对。

Multimap 的基本操作

在 C++ STL 的 multimap 容器上可以执行多种操作。其中一些操作如下

插入元素

在 C++ 中，可以通过 insert() 函数将键值对插入 multimap。不支持通过 [] 运算符进行插入，因为单个键可能存在多个元素。

C++ 插入元素示例

让我们举一个例子来说明如何在 C++ multimap 中插入元素。

示例

#include <iostream>
#include <map>
int main() {   //main function
    std::multimap<int, std::string> mm;
    mm.insert(std::pair<int, std::string>(1, "Apple"));
    mm.insert(std::pair<int, std::string>(2, "Banana"));
    mm.insert(std::pair<int, std::string>(1, "Avocado")); 
    
    mm.insert({3, "Cherry"});
    mm.insert({2, "Blueberry"}); 
    
    mm.emplace(4, "Date");
    mm.emplace(3, "Cranberry");  
    std::cout << "Multimap contents:\n";
    for (const auto& pair : mm) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << '\n';
    }
    return 0;
}

编译并运行

输出

Multimap contents:
Key: 1, Value: Apple
Key: 1, Value: Avocado
Key: 2, Value: Banana
Key: 2, Value: Blueberry
Key: 3, Value: Cherry
Key: 3, Value: Cranberry
Key: 4, Value: Date

说明

在此示例中，我们演示了如何使用 C++ 中的 std::multimap 来存储具有重复键的键值对。首先，我们使用 insert（pairs 和 initializer lists）和 emplace 添加元素，然后显示所有元素。由于 multimap 以键排序的方式存储项目并且不消除重复项，因此像 1、2 和 3 这样的键会多次重复出现，并带有不同的值。

访问元素

在 C++ 中，multimap 的成员只能通过迭代器访问。第一个成员可以访问键，第二个成员可以通过 -> 运算符访问值。这里不支持 [] 运算符。我们可以使用 next() 和 advance() 方法来推进迭代器。

但是，第一个和最后一个元素可以直接通过 begin() 和 end() 迭代器访问。

C++ 访问元素示例

让我们举一个例子来说明如何访问 C++ multimap 中的元素。

示例

#include <iostream>
#include <map>
int main() {  //main function
    std::multimap<int, std::string> mm;
    mm.insert({1, "Apple"});
    mm.insert({2, "Banana"});
    mm.insert({1, "Avocado"});
    mm.insert({3, "Cherry"});
    std::cout << "All elements:\n";
    for (const auto& pair : mm) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << '\n';
    }
    std::cout << "\nValues for key 2:\n";
    auto range = mm.equal_range(2);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << '\n';
    }
    return 0;
}

编译并运行

输出

All elements:
Key: 1, Value: Apple
Key: 1, Value: Avocado
Key: 2, Value: Banana
Key: 3, Value: Cherry

Values for key 2:
Banana

说明

在此示例中，我们生成一个 multimap，将多个字符串值映射到整数键。它包含一些元素，打印所有键值对，然后使用 equal_range() 查找并打印键为 2 的所有值。

更新元素

在 C++ 中，我们无法更新 multimap 中元素的键。我们可以通过指向该元素的迭代器来更新值。

C++ 更新元素示例

让我们举一个例子来说明如何在 C++ multimap 中更新元素。

示例

#include <iostream>
#include <map>
int main() {   //main function
    std::multimap<int, std::string> mm;
    mm.insert({1, "Apple"});
    mm.insert({2, "Banana"});
    mm.insert({1, "Avocado"});
    std::cout << "Before update:\n";
    for (const auto& pair : mm) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << '\n';
    }
    auto range = mm.equal_range(2);
    for (auto it = range.first; it != range.second; ++it) {
        if (it->second == "Banana") {
            mm.erase(it);
            mm.insert({2, "Blueberry"});
            break; 
        }
    }
    std::cout << "\nAfter update:\n";
    for (const auto& pair : mm) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << '\n';
    }
    return 0;
}

编译并运行

输出

Before update:
Key: 1, Value: Apple
Key: 1, Value: Avocado
Key: 2, Value: Banana

After update:
Key: 1, Value: Apple
Key: 1, Value: Avocado
Key: 2, Value: Blueberry

说明

在此示例中，我们创建一个 multimap，插入一些键值对，然后打印它们。之后，它检索键为 2 的值“Banana”，删除它，然后插入具有相同键但新值为“Blueberry”的新对。之后，它打印新的 multimap。

遍历元素

在 C++ 中，可以使用基于范围的 for 循环或循环中的 begin() 和 end() 迭代器来遍历 multimap。

C++ 遍历元素示例

让我们举一个例子来说明如何遍历 C++ multimap 中的元素。

示例

#include <iostream>
#include <map>
int main() {  //main function
    std::multimap<int, std::string> mm;
    mm.insert({1, "Apple"});
    mm.insert({2, "Banana"});
    mm.insert({1, "Avocado"});
    mm.insert({3, "Cherry"});
    std::cout << "Traversal using iterator:\n";
    for (std::multimap<int, std::string>::iterator it = mm.begin(); it != mm.end(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << '\n';
    }
    return 0;
}

编译并运行

输出

Traversal using iterator:
Key: 1, Value: Apple
Key: 1, Value: Avocado
Key: 2, Value: Banana
Key: 3, Value: Cherry

说明

在此示例中，我们初始化一个 multimap，添加键值对，然后在一个 for 循环中使用迭代器来遍历并按键的升序输出所有元素。

查找元素

在 C++ 中，multimap 通过 find() 方法支持快速按键查找操作。它返回指向给定键的第一个元素的迭代器。如果给定的键不存在，它将返回 end() 迭代器。

如果我们想搜索所有包含相同键的元素中的特定元素，我们可以搜索 equal_range() 方法返回的范围。

C++ 查找元素示例

让我们举一个例子来说明如何在 C++ multimap 中查找元素。

示例

#include <iostream>
#include <map>
int main() {    //main function
    std::multimap<int, std::string> mm;

// insert key-value pair
    mm.insert({1, "Apple"});
    mm.insert({2, "Banana"});
    mm.insert({1, "Avocado"});
    mm.insert({3, "Cherry"});

//define the key to search
    int keyToFind = 1;
    auto it = mm.find(keyToFind);

    if (it != mm.end()) {
        std::cout << "First occurrence of key " << keyToFind << ": " << it->second << '\n';
        std::cout << "All values for key " << keyToFind << ":\n";
        for (auto rangeIt = it; rangeIt != mm.end() && rangeIt->first == keyToFind; ++rangeIt) {
            std::cout << rangeIt->second << '\n';
        }
    } else {
        std::cout << "Key " << keyToFind << " not found.\n";
    }
    return 0;
}

编译并运行

输出

First occurrence of key 1: Apple
All values for key 1:
Apple
Avocado

说明

在此示例中，我们创建一个 multimap，插入键值对，并使用 find() 函数查找键 1 的第一个值。如果它找到给定的元素，它会显示该元素，然后继续打印具有相同键的其余值。

删除元素

在 C++ 中，可以使用 erase() 函数通过传递键或迭代器来移除 multimap 元素。如果传递键，则会移除具有该特定键的所有元素。如果传递迭代器，则会移除迭代器指向的元素。

C++ 移除元素示例

让我们举一个例子来说明如何在 C++ multimap 中移除元素。

示例

#include <iostream>
#include <map>

int main() {   //main function
    std::multimap<int, std::string> mm;
    mm.insert({1, "Apple"});
    mm.insert({2, "Banana"});
    mm.insert({1, "Avocado"});
    mm.insert({3, "Cherry"});
    mm.
erase(1);
    auto it = mm.begin(); 
    mm.erase(it);
    std::cout << "After removal:\n";
    for (const auto& pair : mm) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << '\n';
    }
    return 0;
}

编译并运行

输出

After removal:
Key: 3, Value: Cherry

说明

在此示例中，我们向 multimap 添加元素，然后通过调用 erase(1) 删除所有键为 1 的条目。之后，它使用迭代器擦除第一个剩余元素。最后，它打印 multimap 的更改内容。

检查 Multimap 的大小

在 C++ 中，我们可以使用 empty() 方法来验证 multimap 是否为空，并使用 size() 方法查找其大小。

empty() 方法返回

True：当 multimap 为空时返回 true。
False：如果 multimap 不为空，则返回 false。

size() 方法返回 multimap 中元素的数量。

C++ 检查 Multimap 大小的示例

让我们举一个例子来说明如何在 C++ 中检查 multimap 的大小。

示例

#include <iostream>
#include <map>

int main() {   //main function
    std::multimap<int, std::string> mm;
    mm.insert({1, "Apple"});
    mm.insert({2, "Banana"});
    mm.insert({1, "Avocado"});
    mm.insert({3, "Cherry"});
    std::cout << "The multimap contains " << mm.size() << " elements.\n";
    if (mm.empty()) {
        std::cout << "The multimap is empty.\n";
    } else {
        std::cout << "The multimap is not empty.\n";
    }
    return 0;
}

编译并运行

输出

The multimap contains 4 elements.
The multimap is not empty.

说明

在此示例中，我们将元素插入 multimap 并使用 size() 打印元素总数。之后，它使用 empty() 检查 multimap 是否为空，并相应地打印结果。

时间复杂度

下表列出了 multimap 操作的时间复杂度

操作	时间复杂度
插入元素	O(log n)
删除元素	O(log n)
访问任意位置的元素。	O(n)
按键查找元素	O(log n)
查找具有特定键的元素数量	O(log n)
遍历 multimap	O(n)

成员函数

以下是 multimap 所有成员函数的列表

构造函数/析构函数

给出的表显示了 C++ Multimap 中使用的各种构造函数/析构函数。

函数	描述
构造函数	构造 multimap
析构函数	Multimap 析构函数
operator=	将 multimap 的元素复制到另一个 multimap。

迭代器

给出的表显示了 C++ Multimap 中使用的各种迭代器函数。

函数	描述
begin	返回指向 multimap 中第一个元素的迭代器。
cbegin	返回指向 multimap 中第一个元素的 const_iterator。
end	返回指向 past-end 的迭代器。
cend	返回指向 past-end 的 const 迭代器。
rbegin	返回指向末尾的反向迭代器。
rend	返回指向开头的反向迭代器。
crbegin	返回指向末尾的 const 反向迭代器。
crend	返回指向开头的 const 反向迭代器。

容量

给出的表显示了 C++ Multimap 中使用的各种容量函数。

函数	描述
empty	如果 multimap 为空，则返回 true。
大小	返回 multimap 中元素的数量。
max_size	返回 multimap 的最大大小。

修饰符

给出的表显示了 C++ Multimap 中使用的各种修改器函数。

函数	描述
insert	将元素插入 multimap。
erase	从 multimap 中擦除元素。
swap	交换 multimap 的内容。
clear	删除 multimap 中的所有元素。
emplace	构造并向 multimap 插入新元素。
emplace_hint	通过提示构造并向 multimap 插入新元素。

观察器

给出的表显示了 C++ Multimap 中使用的各种观察者函数。

函数	描述
key_comp	返回键比较对象的副本。
value_comp	返回值比较对象的副本。

操作

给出的表显示了 C++ Multimap 中执行的各种操作。

函数	描述
find	搜索具有给定键的元素。
count	获取与给定键匹配的元素数量。
lower_bound	返回指向下界的迭代器。
upper_bound	返回指向界限的迭代器。
equal_range()	返回与给定键匹配的元素范围。

分配器

给出的表显示了 C++ Multimap 中使用的分配器函数。

函数	描述
get_allocator	返回用于构造 multimap 的分配器对象。

非成员重载函数

给出的表显示了 C++ Multimap 中使用的非成员重载函数。

函数	描述
operator==	检查两个 multimap 是否相等。
operator!=	检查两个 multimap 是否相等。
operator<	检查第一个 multimap 是否小于另一个。
operator<=	检查第一个 multimap 是否小于或等于另一个。
operator>	检查第一个 multimap 是否大于另一个。
operator>=	检查第一个 multimap 是否大于或等于另一个。
swap()	交换两个 multimap 的元素。

结论

总之，C++ multimap 是一个标准模板库 (STL) 关联容器，它保存具有有序键的键值对，并且允许重复键。它基于自平衡红黑树实现，并提供多种快速操作，包括以对数时间进行插入、删除和查找。

在 C++ 中，multimap 不支持像 map 那样的 [] 运算符，而是通过 insert()、emplace()、find() 和 equal_range() 等函数进行访问。迭代器用于遍历和检索元素。它提供了大量的成员函数来有效管理和适应流行的 STL 功能，例如迭代器、容量测试和元素操作。

C++ Multimap 选择题

1) 关于 C++ 中的 multimap，以下哪个选项是正确的？

它以无序的方式存储键值对
它允许重复键
它不使用任何内部数据结构
键和值是分开存储的

答案：b) 它允许重复键

2) 在 C++ multimap 中，可以使用以下哪个方法插入元素？

add()
push()
insert()
put()

答案：c) insert()

3) 以下哪个函数返回 multimap 中与特定键匹配的元素范围？

equal_range()
find_range()
range()
get_range()

答案：a) equal_range()

4) 在 C++ multimap 中插入元素的复杂度是多少？

O(1)
O(n)
O(n log n)
O(log n)

答案：d) O(log n)

5) 以下哪个方法不能直接访问 multimap 元素？

begin()
find()
[] 运算符
equal_range()

答案：c) [] 运算符

下一个主题C++ 算法函数

← 上一个下一个 →

C++ Multimap

语法

参数

创建 multimap

C++ 创建 Multimap 的示例

示例

Multimap 的基本操作

插入元素

示例

访问元素

示例

更新元素

示例

遍历元素

示例

查找元素

示例

删除元素

示例

检查 Multimap 的大小

示例

时间复杂度

成员函数

构造函数/析构函数

迭代器

容量

修饰符

观察器

操作

分配器

非成员重载函数

C++ Multimap 选择题

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ Multimap

语法

参数

创建 multimap

C++ 创建 Multimap 的示例

示例

Multimap 的基本操作

插入元素

示例

访问元素

示例

更新元素

示例

遍历元素

示例

查找元素

示例

删除元素

示例

检查 Multimap 的大小

示例

时间复杂度