复杂度都为常数

a.empty()

判空，空返回 \(1\)，否则为 \(0\)。

a.size()

返回元素个数。

swap(a,b) || a.swap(b)

交换 \(a,b\)，要求 \(a,b\) 同一类型。

以下内容容器适配器没有：

a.begin() || a.cbegin()

返回指向第一个元素的迭代器。

a.end() || a.cend()

返回指向最后一个元素下一个的迭代器。

unordered_multiset 不做详细介绍，类比 multiset 和 unordered_set 可知。

set a

\(a\) 有序，\(T\) 为类型，\(cmp\) 是仿函数（比较函数）默认是 less，\(a\) 中元素不重复。

multiset a

\(a\) 有序，\(T\) 为类型，\(cmp\) 是仿函数（比较函数）默认是 less，\(a\) 中元素可以重复。

unordered_set a

\(a\) 无序，\(T\) 为类型，\(hh\) 是哈希函数，默认是 hash，\(a\) 中元素不重复。

这里以 set 为例，multiset 和 unordered_set 类似。

set a{k1,k2,k3,...,kn}

将 \(k1,k2,k3,...,kn\) 初始化入 \(a\) 中。

set a(b)

将 \(b\) 拷贝进 \(a\)，要求 \(a,b\) 类型一致。

set a(bg,ed)

将 \([bg,ed)\) 拷贝进 \(a\)，\(bg,ed\) 为迭代器。

a.insert(x)

插入一个值 \(x\)。

a.insert(bg,ed)

插入 \([bg,ed)\) 里的所有数，\(bg,ed\) 为迭代器。

a.insert({x1,x2,x3,...,xn})

插入 \(x1,x2,x3,...,xn\) 。

a.erase(pos)

删除 \(pos\) 位置元素，\(pos\) 为迭代器。

a.erase(x)

删除所有等于 \(x\) 的数。

a.erase(bg,ed)

删除 \(a\) 中在 \([bg,ed)\) 的数，\(bg,ed\) 为迭代器。

a.clear()

清空 \(a\)。

a.count(x)

返回 \(a\) 中等于 \(x\) 的个数，在 set 中只为 \(0,1\)。

a.find(x)

返回指向 \(a\) 中等于 \(x\) 的数的一个迭代器，如果没找见，返回 a.end()。

a.lower_bound(x)

返回指向 \(a\) 中第一个大于 \(x\) 的数的迭代器。

a.upper_bound(x)

返回指向 \(a\) 中第一个大于等于 \(x\) 的数的迭代器。

注 ：

\(3\) 和 \(4\) 都是基于二分查找的算法，所以对于 unordered_set 不适用。

如果用 algorithm 的算法，复杂度则是 \(\mathrm O(n)\) 。

set 和 multiset 除了 a.count(x) 都是 \(\mathrm O (\log n)\)

set 的 a.count(x) 是 \(\mathrm O (\log n)\)，但 multiset 是 \(\mathrm O (\log n) + k\) 的，其中 \(k\) 是相同元素个数。

unordered_set 理论都是 \(\mathrm O (1)\)，但可能被卡成 \(\mathrm O (n)\)（因为基于哈希。

unordered_multimap 不做详细介绍，类比 multimap 和 unordered_map 可知。

map a

\(a\) 有序，按键大小排序，\(Tk\) 为键类型，\(Tv\) 为值类型，\(cmp\) 是仿函数（比较函数）默认是 less，\(a\) 中同一个键只对应一个值。

multimap a

\(a\) 有序，按键大小排序，\(Tk\) 为键类型，\(Tv\) 为值类型，\(cmp\) 是仿函数（比较函数）默认是 less，\(a\) 中同一个键可对应多个值。

unordered_set a

\(a\) 无序，\(Tk\) 为键类型，\(Tv\) 为值类型，\(hh\) 是哈希函数，默认是 hash，\(a\) 中同一个键只对应一个值。

这里以 map 为例，multiset 和 unordered_set 类似。

map a{{k1,v1},{k2,v2},{k3,v3},...,{kn,vn}}

将 \(k1:v1,k2:v2,k3:v3,...,kn:vn\) 初始化入 \(a\) 中，\(k\) 是键，\(v\) 是值。

等同于 map a{make_pair(k1,v1),...,make_pair(kn,vn)}

和 map a{pair{k1,v1},...,pair{kn,vn}}

map a(b)

将 \(b\) 拷贝进 \(a\)，要求 \(a,b\) 类型一致。

map a(bg,ed)

将 \([bg,ed)\) 拷贝进 \(a\)，\(bg,ed\) 为迭代器。

multimap 没有通过键查询的操作，因为一个键对应多个值。

a.at(k)

返回 \(a\) 中键 \(k\) 对应的值，如果未找到，返回异常：out_of_range。

a[k]

返回 \(a\) 中键 \(k\) 对应的值，如果未找到，就添加键 \(k\)，值为 \(0\)。

a.insert({k,v})

插入一对键值，分别为 \(k:v\)。

类似初始化，也可用 make_pair() 和 pair{}。

如果键重复，就会插入失败，不会覆盖。

a.insert(bg,ed)

插入 \([bg,ed)\) 里的所有键和值，\(bg,ed\) 为迭代器。

如果键重复，就会插入失败，不会覆盖。

a.insert({{k1,v1},{k2,v2},...,{kn,vn}})

插入 \(n\) 对键值，分别为 \(k1:v1,k2:v2,...,kn:vn\)，其中 \(ki\) 对应 \(vi\)。

类似初始化，也可用 make_pair() 和 pair{}。

如果键重复，就会插入失败，不会覆盖。

a[k]=v

插入一对键值，分别为 \(k:v\)。

如果键重复，会覆盖 当前键所对应的值。

multimap 也不支持这种插入。

a.erase(pos)

删除 \(pos\) 位置元素，\(pos\) 为迭代器。

a.erase(k)

删除所有键等于 \(k\) 的数。

a.erase(bg,ed)

删除 \(a\) 中在 \([bg,ed)\) 的数，\(bg,ed\) 为迭代器。

a.clear()

清空 \(a\)。

a.count(k)

返回 \(a\) 中键等于 \(k\) 的个数，在 map 中只为 \(0,1\)。

a.find(k)

返回指向 \(a\) 中键等于 \(k\) 的数的一个迭代器，如果没找见，返回 a.end()。

a.lower_bound(k)

返回指向 \(a\) 中第一个键大于 \(k\) 的数的迭代器。

a.upper_bound(k)

返回指向 \(a\) 中第一个键大于等于 \(k\) 的数的迭代器。

注 ：

\(3\) 和 \(4\) 都是基于二分查找的算法，所以对于 unordered_map 不适用。

如果用 algorithm 的算法，复杂度则是 \(\mathrm O(n)\) 。

map 和 multimap 除了 a.count(x) 都是 \(\mathrm O (\log n)\)

map 的 a.count(x) 是 \(\mathrm O (\log n)\)，但 multimap 是 \(\mathrm O (\log n) + k\) 的，其中 \(k\) 是相同元素个数。

unordered_map 理论都是 \(\mathrm O (1)\)，但可能被卡成 \(\mathrm O (n)\)（因为基于哈希。

本文来自博客园，作者：xrlong，转载请注明原文链接：https://www.cnblogs.com/xrlong/articles/17237744.html