极客教程在C++ STL中Multimap与Map的比较及示例
C++ STL中的Map
Map以有序的方式存储唯一的键值对。每个键都与一个可能是唯一的值相关联。键可以插入或删除，但不能被修改。与键相关联的值可以改变。使用键快速访问值是一种很好的方式，它可以在O(1)时间内完成。
#include <iostream>
#include <iterator>
#include <map>
using namespace std;
int main()
{
// 空map容器
map<int, int> gquiz1;
//以随机顺序插入元素
gquiz1.insert(pair<int, int>(1, 40));
gquiz1.insert(pair<int, int>(2, 30));
gquiz1.insert(pair<int, int>(3, 60));
gquiz1.insert(pair<int, int>(4, 20));
gquiz1.insert(pair<int, int>(5, 50));
gquiz1.insert(pair<int, int>(6, 50));
gquiz1.insert(pair<int, int>(7, 10));
//打印map gquiz1
map<int, int>::iterator itr;
cout << "\nThe map gquiz1 is : \n";
cout << "\tKEY\tELEMENT\n";
for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) {
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
cout << endl;
//将gquiz1中的元素赋值给gquiz2
map<int, int> gquiz2(gquiz1.begin(), gquiz1.end());
//打印map gquiz2的所有元素
cout << "\nThe map gquiz2 after"
<< " assign from gquiz1 is : \n";
cout << "\tKEY\tELEMENT\n";
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
cout << endl;
//从gquiz2中删除所有小于键值为3的元素
cout << "\ngquiz2 after removal of"
" elements less than key=3 : \n";
cout << "\tKEY\tELEMENT\n";
gquiz2.erase(gquiz2.begin(), gquiz2.find(3));
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
//删除所有键为4的元素
int num;
num = gquiz2.erase(4);
cout << "\ngquiz2.erase(4) : ";
cout << num << " removed \n";
cout << "\tKEY\tELEMENT\n";
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
cout << endl;
//取下限和上限
//对于map gquiz1中的键=5
cout << "gquiz1.lower_bound(5) : "
<< "\tKEY = ";
cout << gquiz1.lower_bound(5)->first << '\t';
cout << "\tELEMENT = "
<< gquiz1.lower_bound(5)->second << endl;
cout << "gquiz1.upper_bound(5) : "
<< "\tKEY = ";
cout << gquiz1.upper_bound(5)->first << '\t';
cout << "\tELEMENT = "
<< gquiz1.upper_bound(5)->second << endl;
return 0;
}
输出
The map gquiz1 is : KEY ELEMENT 1 40 2 30 3 60 4 20 5 50 6 50 7 10 The map gquiz2 after assign from gquiz1 is : KEY ELEMENT 1 40 2 30 3 60 4 20 5 50 6 50 7 10 gquiz2 after removal of elements less than key=3 : KEY ELEMENT 3 60 4 20 5 50 6 50 7 10 gquiz2.erase(4) : 1 removed KEY ELEMENT 3 60 5 50 6 50 7 10 gquiz1.lower_bound(5) : KEY = 5 ELEMENT = 50 gquiz1.upper_bound(5) : KEY = 6 ELEMENT = 50
C++ STL中的Multimap
Multimap类似于map，但它允许多个元素具有相同的键。同时，键值对不需要在这种情况下是唯一的。关于multimap需要注意的一点是，它总是保持所有键的排序顺序。这些特性使得multimap在竞争编程中非常有用。
#include <iostream>
#include <iterator>
#include <map>
using namespace std;
int main()
{
// 空的multimap容器
multimap<int, int> gquiz1;
// 以随机顺序插入元素
gquiz1.insert(pair<int, int>(1, 40));
gquiz1.insert(pair<int, int>(2, 30));
gquiz1.insert(pair<int, int>(3, 60));
gquiz1.insert(pair<int, int>(6, 50));
gquiz1.insert(pair<int, int>(6, 10));
// 打印multimap gquiz1
multimap<int, int>::iterator itr;
cout << "\nThe multimap gquiz1 is : \n";
cout << "\tKEY\tELEMENT\n";
for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) {
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
cout << endl;
// 随机添加元素以检查已排序的键属性
gquiz1.insert(pair<int, int>(4, 50));
gquiz1.insert(pair<int, int>(5, 10));
// 再次打印multimap gquiz1
cout << "\nThe multimap gquiz1 after"
<< " adding extra elements is : \n";
cout << "\tKEY\tELEMENT\n";
for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) {
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
cout << endl;
// 从gquiz1分配元素到gquiz2
multimap<int, int> gquiz2(gquiz1.begin(),
gquiz1.end());
// 打印multimap gquiz2的所有元素
cout << "\nThe multimap gquiz2 after"
<< " assign from gquiz1 is : \n";
cout << "\tKEY\tELEMENT\n";
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
cout << endl;
// 去除所有键值小于3的元素
cout << "\ngquiz2 after removal of"
<< " elements less than key=3 : \n";
cout << "\tKEY\tELEMENT\n";
gquiz2.erase(gquiz2.begin(), gquiz2.find(3));
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
// 去除所有键为4的元素
int num;
num = gquiz2.erase(4);
cout << "\ngquiz2.erase(4) : ";
cout << num << " removed \n";
cout << "\tKEY\tELEMENT\n";
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
cout << endl;
// multimap gquiz1键=5的下限和上限
cout << "gquiz1.lower_bound(5) : "
<< "\tKEY = ";
cout << gquiz1.lower_bound(5)->first << '\t';
cout << "\tELEMENT = "
<< gquiz1.lower_bound(5)->second
<< endl;
cout << "gquiz1.upper_bound(5) : "
<< "\tKEY = ";
cout << gquiz1.upper_bound(5)->first << '\t';
cout << "\tELEMENT = "
<< gquiz1.upper_bound(5)->second
<< endl;
return 0;
}
输出
multimap gquiz1是：KEY ELEMENT 1 40 2 30 3 60 6 50 6 10 在添加额外元素后的multimap gquiz1为：KEY ELEMENT 1 40 2 30 3 60 4 50 5 10 6 50 6 10 经gquiz1所分配的multimap gquiz2为：KEY ELEMENT 1 40 2 30 3 60 4 50 5 10 6 50 6 10 gquiz2从key = 3开始删除元素后为：KEY ELEMENT 3 60 4 50 5 10 6 50 6 10 gquiz2.erase(4)：1 被删除 KEY ELEMENT 3 60 5 10 6 50 6 10 gquiz1.lower_bound(5)：KEY = 5 ELEMENT = 10 gquiz1.upper_bound(5)：KEY = 6 ELEMENT = 50
时间和空间复杂度：
- 插入元素：每个插入操作的时间复杂度为O(log n)，其中n是multimap中元素的数量。每个插入操作的空间复杂度为O(1)。
- 打印multimap：时间复杂度为O(n)，其中n是multimap中元素的数量。空间复杂度为O(1)。
- 添加元素：每个插入操作的时间复杂度为O(log n)，其中n是multimap中元素的数量。每个插入操作的空间复杂度为O(1)。
- 从一个multimap分配元素到另一个multimap：时间复杂度为O(n)，其中n是被分配的元素的数量。空间复杂度为O(n)，其中n是被分配的元素的数量。
- 移除所有小于某个键的元素：每个操作的时间复杂度为O(log n)，其中n是multimap中元素的数量。每个操作的空间复杂度为O(1)。
- 移除所有特定键的元素：每个操作的时间复杂度为O(log n)，其中n是multimap中元素的数量。每个操作的空间复杂度为O(1)。
- 查找键的lower bound和upper bound：每个操作的时间复杂度为O(log n)，其中n是multimap中元素的数量。每个操作的空间复杂度为O(1)。
- 总的来说，程序的时间复杂度由插入和移除操作以及lower和upper bound操作的对数时间复杂度主导。空间复杂度与被分配的元素数量成线性关系。
C++ STL中Map和Multimap的区别
| S No. | Map | Multimap |
|---|---|---|
| 1 | 它存储唯一的键值对，其中每个键都是唯一的。 | 它可以存储重复的键值对，其中键可能不唯一。 |
| 2 | 在map上使用count()函数只能返回两个值，即0或1。 | 在multimap上使用count()函数可以返回任何非负整数。 |
| 3 | 访问任何键的值很容易，直接可访问。 | 访问任何键的值并不容易，而且无法直接访问。 |
| 4 | 使用键删除时，在map中只会删除一个键值对。 | 使用键删除时，在multimap中将删除具有相同键的所有键值对。 |
| 5 | 当需要快速访问值并使用键作为查找表的唯一索引时，可以使用map作为简单的查找表。 | 当需要使用键对值进行分组时，可以使用multimap。 |