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