集合与关联数组

例题

有序集合std::set

在有序集合中，元素是按顺序排序好的。插入、删除、查找操作的复杂度都是 $\mathcal{O}(\log n)$。有序集合的实现是std::set， 头文件是<set>。

set和数组（包括vector）一样，都是保存一批数据的数据结构。但有一系列不同的地方：

1. 数组读写访问每个元素的时间复杂度是$\mathcal{O}(1)$，而set是$\mathcal{O}(\log n)$。
2. set保证元素的值的唯一性，多次插入同一个值，只会保留一个，而数组没有这个功能。
3. set保证元素的有序性，插入的数据会自动按顺序排列。
4. 数组可以按下标随机访问数据，而set不能。

set可以通过迭代器进行遍历：

set<int> s;
s.insert(1);
s.insert(3);
s.insert(2);
for (auto it = s.begin(); it != s.end(); it++)
    printf("%d\n", *it);

在set中查找和删除元素，使用s.find(x)和s.erase(x)方法，前者返回指向对应元素的迭代器（如果存在），或者s.end()（如果找不到）。

答案 - Distinct Numbers

这里要求我们统计n个整数中一共有多少个不同的数，我们可以用set来完成这个任务。

#include <bits/stdc++.h>
using namespace std;
 
int n;
set<int> s;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        s.insert(a);        // 如果有重复的元素，在set中只会保留一个。
    }
    printf("%d", s.size());
    return 0;
}

无序集合std::unordered_set

set是有序的元素集合，如果问题不需要元素间有顺序，也可以使用std::unordered_set，性能比set更高一些（约2倍速度）。

set在内部使用二叉搜索树实现，而unordered_set使用哈希实现，需要元素有对应的哈希函数。

关联数组std::map

关联数组(map)是一组 键(key)和值(value)的列表，键要求是唯一的，不能有重复，而值可以有重复。map支持以下操作：

• m[key]：返回key对应的值的引用，既可以读取，也可以写入。比如cout << m[key]或者m[key]=5都是可以的。
• 如果对应的键不存在，则访问m[key]会用值的默认构造器来初始化。这个的意思是对于大部分情况，访问不存在的键就会得到默认值。 比如:

  map<int,int> m1;
  cout << m1[1];        // 0   （int的默认值是0）
   
  map<int,vector<int>> m2;
  m2[1].push_back(5);
  cout << m2[1].size() << " " << m2[2].size();  // 1 0     （vector的默认值是空的vector）

• m.count(key)：返回一个键对应的值的个数（0或1），所以可以用来检查一个键是否存在。
• m.erase(key)：删除一个键和对应的值

map的键也是排序的，如果不需要键有序，也可以使用unordered_map。

map的遍历

map<int,int> m;
m[1] = 1;
m[2] = 4;
m[3] = 9;
for (const auto &x: m)  // 标准遍历方法
    printf("%d -> %d\n", x.first, x.second);
for (auto x: m)         // 也可以，但x会做一份复制，稍慢，而且修改x并不会修改map
    printf("%d -> %d\n", x.first, x.second);

多重集合std::multiset和多重关联数组std::multimap

set和map经常使用的另外一个变体是multiset和multimap，区别是multiset允许同一个值存在多个， 而multimap允许同一个键对应多个值。使用这两个数据结构时，有以下经常要注意的地方：

• erase(x)会删除同一个键的所有记录，所以如果只想删除一个，需要写s.erase(s.find(x))。
• count(x)返回值自然可能大于1，而且要注意，count()操作可能是$\mathcal{O}(n)$的，取决于同一个值有多少个，这个坑有时候会导致程序TLE。

习题