C++ STL中 set 和 map 的区别

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

set 和 map 的区别

区别在于 set 仅用于存储键，而 map 用于存储键值对。 例如，考虑打印已排序的不同元素的问题，使用 set 因为键需要值。 如果将问题更改为打印不同排序元素的频率，那么使用 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 << ", "\n            << it.second << "]\n"; // Sorted

    return 0;
}

输出结果：

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

集合和映射的变化：
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 << ", "\n            << 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]