在C++ STL中Multimap与Map的比较及示例

在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。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 教程