STL 容器库

概述

容器库是类模板与算法的汇集,允许程序员简单地访问常见数据结构,例如队列、链表和栈。有三类容器——顺序容器、关联容器和无序关联容器——每种都被设计为支持不同组的操作。

容器管理为其元素分配的存储空间,并提供直接或间接地通过迭代器(拥有类似指针属性的对象)访问它们的函数。

大多数容器拥有至少几个常见的成员函数,并共享功能。特定应用的最佳容器不仅依赖于提供的功能,还依赖于对于不同工作量的效率。

按照分类,有以下几类容器:

  • 顺序容器:顺序容器实现能按顺序访问的数据结构。array,vector,deque,forward_list,list
  • 关联容器:关联容器实现能快速查找( O(log n) 复杂度)的数据结构。set,map,multiset,multimap
  • 无序关联容器:无序关联容器提供能快速查找(均摊 O(1) ,最坏情况 O(n) 的复杂度)的无序(哈希)数据结构。unordered_set,unordered_map,unordered_multiset,unordered_multimap
  • 容器适配器:容器适配器提供顺序容器的不同接口。stack,queue,priority_queue
  • span:span 是相接的对象序列上的非占有视图,某个其他对象占有序列的存储。

array(C++11 起)

定义于头文件<array>

1
template<class T, std::size_t N> struct array;

std::array 是封装固定大小数组的容器。

此容器是一个聚合类型,其语义等同于保有一个 C 风格数组 T[N] 作为其唯一非静态数据成员的结构体。不同于 C 风格数组,它不会自动退化成 T* 。它能作为聚合类型聚合初始化,只要有至多 N 个能转换成 T 的初始化器: std::array<int, 3> a = {1,2,3};

该结构体结合了 C 风格数组的性能和可访问性和容器的优点,譬如知晓其大小、支持赋值、随机访问等。

std::array 满足容器 (Container) 和可逆容器 (ReversibleContainer) 的要求,除了默认构造的 array 是非空的,及交换的复杂度是线性,它满足相接容器 (ContiguousContainer) 的要求并 (C++17 起)部分满足顺序容器 (SequenceContainer) 的要求。

零长 array ( N == 0 )有特殊情况。该情况下, array.begin() == array.end() ,并拥有某个唯一值。在零长 array 上调用 front() 或 back() 的效应是未定义的。

亦可将 array 当做拥有 N 个同类型元素的元组。

成员类型

成员类型 定义
value_type T
size_type std::size_t
difference_type std::ptrdiff_t
reference value_type&
const_reference const value_type&
pointer value_type*
const_pointer const value_type*
iterator 随机访问迭代器 (LegacyRandomAccessIterator) 兼常表达式迭代器 (ConstexprIterator) (C++20 起)且为字面类型 (LiteralType) (C++17 起)
const_iterator 常随机访问迭代器兼常表达式迭代器 (ConstexprIterator) (C++20 起)且为字面类型 (LiteralType) (C++17 起)
reverse_iterator std::reverse_iterator
const_reverse_iterator std::reverse_iterator<const_iterator>

隐式定义的成员函数

方法 说明
(构造函数)(隐式声明) 遵循聚合初始化的规则初始化 array (注意默认初始化可以导致非类的 T 的不确定值)
(析构函数)(隐式声明) 销毁 array 的每个元素
operator=(隐式声明) 以来自另一 array 的每个元素重写 array 的对应元素

元素访问

方法 说明
at 访问指定的元素,同时进行越界检查
operator[] 访问指定的元素
front 访问第一个元素
back 访问最后一个元素
data 返回指向内存中数组第一个元素的指针

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器
rbegin
crbegin
返回指向容器最后元素的逆向迭代器
rend
crend
返回指向前端的逆向迭代器

容量

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数

操作

方法 说明
fill 以指定值填充容器
swap 交换内容
operator==
operator!=
operator<
operator<=
operator>
operator>=
按照字典顺序比较 array 中的值 (函数模板)
std::get(std::array) 访问 array 的一个元素 (函数模板)
std::swap(std::array)(C++11) 特化 std::swap 算法 (函数模板)
std::tuple_size<std::array> 获得 array 的大小 (类模板特化)
std::tuple_element<std::array> 获得 array 元素的类型 (类模板特化)
make_array 创建 std::array 对象,从参数推导出其大小和可选的元素类型 (函数模板)
to_array 从内建数组创建 std::array 对象 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <string>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <array>

int main()
{
// 用聚合初始化构造
std::array<int, 3> a1{ {1, 2, 3} }; // CWG 1270 重申前的 C++11 中要求双花括号
// ( C++11 之后的版本和 C++14 起不要求)
std::array<int, 3> a2 = {1, 2, 3}; // = 后决不要求
std::array<std::string, 2> a3 = { std::string("a"), "b" };

// 支持容器操作
std::sort(a1.begin(), a1.end());
std::reverse_copy(a2.begin(), a2.end(), std::ostream_iterator<int>(std::cout, " "));

std::cout << '\n';

// 支持带范围 for 循环
for(const auto& s: a3)
std::cout << s << ' ';
}

vector

动态的相接数组

定义于头文件 <vector>

1
2
3
4
5
6
7
8
9
10
template<
class T,
class Allocator = std::allocator<T>
> class vector;
(1)
namespace pmr {
template <class T>
using vector = std::vector<T, std::pmr::polymorphic_allocator<T>>;
}
(2)

(2) (C++17 起)
1) std::vector 是封装动态数组的顺序容器。
2) std::pmr::vector 是使用多态分配器的模板别名。
元素相继存储,这意味着不仅可通过迭代器,还能用指向元素的常规指针访问元素。这意味着指向 vector 元素的指针能传递给任何期待指向数组元素的指针的函数。

(C++03 起)
vector 的存储是自动管理的,按需扩张收缩。 vector 通常占用多于静态数组的空间,因为要分配更多内存以管理将来的增长。 vector 所用的方式不在每次插入元素时,而只在额外内存耗尽时重分配。分配的内存总量可用 capacity() 函数查询。额外内存可通过对 shrink_to_fit() 的调用返回给系统。 (C++11 起)

重分配通常是性能上有开销的操作。若元素数量已知,则 reserve() 函数可用于消除重分配。

vector 上的常见操作复杂度(效率)如下:

  • 随机访问——常数 O(1)
  • 在末尾插入或移除元素——均摊常数 O(1)
  • 插入或移除元素——与到 vector 结尾的距离成线性 O(n)
  • std::vector (对于 bool 以外的 T )满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、顺序容器 (SequenceContainer) 、相接容器 (ContiguousContainer) (C++17 起)及可逆容器 (ReversibleContainer) 的要求。

特化

方法 说明
vector<bool> 标准库提供 std::vector 对类型 bool 的特化,它可能为空间效率优化。节省空间的动态bitset

成员类型

成员类型 定义
value_type T
allocator_type Allocator
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
reference Allocator::reference(C++11 前)
value_type&(C++11 起)
const_reference Allocator::const_reference(C++11 前)
const value_type&(C++11 起)
pointer Allocator::pointer(C++11 前)
std::allocator_traits::pointer(C++11 起)
const_pointer Allocator::const_pointer(C++11 前)
std::allocator_traits::const_pointer(C++11 起)
iterator 随机访问迭代器 (LegacyRandomAccessIterator)
const_iterator 常随机访问迭代器
reverse_iterator std::reverse_iterator
const_reverse_iterator std::reverse_iterator<const_iterator>

构造函数

构造函数 定义
(构造函数) 构造 vector
(析构函数) 析构 vector
operator= 赋值给容器
assign 将值赋给容器
get_allocator 返回相关的分配器

元素访问

方法 说明
at 访问指定的元素,同时进行越界检查
operator[] 访问指定的元素
front 访问第一个元素
back 访问最后一个元素
data 返回指向内存中数组第一个元素的指针

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器
rbegin
crbegin
返回指向容器最后元素的逆向迭代器
rend
crend
返回指向前端的逆向迭代器

容量

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数
reserve 预留存储空间
capacity 返回当前存储空间能够容纳的元素数
shrink_to_fit(C++11) 通过释放未使用的内存减少内存的使用

修改器

方法 说明
clear 清除内容
insert 插入元素
emplace(C++11) 原位构造元素
erase 擦除元素
push_back 将元素添加到容器末尾
emplace_back(C++11) 在容器末尾就地构造元素
pop_back 移除末元素
resize 改变容器中可存储元素的个数
swap 交换内容
operator==
operator!=
operator<
operator<=
operator>
operator>=
按照字典顺序比较 vector 中的值 (函数模板)
std::swap(std::vector) 特化 std::swap 算法 (函数模板)
erase(std::vector)
erase_if(std::vector)(C++20)
擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>

int main()
{
// 创建含有整数的 vector
std::vector<int> v = {7, 5, 16, 8};

// 添加二个整数到 vector
v.push_back(25);
v.push_back(13);

// 迭代并打印 vector 的值
for(int n : v) {
std::cout << n << '\n';
}
}

deque

双端队列

定义于头文件 <deque>

1
2
3
4
5
6
7
8
9
10
template<
class T,
class Allocator = std::allocator<T>
> class deque;
(1)
namespace pmr {
template <class T>
using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>;
}
(2)

(2) (C++17 起)
std::deque ( double-ended queue ,双端队列)是有下标顺序容器,它允许在其首尾两段快速插入及删除。另外,在 deque 任一端插入或删除不会非法化指向其余元素的指针或引用。

与 std::vector 相反, deque 的元素不是相接存储的:典型实现用单独分配的固定大小数组的序列,外加额外的登记,这表示下标访问必须进行二次指针解引用,与之相比 vector 的下标访问只进行一次。

deque 的存储按需自动扩展及收缩。扩张 deque 比扩展 std::vector 便宜,因为它不涉及到复制既存元素到新内存位置。另一方面, deque 典型地拥有较大的最小内存开销;只保有一个元素的 deque 必须分配其整个内部数组(例如 64 位 libstdc++ 上为对象大小 8 倍; 64 位 libc++ 上为对象大小 16 倍或 4096 字节的较大者)。

deque 上常见操作的复杂度(效率)如下:

  • 随机访问——常数 O(1)
  • 在结尾或起始插入或移除元素——常数 O(1)
  • 插入或移除元素——线性 O(n)
  • std::deque 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、顺序容器 (SequenceContainer) 和可逆容器 (ReversibleContainer) 的要求。

成员类型

成员类型 定义
value_type T
allocator_type Allocator
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
reference Allocator::reference(C++11 前)
value_type&(C++11 起)
const_reference Allocator::const_reference(C++11 前)
const value_type&(C++11 起)
pointer Allocator::pointer(C++11 前)
std::allocator_traits::pointer(C++11 起)
const_pointer Allocator::const_pointer(C++11 前)
std::allocator_traits::const_pointer(C++11 起)
iterator 随机访问迭代器 (LegacyRandomAccessIterator)
const_iterator 常随机访问迭代器
reverse_iterator std::reverse_iterator
const_reverse_iterator std::reverse_iterator<const_iterator>

构造函数

构造函数 定义
(构造函数) 构造 deque
(析构函数) 析构 deque
operator= 赋值给容器
assign 将值赋给容器
get_allocator 返回相关的分配器

元素访问

方法 说明
at 访问指定的元素,同时进行越界检查
operator[] 访问指定的元素
front 访问第一个元素
back 访问最后一个元素

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器
rbegin
crbegin
返回指向容器最后元素的逆向迭代器
rend
crend
返回指向前端的逆向迭代器

容量

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数
shrink_to_fit(C++11) 通过释放未使用的内存减少内存的使用

修改器

方法 说明
clear 清除内容
insert 插入元素
emplace(C++11) 原位构造元素
erase 擦除元素
push_back 将元素添加到容器末尾
emplace_back(C++11) 在容器末尾就地构造元素
pop_back 移除末元素
push_front 插入元素到容器起始
emplace_front(C++11) 在容器头部就地构造元素
pop_front 移除首元素
resize 改变容器中可存储元素的个数
swap 交换内容
operator==
operator!=
operator<
operator<=
operator>
operator>=
按照字典顺序比较 deque 中的值 (函数模板)
std::swap(std::deque) 特化 std::swap 算法 (函数模板)
erase(std::deque)
erase_if(std::deque)(C++20)
擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <deque>

int main()
{
// 创建容纳整数的 deque
std::deque<int> d = {7, 5, 16, 8};

// 从 deque 的首尾添加整数
d.push_front(13);
d.push_back(25);

// 迭代并打印 deque 的值
for(int n : d) {
std::cout << n << '\n';
}
}

forward_list(C++11 起)

单链表

定义于头文件 <forward_list>

1
2
3
4
5
6
7
8
9
10
template<
class T,
class Allocator = std::allocator<T>
> class forward_list;
(1) (C++11 起)
namespace pmr {
template <class T>
using forward_list = std::forward_list<T, std::pmr::polymorphic_allocator<T>>;
}
(2)

(2) (C++17 起)
std::forward_list 是支持从容器中的任何位置快速插入和移除元素的容器。不支持快速随机访问。它实现为单链表,且实质上与其在 C 中实现相比无任何开销。与 std::list 相比,此容器提在不需要双向迭代时提供更有效地利用空间的存储。

在链表内或跨数个链表添加、移除和移动元素,不会非法化当前指代链表中其他元素的迭代器。然而,在从链表移除元素(通过 erase_after )时,指代对应元素的迭代器或引用会被非法化。

std::forward_list 满足容器 (Container) (除了 operator== 的复杂度始终为线性和 size 函数)、具分配器容器 (AllocatorAwareContainer) 和顺序容器 (SequenceContainer) 的要求。

成员类型

成员类型 定义
value_type T
allocator_type Allocator
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
reference value_type&
const_reference const value_type&
pointer std::allocator_traits::pointer
const_pointer std::allocator_traits::const_pointer
iterator 向前迭代器 (LegacyForwardIterator)
const_iterator 常向前迭代器

构造函数

构造函数 定义
(构造函数) 构造 forward_list
(析构函数) 析构 forward_list
operator= 赋值给容器
assign 将值赋给容器
get_allocator 返回相关的分配器

元素访问

方法 说明
front 访问第一个元素

迭代器

方法 说明
before_begin
cbefore_begin
返回指向第一个元素之前迭代器
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器

容量

方法 说明
empty 检查容器是否为空
max_size 返回可容纳的最大元素数

修改器

方法 说明
clear 清除内容
insert_after 在某个元素后插入新元素
emplace_after 在元素后原位构造元素
erase_after 擦除元素后的元素
push_front 插入元素到容器起始
emplace_front 在容器头部就地构造元素
pop_front 移除首元素
resize 改变容器中可存储元素的个数
swap 交换内容

操作

方法 说明
merge 合并二个已排序列表
splice_after 从另一 forward_list 移动元素
remove
remove_if
移除满足特定标准的元素
reverse 将该链表的所有元素的顺序反转
unique 删除连续的重复元素
sort 对元素进行排序
operator==
operator!=
operator<
operator<=
operator>
operator>=
按照字典顺序比较 forward_list 中的值 (函数模板)
std::swap(std::forward_list)(C++11) 特化 std::swap 算法 (函数模板)
erase(std::forward_list)
erase_if(std::forward_list)(C++20)
擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <forward_list>
#include <string>
#include <iostream>

template<typename T>
std::ostream& operator<<(std::ostream& s, const std::forward_list<T>& v) {
s.put('[');
char comma[3] = {'\0', ' ', '\0'};
for (const auto& e : v) {
s << comma << e;
comma[0] = ',';
}
return s << ']';
}

int main()
{
// c++11 初始化器列表语法:
std::forward_list<std::string> words1 {"the", "frogurt", "is", "also", "cursed"};
std::cout << "words1: " << words1 << '\n';

// words2 == words1
std::forward_list<std::string> words2(words1.begin(), words1.end());
std::cout << "words2: " << words2 << '\n';

// words3 == words1
std::forward_list<std::string> words3(words1);
std::cout << "words3: " << words3 << '\n';

// words4 为 {"Mo", "Mo", "Mo", "Mo", "Mo"}
std::forward_list<std::string> words4(5, "Mo");
std::cout << "words4: " << words4 << '\n';
}

list

双链表

定义于头文件 <list>

1
2
3
4
5
6
7
8
9
10
template<
class T,
class Allocator = std::allocator<T>
> class list;
(1)
namespace pmr {
template <class T>
using list = std::list<T, std::pmr::polymorphic_allocator<T>>;
}
(2)

(2) (C++17 起)
std::list 是支持常数时间从容器任何位置插入和移除元素的容器。不支持快速随机访问。它通常实现为双向链表。与 std::forward_list 相比,此容器提供双向迭代但在空间上效率稍低。

在 list 内或在数个 list 间添加、移除和移动元素不会非法化迭代器或引用。迭代器仅在对应元素被删除时非法化。

std::list 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、顺序容器 (SequenceContainer) 及可逆容器 (ReversibleContainer) 的要求。

成员类型

成员类型 定义
value_type T
allocator_type Allocator
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
reference Allocator::reference(C++11 前)
value_type&(C++11 起)
const_reference Allocator::const_reference(C++11 前)
const value_type&(C++11 起)
pointer Allocator::pointer(C++11 前)
std::allocator_traits::pointer(C++11 起)
const_pointer Allocator::const_pointer(C++11 前)
std::allocator_traits::const_pointer(C++11 起)
iterator 双向迭代器 (LegacyBidirectionalIterator)
const_iterator 常双向迭代器
reverse_iterator std::reverse_iterator
const_reverse_iterator std::reverse_iterator<const_iterator>

构造函数

构造函数 定义
(构造函数) 构造 list
(析构函数) 析构 list
operator= 赋值给容器
assign 将值赋给容器
get_allocator 返回相关的分配器

元素访问

方法 说明
front 访问第一个元素
back 访问最后一个元素

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器
rbegin
crbegin
返回指向容器最后元素的逆向迭代器
rend
crend
返回指向前端的逆向迭代器

容量

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数

修改器

方法 说明
clear 清除内容
insert 插入元素
emplace(C++11) 原位构造元素
erase 擦除元素
push_back 将元素添加到容器末尾
emplace_back(C++11) 在容器末尾就地构造元素
pop_back 移除末元素
push_front 插入元素到容器起始
emplace_front(C++11) 在容器头部就地构造元素
pop_front 移除首元素
resize 改变容器中可存储元素的个数
swap 交换内容

操作

方法 说明
merge 合并二个已排序列表
splice 从另一个list中移动元素
remove
remove_if
移除满足特定标准的元素
reverse 将该链表的所有元素的顺序反转
unique 删除连续的重复元素
sort 对元素进行排序
operator==
operator!=
operator<
operator<=
operator>
operator>=
按照字典顺序比较 list 中的值 (函数模板)
std::swap(std::list) 特化 std::swap 算法 (函数模板)
erase(std::list)
erase_if(std::list)(C++20)
擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <algorithm>
#include <iostream>
#include <list>

int main()
{
// 创建含整数的 list
std::list<int> l = { 7, 5, 16, 8 };

// 添加整数到 list 开头
l.push_front(25);
// 添加整数到 list 结尾
l.push_back(13);

// 以搜索插入 16 前的值
auto it = std::find(l.begin(), l.end(), 16);
if (it != l.end()) {
l.insert(it, 42);
}

// 迭代并打印 list 的值
for (int n : l) {
std::cout << n << '\n';
}
}

set

唯一键的集合,按照键排序

定义于头文件 <set>

1
2
3
4
5
6
7
8
9
10
11
template<
class Key,
class Compare = std::less<Key>,
class Allocator = std::allocator<Key>
> class set;
(1)
namespace pmr {
template <class Key, class Compare = std::less<Key>>
using set = std::set<Key, Compare, std::pmr::polymorphic_allocator<Key>>;
}
(2)

(2) (C++17 起)
std::set 是关联容器,含有 Key 类型对象的已排序集。用比较函数 Compare 进行排序。搜索、移除和插入拥有对数复杂度。 set 通常以红黑树实现。

在每个标准库使用比较 (Compare) 概念的场所,用等价关系确定唯一性。不精确地说,若二个对象 a 与 b 相互间既不比较大于亦不比较小于: !comp(a, b) && !comp(b, a) ,则认为它们等价。

std::set 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、关联容器 (AssociativeContainer) 和可逆容器 (ReversibleContainer) 的要求。

成员类型

成员类型 定义
key_type Key
value_type Key
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
key_compare Compare
value_compare Compare
allocator_type Allocator
reference Allocator::reference(C++11 前)
value_type&(C++11 起)
const_reference Allocator::const_reference(C++11 前)
const value_type&(C++11 起)
pointer Allocator::pointer(C++11 前)
std::allocator_traits::pointer(C++11 起)
const_pointer Allocator::const_pointer(C++11 前)
std::allocator_traits::const_pointer(C++11 起)
iterator 常双向迭代器 (LegacyBidirectionalIterator)
const_iterator 常双向迭代器
reverse_iterator std::reverse_iterator
const_reverse_iterator std::reverse_iterator<const_iterator>
node_type(C++17 起) 表示容器结点的结点把柄特化
insert_return_type(C++17 起) 描述插入 node_type 结果的类型,下列类型的特化 template struct { Iter position; bool inserted; NodeType node;}; ,以模板实参 iterator 和 node_type 实例化。

构造函数

构造函数 定义
(构造函数) 构造 set
(析构函数) 析构 set
operator= 赋值给容器
get_allocator 返回相关的分配器

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器
rbegin
crbegin
返回指向容器最后元素的逆向迭代器
rend
crend
返回指向前端的逆向迭代器

容量

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数

修改器

方法 说明
clear 清除内容
insert 插入元素或结点 (C++17 起)
emplace(C++11) 原位构造元素
emplace_hint(C++11) 使用提示原位构造元素
erase 擦除元素
swap 交换内容
extract(C++17) 从另一容器释出结点
merge(C++17) 从另一容器接合结点

查找

方法 说明
count 返回匹配特定键的元素数量
find 寻找带有特定键的元素
contains(C++20) 检查容器是否含有带特定关键的元素
equal_range 返回匹配特定键的元素范围
lower_bound 返回指向首个不小于给定键的元素的迭代器
upper_bound 返回指向首个大于给定键的元素的迭代器

观察器

方法 说明
key_comp 返回用于比较键的函数
value_comp 返回用于在value_type类型的对象中比较键的函数。
operator==
operator!=
operator<
operator<=
operator>
operator>=
按照字典顺序比较 set 中的值 (函数模板)
std::swap(std::set) 特化 std::swap 算法 (函数模板)
erase_if(std::set)(C++20) 擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <string>
#include <set>
#include <cmath>

struct Point { double x, y; };
struct PointCmp {
bool operator()(const Point& lhs, const Point& rhs) const {
return std::hypot(lhs.x, lhs.y) < std::hypot(rhs.x, rhs.y);
}
};

int main()
{
// (1) 默认初始化器
std::set<std::string> a;
a.insert("cat");
a.insert("dog");
a.insert("horse");
for(auto& str: a) std::cout << str << ' ';
std::cout << '\n';

// (2) 迭代器初始化器
std::set<std::string> b(a.find("dog"), a.end());
for(auto& str: b) std::cout << str << ' ';
std::cout << '\n';

// (3) 复制构造函数
std::set<std::string> c(a);
c.insert("another horse");
for(auto& str: c) std::cout << str << ' ';
std::cout << '\n';

// (4) 移动构造函数
std::set<std::string> d(std::move(a));
for(auto& str: d) std::cout << str << ' ';
std::cout << '\n';
std::cout << "moved-from set is ";
for(auto& str: a) std::cout << str << ' ';
std::cout << '\n';

// (5) initializer_list 构造函数
std::set<std::string> e {"one", "two", "three", "five", "eight"};
for(auto& str: e) std::cout << str << ' ';
std::cout << '\n';

// 自定义比较
std::set<Point, PointCmp> z = {{2, 5}, {3, 4}, {1, 1}};
z.insert({1, -1}); // 这会失败,因为 1,-1 的长度等于 1,1
for(auto& p: z) std::cout << '(' << p.x << ',' << p.y << ") ";
std::cout << '\n';
}

map

键值对的集合,按照键排序,键是唯一的

定义于头文件 <map>

1
2
3
4
5
6
7
8
9
10
11
12
13
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T> >
> class map;
(1)
namespace pmr {
template <class Key, class T, class Compare = std::less<Key>>
using map = std::map<Key, T, Compare,
std::pmr::polymorphic_allocator<std::pair<const Key,T>>>
}
(2)

(2) (C++17 起)
std::map 是有序键值对容器,它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树

在每个标准库使用比较 (Compare) 概念的位置,唯一性以等价关系检验。不精确而言,若二个对象 a 与 b 互相比较不小于对方 : !comp(a, b) && !comp(b, a) ,则认为它们等价(非唯一)。

std::map 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、关联容器 (AssociativeContainer) 和可逆容器 (ReversibleContainer) 的要求。

成员类型

成员类型 定义
key_type Key
mapped_type T
value_type std::pair
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
key_compare Compare
allocator_type Allocator
reference Allocator::reference(C++11 前)
value_type&(C++11 起)
const_reference Allocator::const_reference(C++11 前)
const value_type&(C++11 起)
pointer Allocator::pointer(C++11 前)
std::allocator_traits::pointer(C++11 起)
const_pointer Allocator::const_pointer(C++11 前)
std::allocator_traits::const_pointer(C++11 起)
iterator 双向迭代器 (LegacyBidirectionalIterator)
const_iterator 常双向迭代器
reverse_iterator std::reverse_iterator
const_reverse_iterator std::reverse_iterator<const_iterator>
node_type(C++17 起) 表示容器结点的结点把柄特化
insert_return_type(C++17 起) 描述插入 node_type 结果的类型,下列类型的特化 template struct { Iter position; bool inserted; NodeType node;}; ,以模板实参 iterator 和 node_type 实例化。
value_compare 比较类型为value_type的对象 (类)

构造函数

构造函数 定义
(构造函数) 构造 map
(析构函数) 析构 map
operator= 赋值给容器
get_allocator 返回相关的分配器

元素访问

方法 说明
at(C++11) 访问指定的元素,同时进行越界检查
operator[] 访问或插入指定的元素

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器
rbegin
crbegin
返回指向容器最后元素的逆向迭代器
rend
crend
返回指向前端的逆向迭代器

容量

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数

修改器

方法 说明
clear 清除内容
insert 插入元素或结点 (C++17 起)
insert_or_assign(C++17) 插入元素,或若关键已存在则赋值给当前元素
emplace(C++11) 原位构造元素
emplace_hint(C++11) 使用提示原位构造元素
try_emplace(C++17) 若键不存在则原位插入,若键存在则不做任何事
erase 擦除元素
swap 交换内容
extract(C++17) 从另一容器释出结点
merge(C++17) 从另一容器接合结点

查找

方法 说明
count 返回匹配特定键的元素数量
find 寻找带有特定键的元素
contains(C++20) 检查容器是否含有带特定关键的元素
equal_range 返回匹配特定键的元素范围
lower_bound 返回指向首个不小于给定键的元素的迭代器
upper_bound 返回指向首个大于给定键的元素的迭代器

观察器

方法 说明
key_comp 返回用于比较键的函数
value_comp 返回用于在value_type类型的对象中比较键的函数。
operator==
operator!=
operator<
operator<=
operator>
operator>=
按照字典顺序比较 map 中的值 (函数模板)
std::swap(std::map) 特化 std::swap 算法 (函数模板)
erase_if(std::map)(C++20) 擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <string>
#include <iomanip>
#include <map>

template<typename Map>
void print_map(Map& m)
{
std::cout << '{';
for(auto& p: m)
std::cout << p.first << ':' << p.second << ' ';
std::cout << "}\n";
}

struct Point { double x, y; };
struct PointCmp {
bool operator()(const Point& lhs, const Point& rhs) const {
return lhs.x < rhs.x; // NB 。有意忽略 y
}
};

int main()
{
// (1) 默认构造函数
std::map<std::string, int> map1;
map1["something"] = 69;
map1["anything"] = 199;
map1["that thing"] = 50;
std::cout << "map1 = "; print_map(map1);

// (2) 范围构造函数
std::map<std::string, int> iter(map1.find("anything"), map1.end());
std::cout << "\niter = "; print_map(iter);
std::cout << "map1 = "; print_map(map1);

// (3) 复制构造函数
std::map<std::string, int> copied(map1);
std::cout << "\ncopied = "; print_map(copied);
std::cout << "map1 = "; print_map(map1);

// (4) 移动构造函数
std::map<std::string, int> moved(std::move(map1));
std::cout << "\nmoved = "; print_map(moved);
std::cout << "map1 = "; print_map(map1);

// (5) initializer_list 构造函数
const std::map<std::string, int> init {
{"this", 100},
{"can", 100},
{"be", 100},
{"const", 100},
};
std::cout << "\ninit = "; print_map(init);


// 定制关键类选项 1 :
// 使用比较 struct
std::map<Point, double, PointCmp> mag = {
{ {5, -12}, 13 },
{ {3, 4}, 5 },
{ {-8, -15}, 17 }
};

for(auto p : mag)
std::cout << "The magnitude of (" << p.first.x
<< ", " << p.first.y << ") is "
<< p.second << '\n';

// 定制关键类选项 2 :
// 使用比较 lambda
// 此 lambda 按照其模比较点,注意其中模取自局部变量 mag
auto cmpLambda = [&mag](const Point &lhs, const Point &rhs) { return mag[lhs] < mag[rhs]; };
// 你亦可使用不依赖局部变量的 lambda ,像这样:
// auto cmpLambda = [](const Point &lhs, const Point &rhs) { return lhs.y < rhs.y; };
std::map<Point, double, decltype(cmpLambda)> magy(cmpLambda);

// 各种插入元素的方式:
magy.insert(std::pair<Point, double>({5, -12}, 13));
magy.insert({ {3, 4}, 5});
magy.insert({Point{-8.0, -15.0}, 17});

std::cout << '\n';
for(auto p : magy)
std::cout << "The magnitude of (" << p.first.x
<< ", " << p.first.y << ") is "
<< p.second << '\n';
}

multiset

键的集合,按照键排序

定义于头文件 <set>

1
2
3
4
5
6
7
8
9
10
11
12
template<
class Key,
class Compare = std::less<Key>,
class Allocator = std::allocator<Key>
> class multiset;
(1)
namespace pmr {
template <class Key, class Compare = std::less<Key>>
using multiset = std::multiset<Key, Compare,
std::pmr::polymorphic_allocator<Key>>;
}
(2)

(2) (C++17 起)
std::multiset 是含有 Key 类型对象有序集的容器。不同于 set ,它允许多个关键拥有等价的值。用关键比较函数 Compare 进行排序。搜索、插入和移除操作拥有对数复杂度。

在标准库使用比较 (Compare) 概念的每处,都用描述于比较 (Compare) 的等价关系确定等价性。不精确地说,若二个对象 a 和 b 互不比较小于对方: !comp(a, b) && !comp(b, a) ,则认为它们等价。

比较等价的元素顺序是插入顺序,而且不会更改。(C++11 起)

std::multiset 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、关联容器 (AssociativeContainer) 和可逆容器 (ReversibleContainer) 的要求。

成员类型

成员类型 定义
key_type Key
value_type Key
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
key_compare Compare
value_compare Compare
allocator_type Allocator
reference Allocator::reference(C++11 前)
value_type&(C++11 起)
const_reference Allocator::const_reference(C++11 前)
const value_type&(C++11 起)
pointer Allocator::pointer(C++11 前)
std::allocator_traits::pointer(C++11 起)
const_pointer Allocator::const_pointer(C++11 前)
std::allocator_traits::const_pointer(C++11 起)
iterator 常双向迭代器 (LegacyBidirectionalIterator)
const_iterator 常双向迭代器
reverse_iterator std::reverse_iterator
const_reverse_iterator std::reverse_iterator<const_iterator>
node_type(C++17 起) 表示容器结点的结点把柄特化

构造函数

构造函数 定义
(构造函数) 构造 multiset
(析构函数) 析构 multiset
operator= 赋值给容器
get_allocator 返回相关的分配器

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器
rbegin
crbegin
返回指向容器最后元素的逆向迭代器
rend
crend
返回指向前端的逆向迭代器

容量

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数

修改器

方法 说明
clear 清除内容
insert 插入元素或结点 (C++17 起)
emplace(C++11) 原位构造元素
emplace_hint(C++11) 使用提示原位构造元素
erase 擦除元素
swap 交换内容
extract(C++17) 从另一容器释出结点
merge(C++17) 从另一容器接合结点

查找

方法 说明
count 返回匹配特定键的元素数量
find 寻找带有特定键的元素
contains(C++20) 检查容器是否含有带特定关键的元素
equal_range 返回匹配特定键的元素范围
lower_bound 返回指向首个不小于给定键的元素的迭代器
upper_bound 返回指向首个大于给定键的元素的迭代器

观察器

方法 说明
key_comp 返回用于比较键的函数
value_comp 返回用于在value_type类型的对象中比较键的函数。
operator==
operator!=
operator<
operator<=
operator>
operator>=
按照字典顺序比较 multiset 中的值 (函数模板)
std::swap(std::multiset) 特化 std::swap 算法 (函数模板)
erase_if(std::multiset)(C++20) 擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// constructing multisets
#include <iostream>
#include <set>

bool fncomp (int lhs, int rhs) {return lhs<rhs;}

struct classcomp {
bool operator() (const int& lhs, const int& rhs) const
{return lhs<rhs;}
};

int main ()
{
std::multiset<int> first; // empty multiset of ints

int myints[]= {10,20,30,20,20};
std::multiset<int> second (myints,myints+5); // pointers used as iterators

std::multiset<int> third (second); // a copy of second

std::multiset<int> fourth (second.begin(), second.end()); // iterator ctor.

std::multiset<int,classcomp> fifth; // class as Compare

bool(*fn_pt)(int,int) = fncomp;
std::multiset<int,bool(*)(int,int)> sixth (fn_pt); // function pointer as Compare

return 0;
}

multimap

键值对的集合,按照键排序

定义于头文件 <map>

1
2
3
4
5
6
7
8
9
10
11
12
13
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T> >
> class multimap;
(1)
namespace pmr {
template <class Key, class T, class Compare = std::less<Key>>
using multimap = std::multimap<Key, T, Compare,
std::pmr::polymorphic_allocator<std::pair<const Key,T>>>;
}
(2)

(2) (C++17 起)
multimap 是关联容器,含有关键-值 pair 的已排序列表,同时容许多个入口拥有同一关键。按照应用到关键的比较函数 Compare 排序。搜索、插入和移除操作拥有对数复杂度。

拥有等价关键的关键-值 pair 的顺序就是插入顺序,且不会更改。(C++11 起)

凡在标准库使用比较 (Compare) 概念出,都用描述于比较 (Compare) 上的等价关系确定等价性。不精确地说,若二个对象 a 和 b 互不小于对方: !comp(a, b) && !comp(b, a) ,则认为它们等价。

std::multimap 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、关联容器 (AssociativeContainer) 和可逆容器 (ReversibleContainer) 的要求。

成员类型

成员类型 定义
key_type Key
mapped_type T
value_type std::pair
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
key_compare Compare
allocator_type Allocator
reference Allocator::reference(C++11 前)
value_type&(C++11 起)
const_reference Allocator::const_reference(C++11 前)
const value_type&(C++11 起)
pointer Allocator::pointer(C++11 前)
std::allocator_traits::pointer(C++11 起)
const_pointer Allocator::const_pointer(C++11 前)
std::allocator_traits::const_pointer(C++11 起)
iterator 双向迭代器 (LegacyBidirectionalIterator)
const_iterator 常双向迭代器
reverse_iterator std::reverse_iterator
const_reverse_iterator std::reverse_iterator<const_iterator>
node_type(C++17 起) 表示容器结点的结点把柄特化
value_compare 比较类型为value_type的对象 (类)

构造函数

构造函数 定义
(构造函数) 构造 multimap
(析构函数) 析构 multimap
operator= 赋值给容器
get_allocator 返回相关的分配器

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器
rbegin
crbegin
返回指向容器最后元素的逆向迭代器
rend
crend
返回指向前端的逆向迭代器

容量

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数

修改器

方法 说明
clear 清除内容
insert 插入元素或结点 (C++17 起)
emplace(C++11) 原位构造元素
emplace_hint(C++11) 使用提示原位构造元素
erase 擦除元素
swap 交换内容
extract(C++17) 从另一容器释出结点
merge(C++17) 从另一容器接合结点

查找

方法 说明
count 返回匹配特定键的元素数量
find 寻找带有特定键的元素
contains(C++20) 检查容器是否含有带特定关键的元素
equal_range 返回匹配特定键的元素范围
lower_bound 返回指向首个不小于给定键的元素的迭代器
upper_bound 返回指向首个大于给定键的元素的迭代器

观察器

方法 说明
key_comp 返回用于比较键的函数
value_comp 返回用于在value_type类型的对象中比较键的函数。
operator==
operator!=
operator<
operator<=
operator>
operator>=
按照字典顺序比较 multimap 中的值 (函数模板)
std::swap(std::multimap) 特化 std::swap 算法 (函数模板)
erase_if(std::multimap)(C++20) 擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <map>

struct Point { double x, y; };
struct PointCmp {
bool operator()(const Point& lhs, const Point& rhs) const {
return lhs.x < rhs.x; // NB 。有意忽略 y
}
};

int main() {
std::multimap<int, int> m = {{1,1},{2,2},{3,3},{4,4},{5,5},{4,4},{3,3},{2,2},{1,1}};
for(auto& p: m) std::cout << p.first << ' ' << p.second << '\n';

// 定制比较
std::multimap<Point, double, PointCmp> mag{
{ {5, 12}, 13 },
{ {3, 4}, 5 },
{ {8, 15}, 17 },
{ {3, -3}, -1 },
};

for(auto p : mag)
std::cout << "The magnitude of (" << p.first.x
<< ", " << p.first.y << ") is "
<< p.second << '\n';
}

unordered_set(C++11 起)

唯一键的集合,按照键生成散列

定义于头文件 <unordered_set>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<
class Key,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator<Key>
> class unordered_set;
(1) (C++11 起)
namespace pmr {
template <class Key,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>>
using unordered_set = std::unordered_set<Key, Hash, Pred,
std::pmr::polymorphic_allocator<Key>>;
}
(2)

(2) (C++17 起)
unordered_set is 是含有 Key 类型唯一对象集合的关联容器。搜索、插入和移除拥有平均常数时间复杂度。

在内部,元素并不以任何特别顺序排序,而是组织进桶中。元素被放进哪个桶完全依赖其值的哈希。这允许对单独元素的快速访问,因为哈希一旦,就准确指代元素被放入的桶。

不可修改容器元素(即使通过非 const 迭代器),因为修改可能更改元素的哈希,并破坏容器。

std::unordered_set 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、无序关联容器 (UnorderedAssociativeContainer) 的要求。

成员类型

成员类型 定义
key_type Key
value_type Key
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
hasher Hash
key_equal KeyEqual(C++20 前)Hash::transparent_key_equal ,若定义且它指名类型,否则为 KeyEqual(C++20 起)
allocator_type Allocator
reference value_type&
const_reference const value_type&
pointer std::allocator_traits::pointer
const_pointer std::allocator_traits::const_pointer
iterator 常向前迭代器 (LegacyForwardIterator)
const_iterator 常向前迭代器
local_iterator 类别、值、差、指针和引用类型都与 iterator 相同的迭代器类型。能用此迭代器在单个桶迭代,但不能跨桶。
const_local_iterator 类别、值、差、指针和引用类型都与 const_iterator 相同的迭代器类型。能用此迭代器在单个桶迭代,但不能跨桶。
node_type(C++17 起) 表示容器结点的结点把柄特化
insert_return_type(C++17 起) 描述插入 node_type 结果的类型,下列类型的特化 template struct { Iter position; bool inserted; NodeType node;}; ,以模板实参 iterator 和 node_type 实例化。

构造函数

构造函数 定义
(构造函数) 构造 unordered_set
(析构函数) 析构 unordered_set
operator= 赋值给容器
get_allocator 返回相关的分配器

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器

容量

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数

修改器

方法 说明
clear 清除内容
insert 插入元素或结点 (C++17 起)
emplace 原位构造元素
emplace_hint 使用提示原位构造元素
erase 擦除元素
swap 交换内容
extract(C++17) 从另一容器释出结点
merge(C++17) 从另一容器接合结点

查找

方法 说明
count 返回匹配特定键的元素数量
find 寻找带有特定键的元素
contains(C++20) 检查容器是否含有带特定关键的元素
equal_range 返回匹配特定键的元素范围

桶接口

方法 说明
begin(size_type)
cbegin(size_type)
返回一个迭代器,指向指定的桶的开始
end(size_type)
cend(size_type)
返回一个迭代器,指向指定的桶的末尾
bucket_count 返回桶数
max_bucket_count 返回桶的最大数量
bucket_size 返回在特定的桶中的元素数量
bucket 返回带有特定键的桶

哈希策略

方法 说明
load_factor 返回每个桶的平均元素数量
max_load_factor 管理每个桶的平均元素数量的最大值
rehash 为至少为指定数量的桶预留存储空间。这会重新生成哈希表。
reserve 为至少为指定数量的元素预留存储空间。这会重新生成哈希表。

观察器

方法 说明
hash_function 返回用于对关键哈希的函数
key_eq 返回用于比较键的相等性的函数
operator==
operator!=
比较 unordered_set 中的值 (函数模板)
std::swap(std::unordered_set)(C++11) 特化 std::swap 算法 (函数模板)
erase_if(std::unordered_set)(C++20) 擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
#include <unordered_set>

template<class T>
T cmerge (T a, T b) { T t(a); t.insert(b.begin(),b.end()); return t; }

int main ()
{
std::unordered_set<std::string> first; // empty
std::unordered_set<std::string> second ( {"red","green","blue"} ); // init list
std::unordered_set<std::string> third ( {"orange","pink","yellow"} ); // init list
std::unordered_set<std::string> fourth ( second ); // copy
std::unordered_set<std::string> fifth ( cmerge(third,fourth) ); // move
std::unordered_set<std::string> sixth ( fifth.begin(), fifth.end() ); // range

std::cout << "sixth contains:";
for (const std::string& x: sixth) std::cout << " " << x;
std::cout << std::endl;

return 0;
}

unordered_map(C++11 起)

键值对的集合,按照键生成散列,键是唯一的

定义于头文件 <unordered_map>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;
(1) (C++11 起)
namespace pmr {
template <class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>>
using unordered_map = std::unordered_map<Key, T, Hash, Pred,
std::pmr::polymorphic_allocator<std::pair<const Key,T>>>;
}
(2)

(2) (C++17 起)
unordered_map 是关联容器,含有带唯一键的键-值 pair 。搜索、插入和元素移除拥有平均常数时间复杂度。

元素在内部不以任何特定顺序排序,而是组织进桶中。元素放进哪个桶完全依赖于其键的哈希。这允许对单独元素的快速访问,因为一旦计算哈希,则它准确指代元素所放进的桶。

std::unordered_map 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、无序关联容器 (UnorderedAssociativeContainer) 的要求。

成员类型

成员类型 定义
key_type Key
mapped_type T
value_type std::pair
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
hasher Hash
key_equal KeyEqual(C++20 前)Hash::transparent_key_equal ,若定义且它指名类型,否则为 KeyEqual(C++20 起)
allocator_type Allocator
reference value_type&
const_reference const value_type&
pointer std::allocator_traits::pointer
const_pointer std::allocator_traits::const_pointer
iterator 向前迭代器 (LegacyForwardIterator)
const_iterator 常向前迭代器
local_iterator 类别、值、差、指针和引用类型都与 iterator 相同的迭代器类型。能用此迭代器在单个桶迭代,但不能跨桶。
const_local_iterator 类别、值、差、指针和引用类型都与 const_iterator 相同的迭代器类型。能用此迭代器在单个桶迭代,但不能跨桶。
node_type(C++17 起) 表示容器结点的结点把柄特化
insert_return_type(C++17 起) 描述插入 node_type 结果的类型,下列类型的特化 template struct { Iter position; bool inserted; NodeType node;}; ,以模板实参 iterator 和 node_type 实例化。

构造函数

构造函数 定义
(构造函数) 构造 unordered_map
(析构函数) 析构 unordered_map
operator= 赋值给容器
get_allocator 返回相关的分配器

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器

容量

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数

修改器

方法 说明
clear 清除内容
insert 插入元素或结点 (C++17 起)
insert_or_assign(C++17) 插入元素,或若关键已存在则赋值给当前元素
emplace 原位构造元素
emplace_hint 使用提示原位构造元素
try_emplace(C++17) 若键不存在则原位插入,若键存在则不做任何事
erase 擦除元素
swap 交换内容
extract(C++17) 从另一容器释出结点
merge(C++17) 从另一容器接合结点

查找

方法 说明
at 访问指定的元素,同时进行越界检查
operator[] 访问或插入指定的元素
count 返回匹配特定键的元素数量
find 寻找带有特定键的元素
contains(C++20) 检查容器是否含有带特定关键的元素
equal_range 返回匹配特定键的元素范围

桶接口

方法 说明
begin(size_type)
cbegin(size_type)
返回一个迭代器,指向指定的桶的开始
end(size_type)
cend(size_type)
返回一个迭代器,指向指定的桶的末尾
bucket_count 返回桶数
max_bucket_count 返回桶的最大数量
bucket_size 返回在特定的桶中的元素数量
bucket 返回带有特定键的桶

哈希策略

方法 说明
load_factor 返回每个桶的平均元素数量
max_load_factor 管理每个桶的平均元素数量的最大值
rehash 为至少为指定数量的桶预留存储空间。这会重新生成哈希表。
reserve 为至少为指定数量的元素预留存储空间。这会重新生成哈希表。

观察器

方法 说明
hash_function 返回用于对关键哈希的函数
key_eq 返回用于比较键的相等性的函数
operator==
operator!=
比较 unordered_map 中的值 (函数模板)
std::swap(std::unordered_map)(C++11) 特化 std::swap 算法 (函数模板)
erase_if(std::unordered_map)(C++20) 擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
// 创建三个 string 的 unordered_map (映射到 string )
std::unordered_map<std::string, std::string> u = {
{"RED","#FF0000"},
{"GREEN","#00FF00"},
{"BLUE","#0000FF"}
};

// 迭代并打印 unordered_map 的关键和值
for( const auto& n : u ) {
std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
}

// 添加新入口到 unordered_map
u["BLACK"] = "#000000";
u["WHITE"] = "#FFFFFF";

// 用关键输出值
std::cout << "The HEX of color RED is:[" << u["RED"] << "]\n";
std::cout << "The HEX of color BLACK is:[" << u["BLACK"] << "]\n";

return 0;
}

unordered_multiset(C++11 起)

键的集合,按照键生成散列

定义于头文件 <unordered_set>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<
class Key,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator<Key>
> class unordered_multiset;
(1) (C++11 起)
namespace pmr {
template <class Key,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>>
using unordered_multiset = std::unordered_multiset<Key, Hash, Pred,
std::pmr::polymorphic_allocator<Key>>
}
(2)

(2) (C++17 起)
unordered_multiset 是关联容器,含有可能非唯一 Key 类型对象的集合。搜索、插入和移除拥有平均常数时间复杂度。

元素在内部并不以任何顺序排序,只是被组织到桶中。元素被放入哪个桶完全依赖其值的哈希。这允许快速访问单独的元素,因为一旦计算哈希,它就指代放置该元素的准确的桶。

不要求此容器的迭代顺序稳定(故例如 std::equal 不能用于比较二个 std::unordered_multiset ),除了关键比较等价(以 key_eq() 为比较器比较相等)的每组元素组成迭代顺序中的相接子范围,它可用 equal_range() 访问。

std::unordered_multiset 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、无序关联容器 (UnorderedAssociativeContainer) 的要求

成员类型

成员类型 定义
key_type Key
value_type Key
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
hasher Hash
key_equal KeyEqual(C++20 前)Hash::transparent_key_equal ,若定义且它指名类型,否则为 KeyEqual(C++20 起)
allocator_type Allocator
reference value_type&
const_reference const value_type&
pointer std::allocator_traits::pointer
const_pointer std::allocator_traits::const_pointer
iterator 常向前迭代器 (LegacyForwardIterator)
const_iterator 常向前迭代器
local_iterator 类别、值、差、指针和引用类型都与 iterator 相同的迭代器类型。能用此迭代器在单个桶迭代,但不能跨桶。
const_local_iterator 类别、值、差、指针和引用类型都与 const_iterator 相同的迭代器类型。能用此迭代器在单个桶迭代,但不能跨桶。
node_type(C++17 起) 表示容器结点的结点把柄特化

构造函数

构造函数 定义
(构造函数) 构造 unordered_multiset
(析构函数) 析构 unordered_multiset
operator= 赋值给容器
get_allocator 返回相关的分配器

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器

容量

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数

修改器

方法 说明
clear 清除内容
insert 插入元素或结点 (C++17 起)
emplace 原位构造元素
emplace_hint 使用提示原位构造元素
erase 擦除元素
swap 交换内容
extract(C++17) 从另一容器释出结点
merge(C++17) 从另一容器接合结点

查找

方法 说明
count 返回匹配特定键的元素数量
find 寻找带有特定键的元素
contains(C++20) 检查容器是否含有带特定关键的元素
equal_range 返回匹配特定键的元素范围

桶接口

方法 说明
begin(size_type)
cbegin(size_type)
返回一个迭代器,指向指定的桶的开始
end(size_type)
cend(size_type)
返回一个迭代器,指向指定的桶的末尾
bucket_count 返回桶数
max_bucket_count 返回桶的最大数量
bucket_size 返回在特定的桶中的元素数量
bucket 返回带有特定键的桶

哈希策略

方法 说明
load_factor 返回每个桶的平均元素数量
max_load_factor 管理每个桶的平均元素数量的最大值
rehash 为至少为指定数量的桶预留存储空间。这会重新生成哈希表。
reserve 为至少为指定数量的元素预留存储空间。这会重新生成哈希表。

观察器

方法 说明
hash_function 返回用于对关键哈希的函数
key_eq 返回用于比较键的相等性的函数
operator==
operator!=
比较 unordered_multiset 中的值 (函数模板)
std::swap(std::unordered_multiset)(C++11) 特化 std::swap 算法 (函数模板)
erase_if(std::unordered_multiset)(C++20) 擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
#include <unordered_set>

template<class T>
T cmerge (T a, T b) { T t(a); t.insert(b.begin(),b.end()); return t; }

int main ()
{
std::unordered_multiset<std::string> first; // empty
std::unordered_multiset<std::string> second ( {"red","green","blue"} ); // init list
std::unordered_multiset<std::string> third ( {"red","yellow","blue"} ); // init list
std::unordered_multiset<std::string> fourth ( second ); // copy
std::unordered_multiset<std::string> fifth ( cmerge(third,fourth) ); // move
std::unordered_multiset<std::string> sixth ( fifth.begin(), fifth.end() ); // range

std::cout << "sixth contains:";
for (const std::string& x: sixth) std::cout << " " << x;
std::cout << std::endl;

return 0;
}

unordered_multimap(C++11 起)

键值对的集合,按照键生成散列

定义于头文件 <unordered_map>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_multimap;
(1) (C++11 起)
namespace pmr {
template <class Key, class T,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>>
using unordered_multimap = std::unordered_multimap<Key, T, Hash, Pred,
std::pmr::polymorphic_allocator<std::pair<const Key,T>>>;
}
(2)

(2) (C++17 起)
unordered_multimap 是无序关联容器,支持等价的关键(一个 unordered_multimap 可含有每个关键值的多个副本)和将关键与另一类型的值关联。 unordered_multimap 类支持向前迭代器。搜索、插入和移除拥有平均常数时间复杂度。

元素在内部不以任何特定顺序排序,而是组织到桶中。元素被放进哪个桶完全依赖于其关键的哈希。这允许到单独元素的快速访问,因为哈希一旦计算,则它指代元素被放进的准确的桶。

不要求此容器的迭代顺序稳定(故例如 std::equal 不能用于比较二个 std::unordered_multimap ),除了关键比较等价(以 key_eq() 为比较器比较相等)的每组元素在迭代顺序中组成相接的子范围,它亦可用 equal_range() 访问。

std::unordered_multimap 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、无序关联容器 (UnorderedAssociativeContainer) 的要求。

成员类型

成员类型 定义
key_type Key
mapped_type T
value_type std::pair
size_type 无符号整数类型(通常是 std::size_t )
difference_type 有符号整数类型(通常是 std::ptrdiff_t )
hasher Hash
key_equal KeyEqual(C++20 前)Hash::transparent_key_equal ,若定义且它指名类型,否则为 KeyEqual(C++20 起)
allocator_type Allocator
reference value_type&
const_reference const value_type&
pointer std::allocator_traits::pointer
const_pointer std::allocator_traits::const_pointer
iterator 向前迭代器 (LegacyForwardIterator)
const_iterator 常向前迭代器
local_iterator 类别、值、差、指针和引用类型都与 iterator 相同的迭代器类型。能用此迭代器在单个桶迭代,但不能跨桶。
const_local_iterator 类别、值、差、指针和引用类型都与 const_iterator 相同的迭代器类型。能用此迭代器在单个桶迭代,但不能跨桶。
node_type(C++17 起) 表示容器结点的结点把柄特化

构造函数

构造函数 定义
(构造函数) 构造 unordered_multimap
(析构函数) 析构 unordered_multimap
operator= 赋值给容器
get_allocator 返回相关的分配器

迭代器

方法 说明
begin
cbegin
返回指向容器第一个元素的迭代器
end
cend
返回指向容器尾端的迭代器

容器

方法 说明
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数

修改器

方法 说明
clear 清除内容
insert 插入元素或结点 (C++17 起)
emplace 原位构造元素
emplace_hint 使用提示原位构造元素
erase 擦除元素
swap 交换内容
extract(C++17) 从另一容器释出结点
merge(C++17) 从另一容器接合结点

查找

方法 说明
count 返回匹配特定键的元素数量
find 寻找带有特定键的元素
contains(C++20) 检查容器是否含有带特定关键的元素
equal_range 返回匹配特定键的元素范围

桶接口

方法 说明
begin(size_type)
cbegin(size_type)
返回一个迭代器,指向指定的桶的开始
end(size_type)
cend(size_type)
返回一个迭代器,指向指定的桶的末尾
bucket_count 返回桶数
max_bucket_count 返回桶的最大数量
bucket_size 返回在特定的桶中的元素数量
bucket 返回带有特定键的桶

哈希策略

方法 说明
load_factor 返回每个桶的平均元素数量
max_load_factor 管理每个桶的平均元素数量的最大值
rehash 为至少为指定数量的桶预留存储空间。这会重新生成哈希表。
reserve 为至少为指定数量的元素预留存储空间。这会重新生成哈希表。

观察器

方法 说明
hash_function 返回用于对关键哈希的函数
key_eq 返回用于比较键的相等性的函数
operator==
operator!=
比较 unordered_multimap 中的值 (函数模板)
std::swap(std::unordered_multimap)(C++11) 特化 std::swap 算法 (函数模板)
erase_if(std::unordered_multimap)(C++20) 擦除所有满足特定判别标准的元素 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <string>
#include <unordered_map>

typedef std::unordered_multimap<std::string,std::string> stringmap;

stringmap merge (stringmap a,stringmap b) {
stringmap temp(a); temp.insert(b.begin(),b.end()); return temp;
}

int main ()
{
stringmap first; // empty
stringmap second ( {{"apple","red"},{"lemon","yellow"}} ); // init list
stringmap third ( {{"apple","green"},{"strawberry","red"}} ); // init list
stringmap fourth (second); // copy
stringmap fifth (merge(third,fourth)); // move
stringmap sixth (fifth.begin(),fifth.end()); // range

std::cout << "sixth contains:";
for (auto& x: sixth) std::cout << " " << x.first << ":" << x.second;
std::cout << std::endl;

return 0;
}

stack

堆栈适配器(LIFO)

定义于头文件 <stack>

1
2
3
4
template<
class T,
class Container = std::deque<T>
> class stack;

std::stack 类是容器适配器,它给予程序员栈的功能——特别是 FILO (先进后出)数据结构。

该类模板表现为底层容器的包装器——只提供特定函数集合。栈从被称作栈顶的容器尾部推弹元素。

成员类型

成员类型 定义
container_type Container
value_type Container::value_type
size_type Container::size_type
reference Container::reference
const_reference Container::const_reference

构造函数

构造函数 定义
(构造函数) 构造 stack
(析构函数) 析构 stack
operator= 赋值给容器适配器

元素访问

方法 说明
top 访问栈顶元素

容量

方法 说明
empty 检查底层的容器是否为空
size 返回容纳的元素数

修改器

方法 说明
push 向栈顶插入元素
emplace(C++11) 于顶原位构造元素
pop 删除栈顶的元素
swap 交换内容

成员对象

方法 说明
Container c 底层容器 (受保护成员对象)
operator==
operator!=
operator<
operator<=
operator>
operator>=
按照字典顺序比较 stack 中的值 (函数模板)
std::swap(std::stack) 特化 std::swap 算法 (函数模板)
std::uses_allocatorstd::stack(C++11) 特化 std::uses_allocator 类型特性 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stack>
#include <deque>
#include <iostream>

int main()
{
std::stack<int> c1;
c1.push(5);
std::cout << c1.size() << '\n';

std::stack<int> c2(c1);
std::cout << c2.size() << '\n';

std::deque<int> deq {3, 1, 4, 1, 5};
std::stack<int> c3(deq);
std::cout << c3.size() << '\n';
}

queue

改写容器来提供队列(FIFO数据结构)

定义于头文件 <queue>

1
2
3
4
template<
class T,
class Container = std::deque<T>
> class queue;

std::queue 类是容器适配器,它给予程序员队列的功能——尤其是 FIFO (先进先出)数据结构。

类模板表现为底层容器的包装器——只提供特定的函数集合。 queue 在底层容器尾端推入元素,从首端弹出元素。

成员类型

成员类型 定义
container_type Container
value_type Container::value_type
size_type Container::size_type
reference Container::reference
const_reference Container::const_reference

构造函数

构造函数 定义
(构造函数) 构造 queue
(析构函数) 析构 queue
operator= 赋值给容器适配器

元素访问

方法 说明
front 访问第一个元素
back 访问最后一个元素

容量

方法 说明
empty 检查底层的容器是否为空
size 返回容纳的元素数

修改器

方法 说明
push 向队列尾部插入元素
emplace(C++11) 于尾部原位构造元素
pop 删除第一个元素
swap 交换内容

成员对象

方法 说明
Container c 底层容器 (受保护成员对象)
operator==
operator!=
operator<
operator<=
operator>
operator>=
按照字典顺序比较 queue 中的值 (函数模板)
std::swap(std::queue) 特化 std::swap 算法 (函数模板)
std::uses_allocator<std::queue>(C++11) 特化 std::uses_allocator 类型特性 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <queue>
#include <deque>
#include <iostream>

int main()
{
std::queue<int> c1;
c1.push(5);
std::cout << c1.size() << '\n';

std::queue<int> c2(c1);
std::cout << c2.size() << '\n';

std::deque<int> deq {3, 1, 4, 1, 5};
std::queue<int> c3(deq);
std::cout << c3.size() << '\n';
}

priority_queue

改写容器来提供优先级队列

定义于头文件 <queue>

1
2
3
4
5
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;

priority_queue 是容器适配器,它提供常数时间的(默认)最大元素查找,对数代价的插入与释出。

可用用户提供的 Compare 更改顺序,例如,用 std::greater 将导致最小元素作为 top() 出现。

用 priority_queue 工作类似管理某些随机访问容器中的堆,优势是不可能突然把堆非法化。

成员类型

成员类型 定义
container_type Container
value_compare (C++17) Compare
value_type Container::value_type
size_type Container::size_type
reference Container::reference
const_reference Container::const_reference

构造函数

构造函数 定义
(构造函数) 构造 priority_queue
(析构函数) 析构 priority_queue
operator= 赋值给容器适配器

元素访问

方法 说明
top 访问栈顶元素

容量

方法 说明
empty 检查底层的容器是否为空
size 返回容纳的元素数

修改器

方法 说明
push 插入元素,并对底层容器排序
emplace(C++11) 原位构造元素并排序底层容器
pop 删除第一个元素
swap 交换内容

成员对象

方法 说明
Container c 底层容器 (受保护成员对象)
Compare comp 比较函数对象 (受保护成员对象)
std::swap(std::priority_queue) 特化 std::swap 算法 (函数模板)
std::uses_allocator<std::priority_queue>(C++11) 特化 std::uses_allocator 类型特性 (函数模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <functional>
#include <queue>
#include <vector>
#include <iostream>

template<typename T> void print_queue(T& q) {
while(!q.empty()) {
std::cout << q.top() << " ";
q.pop();
}
std::cout << '\n';
}

int main() {
std::priority_queue<int> q;

for(int n : {1,8,5,6,3,4,0,9,7,2})
q.push(n);

print_queue(q);

std::priority_queue<int, std::vector<int>, std::greater<int> > q2;

for(int n : {1,8,5,6,3,4,0,9,7,2})
q2.push(n);

print_queue(q2);

// 用 lambda 比较元素。
auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1);};
std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);

for(int n : {1,8,5,6,3,4,0,9,7,2})
q3.push(n);

print_queue(q3);
}

span(C++20)

相接的对象序列上的非占有视图

定义于头文件 <span>

1
2
3
4
template< 
class T,
std::size_t Extent = std::dynamic_extent
> class span;

(C++20 起)
类模板 span 所描述的对象能指代对象的相接序列,序列的首元素在零位置。 span 能拥有静态长度,该情况下序列中的元素数已知并编码于类型中,或拥有动态长度。

典型实现只保有二个成员:指向 T 的指针和大小。

成员类型

成员类型 定义
element_type T
value_type std::remove_cv_t
index_type std::size_t
difference_type std::ptrdiff_t
pointer T*
reference T&
iterator 实现定义的 LegacyRandomAccessIterator 、常表达式迭代器 (ConstexprIterator) 兼 LegacyContiguousIterator ,其 value_type 为 value_type
const_iterator 实现定义的常 LegacyRandomAccessIterator、常表达式迭代器 (ConstexprIterator) 兼 LegacyContiguousIterator ,其 value_type 为 value_type
reverse_iterator std::reverse_iterator
const_reverse_iterator std::reverse_iterator<const_iterator>

构造函数

构造函数 定义
(构造函数) 构造 span
operator= 赋值 span

迭代器

方法 说明
begincbegin 返回指向序列起始的迭代器
endcend 返回指向序列末尾的迭代器
rbegincrbegin 返回指向序列逆向起始的逆向迭代器
rendcrend 返回指向序列逆向末尾的逆向迭代器

元素访问

方法 说明
front 访问第一个元素
back 访问最后一个元素
operator[] 访问序列的元素
data 返回指向元素序列起始的指针

观察器

方法 说明
size 返回序列中的元素数
size_bytes 返回以字节表示的序列大小
empty 检查序列是否为空

子视图

方法 说明
first 获得由序列首 N 个元素组成的子段
last 获得由序列末 N 个元素组成的子段
subspan 获得子段
beginend 返回指向 span 开始和结尾的迭代器 (函数)
as_bytesas_writable_bytes 转换 span 为对其底层字节的视图 (函数模板)
std::get(std::span) 访问静态长度 span 的单个元素 (函数模板)
dynamic_extent(C++20) size_t 类型常量,指明 span 拥有动态长度 (常量)
std::tuple_sizestd::span 获得静态长度 span 的大小 (类模板特化)
std::tuple_elementstd::span 获得静态长度 span 的元素类型 (类模板特化)

爬取代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
let cheerio = require("cheerio");
let fs = require("fs-extra");
let promisify = require("util").promisify;
let fetchUrl = require("fetch").fetchUrl;
const outputJsonAsync = promisify(fs.outputJson);

fetchUrl[promisify.custom] = function(url, option) {
return new Promise((resolve, reject) => {
fetchUrl(url, option, function(error, meta, body) {
error ? resolve(error) : resolve(body.toString());
});
});
};

const fetchUrlAsync = promisify(fetchUrl);

(async function() {
try {
let body = null;
let hrefs = [
"https://zh.cppreference.com/w/cpp/container/array",
"https://zh.cppreference.com/w/cpp/container/vector",
"https://zh.cppreference.com/w/cpp/container/deque",
"https://zh.cppreference.com/w/cpp/container/forward_list",
"https://zh.cppreference.com/w/cpp/container/list",

"https://zh.cppreference.com/w/cpp/container/set",
"https://zh.cppreference.com/w/cpp/container/map",
"https://zh.cppreference.com/w/cpp/container/multiset",
"https://zh.cppreference.com/w/cpp/container/multimap",

"https://zh.cppreference.com/w/cpp/container/unordered_set",
"https://zh.cppreference.com/w/cpp/container/unordered_map",
"https://zh.cppreference.com/w/cpp/container/unordered_multiset",
"https://zh.cppreference.com/w/cpp/container/unordered_multimap",

"https://zh.cppreference.com/w/cpp/container/stack",
"https://zh.cppreference.com/w/cpp/container/queue",
"https://zh.cppreference.com/w/cpp/container/priority_queue",

"https://zh.cppreference.com/w/cpp/container/span"
];

for (const href of hrefs) {
body = await fetchUrlAsync(href);
console.log();
console.log(href);
console.log("----------------------------------------------------------------------------------------");
console.log();
let $ = cheerio.load(body);
var s = $(".t-dsc-begin").each(function(i, table) {
$(table)
.find("tr")
.each(function(i, tr) {
if (
$(tr)
.parent()
.parent()
.hasClass("t-rev-begin")
)
return;
if ($(tr).find("td").length === 1) {
console.log();
let title = $(tr)
.text()
.trim();
if (title) {
console.log("### " + title);
console.log("|方法|说明|");
} else {
console.log("### 成员类型");
console.log("|成员类型|定义|");
}
console.log("|----|----|");
} else {
let deal = data =>
data
.replace(/\[编辑\]/g, "")
.replace(/\r\n/g, "")
.replace(/\n/g, "")
.replace(/\(公开成员函数\)/g, "")
.replace(/\(类模板\)/g, "")
.trim();
let td1 = $(tr)
.find("td")
.eq(0)
.text();
let href = $(tr)
.find("td")
.eq(0)
.find("a")
.attr("href");
let td2 = $(tr)
.find("td")
.eq(1)
.text();
td1 = deal(td1);
td2 = deal(td2);
if (href) {
if (!href.includes("https://zh.cppreference.com")) {
href = "https://zh.cppreference.com" + href;
}
td1 = `[${td1}](${href})`;
}

let data = "|" + td1 + "|" + td2 + "|";
if (data.includes("11 前)") && data.includes("11 起)")) {
data = data.replace("11 前)", "11 前)<br>");
}
console.log(data);
}
});
});
}
} catch (error) {
console.log("error:", error);
}
})();
您的支持将鼓励我继续创作!
0%