set

通常使用自平衡二叉搜索树（例如红黑树）来实现

初始化

1
2
3
set<int> val; // 定义空集合
set<int> val = {6, 10, 5, 1}; // 定义集合并初始化，递增顺序
std::set <data_type, greater<data_type>> set_name; // 递减顺序

方法

  • .begin() 返回 vector 中第一个元素的 iterator
  • .end() 返回 vector 中最后一个元素后面的 iterator
  • .size() 返回 vector 大小
  • .max_size() 返回目前最多能装多少元素
  • .empty() 是否为空
  • .insert(g) 将元素 gg 插入集合
  • .erase(g) 将元素 gg 从集合中移除
  • .find(g) 返回元素 gg 对应的 iterator
  • .count(g) 根据是否存在对应元素返回 11 或 00
  • .lower_bound(g) 找到第一个不小于 gg 的元素的 iterator
  • .upper_bound(g) 找到第一个大于 gg 的元素的 iterator

时间复杂度

插入、删除、查找: O(log⁡N)O(\log N)
创建或清除: O(N)O(N)

multiset

同样基于红黑树实现，和 set 基本相同，仅仅是允许有重复元素。

方法

基本与 set 相同

  • .erase(g) 将所有元素 gg 从集合中移除
  • .erase(it) 将 iterator it 指向的元素移除
  • .count(g) 返回元素 gg 的数量
  • .find(g) 返回第一个元素 gg 对应的 iterator
  • .equal_range(g) 返回一对 iterator，分别指向第一个等于 5 的元素和第一个大于 5 的元素。

map

插入数据方式

1
2
3
4
5
6
7
8
9
map<int, std::string> mymap;
// 使用 insert
mymap.insert(make_pair(1, "one")); 
mymap.insert(pair<int, string>(1, "one"));
mymap.insert({1, "one"});
// 直接插入
mymap[1] = "one";
// 使用 emplace
mymap.emplace(1, "one");

特殊用法

如果创建的 map 为 map<template, int> 的形式，那么即使在 map 中没有插入 key-value pair，直接访问某个不存在的 key，可以正常返回，返回值为 00。例如：

1
2
3
4
5
6
7
map<int, int> tail_val_count;
tail_val_count[prefix_sum[n - 1]]++;
for (int i = n - 2; i >= 0; i--)
{
    count += tail_val_count[prefix_sum[i] + k];
    tail_val_count[prefix_sum[i]]++;
}

multimap

也就是 map 允许 key 相同的数据结构。