C++ STL中的set和map

STL中的set和map在某种意义上是相似的，它们都使用红黑树(一种自平衡BST)。注意，搜索、插入和删除的时间复杂度是O(Log n)。

set和map的差异

设置的差异用于仅存储键，而map用于存储键值对。例如，考虑打印已排序的不同元素的问题，我们使用set，因为键需要值。而如果我们将问题更改为打印不同排序元素的频率，则使用map。我们需要map将数组值存储为键，频率存储为值。

// CPP program to demonstrate working of set
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    set<int> s1;
    s1.insert(2);
    s1.insert(5);
    s1.insert(3);
    s1.insert(6);
 
    cout << "Elements in set:\n";
    for (auto it : s1)
        cout << it << " "; // Sorted
 
    return 0;
}

输出:

Elements in set:
2 3 5 6

// CPP program to demonstrate working of map
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    map<int, int> m;
 
    m[1] = 2; // Insertion by indexing
 
    // Direct pair insertion
    m.insert({ 4, 5 });
 
    // Insertion of pair by make_pair
    m.insert(make_pair(8, 5));
 
    cout << "Elements in map:\n";
    for (auto it : m)
        cout << "[ " << it.first << ", "
             << it.second << "]\n"; // Sorted
 
    return 0;
}

输出:

Elements in map:
[ 1, 2]
[ 4, 5]
[ 8, 5]

set和map的变体

Set和Map，都存储惟一值和排序值。但是如果我们没有这样的要求，我们使用multiset/multimap和unordered_set/unordered_map。

Multimap

Multimap不允许通过索引存储元素。

// CPP program to demonstrate working of Multimap
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    multimap<int, int> m;
 
    m.insert({ 1, 2 });
    m.insert({ 2, 3 });
    m.insert({ 4, 5 });
    m.insert({ 2, 3 });
    m.insert({ 1, 2 });
 
    cout << "Elements in Multimap:\n";
    for (auto it : m)
        cout << "[ " << it.first << ", "
             << it.second << "]\n"; // Sorted
 
    return 0;
}

输出:

Elements in Multimap:
[ 1, 2]
[ 1, 2]
[ 2, 3]
[ 2, 3]
[ 4, 5]

Multiset

// CPP program to demonstrate working of Multiset
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    multiset<int> ms;
 
    ms.insert(1);
    ms.insert(3);
    ms.insert(4);
    ms.insert(2);
    ms.insert(2);
 
    cout << "Elements in Multiset:\n";
    for (auto it : ms)
        cout << it << " ";
 
    return 0;
}

输出:

Elements in Multiset:
1 2 2 3 4

Unordered_set

// CPP program to demonstrate working of Unordered_set
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    unordered_set<int> us;
 
    us.insert(1);
    us.insert(3);
    us.insert(4);
    us.insert(2);
    us.insert(2);
 
    cout << "Elements in unordered_set:\n";
    for (auto it : us)
        cout << it << " "; // Sorted
 
    return 0;
}

输出:

Elements in unordered_set:
2 4 1 3

Unordered_map

// CPP program to demonstrate working of Unordered_map
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    unordered_map<int, int> um;
 
    um[1] = 2;
    um[4] = 5;
    um[2] = 3;
    um[8] = 5;
    um[3] = 6;
 
    cout << "Elements in unordered_map:\n";
    for (auto it : um)
        cout << "[ " << it.first << ", " << it.second << "]\n";
 
    return 0;
}

输出:

Elements in unordered_map:
[ 3, 6]
[ 2, 3]
[ 8, 5]
[ 1, 2]
[ 4, 5]

让我们用表格的形式来看看它们的区别: