小鲸鱼的梦境
0%

C++ STL学习笔记

发表于 分类于 Valine：
本文字数： 32k 阅读时长 ≈ 29 分钟

STL简介

  • 标准模板库(STL, Standard Template Library)提供了一些常用的数据结构和算法
  • 基本组件: 容器(container)、迭代器(iterator)、函数对象(function object)、算法(algorithms)
  • 从根本上说，STL 是一些容器、算法和其他一些组件的集合，所有容器和算法都是总结了几十年来算法和数据结构的研究成果，汇集了许多计算机专家学者经验的基础上实现的，因此可以说，STL 基本上达到了各种存储方法和相关算法的高度优化。

目录

基本组件

头文件: <iterator> <functional> <vector> <deque> <list> <queue> <stack> <set> <map> <algorithm> <numeric> <memory> <utility>

  • 容器: 容纳、包含一组元素的对象
    • 分为 序列容器和关联容器
    • 序列容器: array, vector, deque, list, forward_list
    • 关联容器: map, set, multimap, multiset(底层是红黑树)
    • 关联容器: unordered_map, unordered_multimap, unordered_set, unordered_multiset(底层是哈希表)
  • 迭代器: 一种泛化的指针，使用'*'访问元素，重载了++, --, []等运算符
    • 正向迭代器(容器类名::iterator 迭代器名;)
    • 常量正向迭代器(容器类名::const_iterator 迭代器名;)
    • 反向迭代器(容器类名::reverse_iterator 迭代器名;)
    • 常量反向迭代器(容器类名::const_reverse_iterator 迭代器名;)
    • 通常迭代器可以使用auto让编译器自动判断类型(因为类型名太长了>_<)
    • 当迭代器指向容器中的一个特定元素时，它们不会保留任何关于容器本身的信息，所以，它所指向元素的容器类型
  • 函数对象: 普通函数和重载了()运算符的对象

迭代器示例

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
/* Code language: C++ */
int main()
{
    /* vector容器 */
    vector<int> nums{1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
    /* 常规遍历方式 */
    for (int i = 0; i < nums.size(); ++i)
        cout << nums[i] << ends;
    cout << endl;
    /* 常规遍历模式2 */
    for (int e : nums)
        cout << e << ends;
    cout << endl;
    /* 正向迭代器 */
    for (auto i = nums.begin(); i != nums.end(); ++i)
        cout << *i << ends;
    cout << endl;
    /* 反向迭代器 */
    for (vector<int>::reverse_iterator i = nums.rbegin(); i < nums.rend(); ++i)
        cout << *i << ends;
    cout << endl;
    return 0;
}
/* Output
* 1 2 3 4 5 6 7 8 9 0 
* 1 2 3 4 5 6 7 8 9 0 
* 1 2 3 4 5 6 7 8 9 0 
* 0 9 8 7 6 5 4 3 2 1
*/

序列型容器

array

array 容器是 C++ 11 标准中新增的序列容器，简单地理解，它就是在 C++ 普通数组的基础上，添加了一些成员函数和全局函数。它比普通数组更安全，且效率并没有因此变差

1
2
3
4
5
6
7
/* 原型 */
/* 定义(不初始化) */
array<double, 10> values;
/* 定义(初始化为0) */
array<int, 10> values;
/* 定义(手动初始化) */
array<int, 10> values {1, 2, 3, 4, 5};

array特性

  • 顺序：顺序容器中的元素按严格的线性顺序存储
  • 连续存储：元素存储在连续的内存位置中，允许对元素进行 \(O(1)\) 的随机访问。元素的指针可以偏移以访问其他元素
  • 固定大小：容器使用隐式构造函数和析构函数静态地分配所需的空间。它的大小是编译时确定的常数，没有额外的内存和时间开销

注意事项：

  • 容器大小 N 必须是常量而不能是变量
  • 不会自动初始化(未初始化时值是不确定的)
  • end() 返回指向数组中最后一个元素之后一个位置的指针(注意不是最后一个元素)
  • 可以通过[]运算符访问任意元素(但没有边界检查)，也可以用 at() 成员函数(越界会抛出异常)

array成员函数

成员函数 功能
\(begin()\) 返回指向容器中第一个元素的随机访问迭代器
\(end()\) 返回指向容器最后一个元素之后一个位置的随机访问迭代器
\(rbegin()\) 返回指向最后一个元素的随机访问迭代器
\(rend()\) 返回指向第一个元素之前一个位置的随机访问迭代器
\(cbegin()\) 和 \(begin()\) 功能相同，只不过在其基础上增加了 const 属性，不能用于修改元素
\(cend()\) 和 \(end()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(crbegin()\) 和 \(rbegin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(crend()\) 和 \(rend()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(size()\) 返回容器中当前元素的数量，其值始终等于初始化 array 类的第二个模板参数 N
\(max\_size()\) 返回容器可容纳元素的最大数量，其值始终等于初始化 array 类的第二个模板参数 N
\(operator[ \, ]\) 返回容器中 n 位置处元素的引用
\(empty()\) 判断容器是否为空，和通过 size()==0 的判断条件功能相同，但其效率可能更快
\(at(n)\) 返回容器中 n 位置处元素的引用，该函数自动检查 n 是否在有效的范围内，如果不是则抛出 out_of_range 异常
\(front()\) 返回容器中第一个元素的直接引用，该函数不适用于空的 array 容器
\(back()\) 返回容器中最后一个元素的直接应用，该函数同样不适用于空的 array 容器
\(data()\) 返回一个指向容器首个元素的指针，利用该指针，可实现复制容器中所有元素等类似功能
\(fill(val)\) 将 val 这个值赋值给容器中的每个元素
\(array1.swap(array2)\) 交换 array1 和 array2 容器中的所有元素，但前提是它们具有相同的长度和类型

vector

vector 是动态数组，可以进行元素的插入和删除，在此过程中，vector 会动态调整所占用的内存空间
vector 支持随机访问，但在除尾部以外的位置增删元素效率较低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 创建空的vector(未分配空间) */
vector<int> values;
/* 创建初始化好的vector */
vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};
/* 创建指定元素数量的vector(第一个参数是元素数量，第二个参数是初始值-不带该参数默认是0) */
vector<int> values(20, 1);
/* 多维的vector及初始化 */
vector<vector<vector<int>>> values(100, vector<vector<int>>(20, vector<int>(10, 0)));

vector<int> first;                                // empty vector of ints
vector<int> second (4,100);                       // four ints with value 100
vector<int> third (second.begin(),second.end());  // iterating through second
vector<int> fourth (third);                       // a copy of third
// the iterator constructor can also be used to construct from arrays:
int myints[] = {16,2,77,29};
vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

vector特性

  • 顺序：顺序容器中的元素按严格的线性顺序存储
  • 动态：支持随机访问，支持通过指针偏移访问，在末尾进行添加/删除操作较快
  • Allocator-aware：容器使用分配器对象动态处理其存储需求(即动态内存分配)

注意事项：

  • 不要使用vector<bool>, 因为这个比较特殊是按位(bit)存储值的，容易出问题，想要构造bool类型的数组建议使用bitset
  • end() 返回指向数组中最后一个元素之后一个位置的指针(注意不是最后一个元素)
  • 对于空的 vector 容器不能使用迭代器
  • vector 容器在申请更多内存的同时，容器中的所有元素可能会被复制或移动到新的内存地址，这会导致之前创建的迭代器失效
  • 可以通过[]运算符访问任意元素(但没有边界检查)，也可以用 at() 成员函数(越界会抛出异常)
  • emplace_back() (c++ 11)和push_back()的区别
    • push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）
    • emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程
    • emplace_back() 的执行效率比 push_back() 高
  • insert的用法
    • iterator insert(pos,elem)在迭代器 pos 指定的位置之前插入一个新元素elem，并返回表示新插入元素位置的迭代器
    • iterator insert(pos,n,elem)在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器
    • iterator insert(pos,first,last)在迭代器 pos 指定的位置之前，插入其他容器（不仅限于vector）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器
    • iterator insert(pos,initlist)在迭代器 pos 指定的位置之前，插入初始化列表（用大括号{}括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器
    • emplace() (C++ 11) 与 insert() 作用类似，但只能插入一个元素，不过效率比较高(原理和前面一样)

vector成员函数

成员函数 函数功能
\(begin()\) 返回指向容器中第一个元素的迭代器
\(end()\) 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用
\(rbegin()\) 返回指向最后一个元素的迭代器
\(rend()\) 返回指向第一个元素所在位置前一个位置的迭代器
\(cbegin()\) 和 \(begin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(cend()\) 和 \(end()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(crbegin()\) 和 \(rbegin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(crend()\) 和 \(rend()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(size()\) 返回实际元素个数
\(max\_size()\) 返回元素个数的最大值,这通常是一个很大的值，一般是 \(2^{32}-1\)，所以我们很少会用到这个函数
\(resize()\) 改变实际元素的个数
\(capacity()\) 返回当前容量
\(empty()\) 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false
\(reserve(n)\) 增加容器的容量
\(shrink \_to\_fit()\) 将内存减少到等于当前元素实际所使用的大小
\(operator[ \, ]\) 重载了 [] 运算符，可以向访问数组中元素那样，通过下标即可访问甚至修改 vector 容器中的元素
\(at()\) 使用经过边界检查的索引访问元素
\(front()\) 返回第一个元素的引用
\(back()\) 返回最后一个元素的引用
\(data()\) 返回指向容器中第一个元素的指针
\(assign()\) 用新元素替换原有内容
\(push\_back()\) 在序列的尾部添加一个元素
\(pop\_back()\) 移出序列尾部的元素
\(insert()\) 在指定的位置插入一个或多个元素
\(erase()\) 移出一个元素或一段元素
\(clear()\) 移出所有的元素，容器大小变为 0
\(swap()\) 交换两个容器的所有元素
\(emplace()\) 在指定的位置直接插入一个元素
\(emplace\_back()\) 在序列尾部插入一个元素
\(get\_allocator()\) 获取分配器

vector底层实现

vector对象最主要的结构就是一段连续的线性内存空间(这很简单)，扩容时可能会另外申请空间再将元素复制到新空间最后释放掉原空间，这也是增删元素后旧的迭代器可能会失效的原因

vector

个人理解，vector本质上还是静态的数组，只不过封装成类以后添加了自动扩大缩小容量的功能，使得数组具备了“动态”的功能

1
2
3
4
5
6
7
8
9
10
//_Alloc 表示内存分配器
template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
    ...
protected:
    pointer _Myfirst;  /* 指向 vector 容器对象的起始位置 */
    pointer _Mylast;  /* 指向 vector 容器对象最后一个元素的末尾 */
    pointer _Myend;  /* 指向整个 vector 容器所占用内存空间的末尾 */
    /* 对于空的 vector 容器，由于没有任何元素的空间分配，因此 _Myfirst、_Mylast 和 _Myend 均为 null */
};

deque

deque是双端队列，在容器首尾添加/删除元素的时间复杂度均为 \(O(1)\)，支持随机访问，但在首尾以外的位置增删元素效率较低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 创建空的deque */
deque<int> d;
/* 创建具有n个元素的deque(默认为0) */
deque<int> d(10);
/* 创建具有n个元素，值为x的deque */
deque<int> d(10, 5)
/* 复制构造 */
array<int, 5>arr{ 11,12,13,14,15 };
deque<int>d(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}

// constructors used in the same order as described above:
deque<int> first;                                // empty deque of ints
deque<int> second (4,100);                       // four ints with value 100
deque<int> third (second.begin(),second.end());  // iterating through second
deque<int> fourth (third);                       // a copy of third
// the iterator constructor can be used to copy arrays:
int myints[] = {16,2,77,29};
deque<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

deque特性

  • 顺序：顺序容器中的元素按严格的线性顺序存储(但不能保证将其所有元素存储在连续的存储位置中)
  • 动态：通常实现为动态数组，它允许直接访问序列中的任何元素，并在序列的开头或结尾提供相对快速的元素添加/删除。
  • Allocator-aware：容器使用分配器对象动态处理其存储需求

注意事项：

  • end() 返回指向数组中最后一个元素之后一个位置的指针(注意不是最后一个元素)
  • 对于空的 deque 容器不能使用迭代器
  • deque 容器在申请更多内存的同时，容器中的所有元素可能会被复制或移动到新的内存地址，这会导致之前创建的迭代器失效
  • 可以通过[]运算符访问任意元素(但没有边界检查)，也可以用 at() 成员函数(越界会抛出异常)
  • deque 中的元素并不一定在连续的存储空间，所以不能通过指针偏移的方法访问
  • emplace 系列的函数比 push高效(原因和前面一样)，insert用法也和前面一样(这是一个全局性的函数，后面不再重复说明)

deque成员函数

成员函数 函数功能
\(begin()\) 返回指向容器中第一个元素的迭代器
\(end()\) 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 \(begin()\) 结合使用
\(rbegin()\) 返回指向最后一个元素的迭代器
\(rend()\) 返回指向第一个元素所在位置前一个位置的迭代器
\(cbegin()\) 和 \(begin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(cend()\) 和 \(end()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(crbegin()\) 和 \(rbegin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(crend()\) 和 \(rend()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(size()\) 返回实际元素个数
\(max\_size()\) 返回容器所能容纳元素个数的最大值, 这通常是一个很大的值，一般是 \(2^{32}-1\)，我们很少会用到这个函数
\(resize()\) 改变实际元素的个数
\(empty()\) 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false
\(shrink\_to\_fit()\) 将内存减少到等于当前元素实际所使用的大小
\(at()\) 使用经过边界检查的索引访问元素
\(front()\) 返回第一个元素的引用
\(back()\) 返回最后一个元素的引用
\(assign()\) 用新元素替换原有内容
\(push\_back()\) 在序列的尾部添加一个元素
\(push\_front()\) 在序列的头部添加一个元素
\(pop\_back()\) 移除容器尾部的元素
\(pop\_front()\) 移除容器头部的元素
\(insert()\) 在指定的位置插入一个或多个元素
\(erase()\) 移除一个元素或一段元素
\(clear()\) 移出所有的元素，容器大小变为 0
\(swap()\) 交换两个容器的所有元素
\(emplace()\) 在指定的位置直接生成一个元素
\(emplace\_front()\) 在容器头部生成一个元素和 \(push\_front()\) 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程
\(emplace\_back()\) 在容器尾部生成一个元素和 \(push\_back()\) 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程

deque底层实现

deque底层是类似等长的指针数组方式的实现，deque 的数组中存储的是指针，而指针所指的是一段连续的空间(这种结构会导致在 deque 较大的时候 resize 的开销会很大)，这种方式的存储的数据是可以通过计算直接获得指定位置(指在 deque 中的逻辑位置)的地址进而访问或修改的。

deque

个人理解，deque 是 vector 的升级版数据结构，其本质是一个指针数组，但又保持了二维数组等长的特性来维持随机访问的能力，使其具备了在首位高效插入的能力，但相应的也使得 deque 的实现要比 vector 更加的复杂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

template<class _Ty, class _Alloc = allocator<_Ty>>
class deque{
    ...
protected:
    iterator start;  /* map 数组中首个连续空间, 其 cur 指针指向的是连续空间中首个元素 */
    iterator finish;  /* map 数组中最后一个连续空间, 其 cur 指针指向的是连续空间最后一个元素的下一个位置 */
    map_pointer map;  /* 指针数组 map */
...
}
/* deque 迭代器 */
template<class T,...>
struct __deque_iterator{
    ...
    T* cur;  /* 指向当前正在遍历的元素 */
    T* first;  /* 指向当前连续空间的首地址 */
    T* last;  /* 指向当前连续空间的末尾地址 */
    map_pointer node;  /* 等价于 T**，用于指向 map 的数组中存储的指向当前连续空间的指针 */
}

list

list是双向链表(部分是双向循环链表)，不支持随机访问，但可以在 \(O(1)\) 时间内于list任意位置插入/删除(不考虑查找时间)

list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 创建空的list */
list<int> values;
/* 创建含n个初值为x元素的list，不指定初值默认为0 */
list<int> values(n, x = 0);
/* 通过拷贝其他容器创建list(可以拷贝普通数组) */
array<int, 5>arr{ 11,12,13,14,15 };
list<int>values(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}

// constructors used in the same order as described above:
list<int> first;                                // empty list of ints
list<int> second (4,100);                       // four ints with value 100
list<int> third (second.begin(),second.end());  // iterating through second
list<int> fourth (third);                       // a copy of third
// the iterator constructor can also be used to construct from arrays:
int myints[] = {16,2,77,29};
list<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

list特性

  • 顺序：顺序容器中的元素按严格的线性顺序存储
  • 双向链表: 每个元素中包含下一个和上一个元素的位置信息，允许在特定元素（甚至整个范围）之前或之后进行 \(O(1)\) 时间的插入和删除操作，但不能直接随机访问
  • Allocator-aware：容器使用分配器对象动态处理其存储需求

说明：

  • insert的用法
    • iterator insert(pos,elem)在迭代器 pos 指定的位置之前插入一个新元素elem，并返回表示新插入元素位置的迭代器
    • iterator insert(pos,n,elem)在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器
    • iterator insert(pos,first,last)在迭代器 pos 指定的位置之前，插入其他容器区域的所有元素，并返回表示第一个新插入元素位置的迭代器
    • iterator insert(pos,initlist)在迭代器 pos 指定的位置之前，插入初始化列表（用大括号{}括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器
  • splice的用法
    • void splice (iterator position, list& x);
      • position 为迭代器，用于指明插入位置,x 为另一个 list 容器
      • 将 x 容器中存储的所有元素全部移动当前 list 容器中 position 指明的位置处
    • void splice (iterator position, list& x, iterator i);
      • position 为迭代器，用于指明插入位置, x 为另一个 list 容器, i 也是一个迭代器，用于指向 x 容器中某个元素
      • 将 x 容器中 i 指向的元素移动到当前容器中 position 指明的位置处
    • void splice (iterator position, list& x, iterator first, iterator last);
      • position 为迭代器，用于指明插入位置；x 为另一个 list 容器；first 和 last 都是迭代器，[fist,last) 用于指定 x 容器中的某个区域
      • 此格式的 splice() 方法的功能是将 x 容器 [first, last) 范围内所有的元素移动到当前容器 position 指明的位置处 (不包括last)
    • 注意，splice方法对另一个list采用的是引用，移动的结点会从另一个list中移走而不是复制
  • unique: void unique（BinaryPredicate）//传入一个二元谓词函数可以使用lambada表达式(所谓二元谓词函数指有两个参数，返回值为bool)

list成员函数

成员函数 功能
\(begin()\) 返回指向容器中第一个元素的双向迭代器
\(end()\) 返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器
\(rbegin()\) 返回指向最后一个元素的反向双向迭代器
\(rend()\) 返回指向第一个元素所在位置前一个位置的反向双向迭代器
\(cbegin()\) 和 \(begin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(cend()\) 和 \(end()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(crbegin()\) 和 \(rbegin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(crend()\) 和 \(rend()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(empty()\) 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false
\(size()\) 返回当前容器实际包含的元素个数
\(max\_size()\) 返回容器所能包含元素个数的最大值,这通常是一个很大的值，一般是 \(2^{32}-1\)，所以我们很少会用到这个函数
\(front()\) 返回第一个元素的引用
\(back()\) 返回最后一个元素的引用
\(assign()\) 用新元素替换容器中原有内容
\(emplace\_front()\) 在容器头部生成一个元素,该函数和 \(push\_front()\) 的功能相同，但效率更高
\(push\_front()\) 在容器头部插入一个元素
\(pop\_front()\) 删除容器头部的一个元素
\(emplace\_back()\) 在容器尾部直接生成一个元素,该函数和 \(push\_back()\) 的功能相同，但效率更高
\(push\_back()\) 在容器尾部插入一个元素
\(pop\_back()\) 删除容器尾部的一个元素
\(emplace()\) 在容器中的指定位置插入元素,该函数和 \(insert()\) 功能相同，但效率更高
\(insert()\) 在容器中的指定位置插入元素
\(erase()\) 删除容器中一个或某区域内的元素
\(swap()\) 交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的
\(resize()\) 调整容器的大小
\(clear()\) 删除容器存储的所有元素
\(splice()\) 将一个 list 容器中的元素插入到另一个容器的指定位置
\(remove(val)\) 删除容器中所有等于 val 的元素
\(remove\_if()\) 删除容器中满足条件的元素
\(unique()\) 删除容器中相邻的重复元素，只保留一个
\(merge()\) 合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的
\(sort()\) 通过更改容器中元素的位置，将它们进行排序
\(reverse()\) 反转容器中元素的顺序

list底层实现

list底层实现是双向链表(在一些版本如SGI STL中是双向循环链表)，其优缺点是很明确的，优点是可以在任何位置进行常数级的插入和删除甚至移动操作，这和array, vector, deque相比都更高效，缺点是依赖保存前后结点的位置信息消耗额外空间，并且不能随机访问

list2

list就是经典的双向链表的封装，和array, vector, deque相比，list牺牲了随机访问的特性，使其具备了快速的插入删除操作的能力，但线性的查找时间和更大的空间占用使得list的效果有时候并不是那么好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* list 结点 */
template<typename T,...>
struct __List_node{
    // ...
    __list_node<T>* prev;
    __list_node<T>* next;
    T myval;
    // ...
}
/* list实现 */
template <class T,...>
class list
{
    //...
    /* 指向链表的头节点，并不存放数据(就是链表常用的dummy结点、哑结点)
    * 可以使对第一个结点的操作一般化 */
    __list_node<T>* node;
}

forward_list

forward_list是单链表，和list相比效率高一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 创建空的forward_list */
forward_list<int> values;
/* 创建含n个初值为x元素的forward_list，不指定初值默认为0 */
forward_list<int> values(n, x = 0);
/* 通过拷贝其他容器创建forward_list(可以拷贝普通数组) */
array<int, 5>arr{ 11,12,13,14,15 };
forward_list<int>values(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}

// constructors used in the same order as described above:
forward_list<int> first;                      // default: empty
forward_list<int> second (3,77);              // fill: 3 seventy-sevens
forward_list<int> third (second.begin(), second.end()); // range initialization
forward_list<int> fourth (third);            // copy constructor
forward_list<int> fifth (move(fourth));  // move ctor. (fourth wasted)
forward_list<int> sixth = {3, 52, 25, 90};    // initializer_list constructor

forward_list特性

  • 顺序：顺序容器中的元素按严格的线性顺序存储
  • 双向链表: 每个元素中包含下一个元素的位置信息，允许在特定元素（甚至整个范围）之前或之后进行 \(O(1)\) 时间的插入和删除操作，但不能直接随机访问
  • Allocator-aware：容器使用分配器对象动态处理其存储需求

说明：

  • forward_list 不提供size()方法，可以使用distance(begin(forward_list), end(forward_list));的方式获得size()的长度(需要 \(O(n)\) 时间)
  • insert的用法
    • iterator insert(pos,elem)在迭代器 pos 指定的位置之前插入一个新元素elem，并返回表示新插入元素位置的迭代器
    • iterator insert(pos,n,elem)在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器
    • iterator insert(pos,first,last)在迭代器 pos 指定的位置之前，插入其他容器区域的所有元素，并返回表示第一个新插入元素位置的迭代器
    • iterator insert(pos,initlist)在迭代器 pos 指定的位置之前，插入初始化列表（用大括号{}括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器
  • splice的用法
    • void splice (iterator position, forward_list& x);
      • position 为迭代器，用于指明插入位置,x 为另一个 forward_list 容器
      • 将 x 容器中存储的所有元素全部移动当前 forward_list 容器中 position 指明的位置处
    • void splice (iterator position, forward_list& x, iterator i);
      • position 为迭代器，用于指明插入位置, x 为另一个 forward_list 容器, i 也是一个迭代器，用于指向 x 容器中某个元素
      • 将 x 容器中 i 指向的元素移动到当前容器中 position 指明的位置处
    • void splice (iterator position, forward_list& x, iterator first, iterator last);
      • position 为迭代器，用于指明插入位置；x 为另一个 forward_list 容器；first 和 last 都是迭代器，[fist,last) 用于指定 x 容器中的某个区域
      • 此格式的 splice() 方法的功能是将 x 容器 [first, last) 范围内所有的元素移动到当前容器 position 指明的位置处 (不包括last)
    • 注意，splice方法对另一个forward_list采用的是引用，移动的结点会从另一个forward_list中移走而不是复制
  • unique: void unique（BinaryPredicate）//传入一个二元谓词函数可以使用lambada表达式(所谓二元谓词函数指有两个参数，返回值为bool)

forward_list成员函数

成员函数 功能
\(before\_begin()\) 返回一个前向迭代器，其指向容器中第一个元素之前的位置(dummy结点)
\(begin()\) 返回一个前向迭代器，其指向容器中第一个元素的位置
\(end()\) 返回一个前向迭代器，其指向容器中最后一个元素之后的位置
\(cbefore\_begin()\) 和 \(before\_begin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(cbegin()\) 和 \(begin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(cend()\) 和 \(end()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
\(empty()\) 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false
\(max\_size()\) 返回容器所能包含元素个数的最大值, 这通常是一个很大的值，一般是 \(2^{32}-1\)，所以我们很少会用到这个函数
\(front()\) 返回第一个元素的引用
\(assign()\) 用新元素替换容器中原有内容
\(push\_front()\) 在容器头部插入一个元素
\(emplace\_front()\) 在容器头部生成一个元素, 该函数和 \(push\_front()\) 的功能相同，但效率更高
\(pop\_front()\) 删除容器头部的一个元素
\(emplace\_after()\) 在指定位置之后插入一个新元素，并返回一个指向新元素的迭代器, 和 \(insert\_after()\) 的功能相同，但效率更高
\(insert\_after()\) 在指定位置之后插入一个新元素，并返回一个指向新元素的迭代器
\(erase\_after()\) 删除容器中某个指定位置或区域内的所有元素
\(swap()\) 交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的
\(resize()\) 调整容器的大小
\(clear()\) 删除容器存储的所有元素
\(splice\_after()\) 将某个 forward_list 容器中指定位置或区域内的元素插入到另一个容器的指定位置之后
\(remove(val)\) 删除容器中所有等于 val 的元素
\(remove\_if()\) 删除容器中满足条件的元素
\(unique()\) 删除容器中相邻的重复元素，只保留一个
\(merge()\) 合并两个事先已排好序的 forward_list 容器，并且合并之后的 forward_list 容器依然是有序的
\(sort()\) 通过更改容器中元素的位置，将它们进行排序
\(reverse()\) 反转容器中元素的顺序

关联型容器

pair

pair是封装好的键值对对象，有两个基本元素<first, second>

1
2
3
4
5
6
/* 创建键值对对象 */
pair<int, string> p;
pair<int, string> q(2, "abc");
pair<int, string> r(q);
p.first = 1;
p.second = "I love you!";

pair重载了 <、<=、>、>=、==、!= 运算符，但比较的pair对象必须是相同的键值类型

map

map是有序的存储键值对pair的容器，默认升序，键值对不可重复

类模板如下：

1
2
3
4
5
template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;
1
2
3
4
5
6
/* 创建空的map */
map<string, int> tree;
/* 带初始值的map */
map<string, int> tree{{"abc", 1}, {"xyz", 2}};
/* 降序排列的map */
map<string, int, greater<string>> tree{{"abc", 1}, {"xyz", 2}};

map特性

  • 关联: 关联容器中的元素是由键而不是在容器中的绝对位置来引用的
  • 顺序: 容器中的元素始终保持指定的顺序。所有插入的元素均按此顺序分配空间
  • 表: 每个元素都将键与映射值相关联, 键用于标识元素的映射值
  • key唯一: 容器中没有两个元素可以具有等效key(广义等于，即!comp(a,b) && !comp(b,a)为真)
  • Allocator-aware：容器使用分配器对象动态处理其存储需求

map成员函数

成员函数 功能
\(begin()\) 返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器,如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器
\(end()\) 返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 \(begin()\) 结合使用,如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器
\(rbegin()\) 返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器,如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器
\(rend()\) 返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器,如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器
\(cbegin()\) 和 \(begin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对
\(cend()\) 和 \(end()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对
\(crbegin()\) 和 \(rbegin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对
\(crend()\) 和 \(rend()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对
\(empty()\) 若容器为空，则返回 true；否则 false
\(size()\) 返回当前 map 容器中存有键值对的个数
\(max\_size()\) 返回 map 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同
\(operator[]\) map容器重载了 [] 运算符，只要知道 map 容器中某个键值对的键的值，就可以向获取数组中元素那样，通过键直接获取对应的值
\(at(key)\) 找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_range 异常
\(insert()\) 向 map 容器中插入键值对
\(erase()\) 删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对
\(swap()\) 交换 2 个 map 容器中存储的键值对，这意味着，操作的 2 个键值对的类型必须相同
\(clear()\) 清空 map 容器中所有的键值对，即使 map 容器的 \(size()\) 为 0
\(emplace()\) 在当前 map 容器中的指定位置处构造新键值对,其效果和插入键值对一样，但效率更高
\(emplace\_hint()\) 在本质上和 \(emplace()\) 在 map 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数
\(find(key)\) 在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 \(end()\) 方法一样的迭代器,另外，如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器
\(lower\_bound(key)\) 返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器,如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器
\(upper\_bound(key)\) 返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器,如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器
\(equal\_range(key)\) 该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价,也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）
\(count(key)\) 在当前 map 容器中，查找键为 key 的键值对的个数并返回,注意，由于 map 容器中各键值对的键的值是唯一的，因此该函数的返回值最大为 1

multimap

multimap和map相比允许key重复，同时不提供at()和opertor[]方法，其他和map类似，不再重复

set

set是按顺序存储唯一元素的容器，容器中元素不允许修改，但可以删除和添加

1
2
3
4
emplate < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;
1
2
3
4
5
6
/* 创建空的set */
set<string> myset;
/* 带初始值的set */
set<string> myset{"abc", "xyz"};
/* 降序排列的set */
set<string, greater<string>> myset{"abc", "xyz"};

set成员函数

成员函数 功能
\(begin()\) 返回指向容器中第一个（注意，是已排好序的第一个）元素的双向迭代器,如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器
\(end()\) 返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 \(begin()\) 结合使用,如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器
\(rbegin()\) 返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器,如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器
\(rend()\) 返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器,如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器
\(cbegin()\) 和 \(begin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值
\(cend()\) 和 \(end()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值
\(crbegin()\) 和 \(rbegin()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值
\(crend()\) 和 \(rend()\) 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值
\(find(val)\) 在 set 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回和 end() 方法一样的迭代器,另外，如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器
\(lower\_bound(val)\) 返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器,如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器
\(upper\_bound(val)\) 返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器,如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器
\(equal\_range(val)\) 该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 \(lower_bound()\) 方法的返回值等价，pair.second 和 \(upper\_bound()\) 方法的返回值等价,也就是说，该方法将返回一个范围，该范围中包含的值为 val 的元素（set 容器中各个元素是唯一的，因此该范围最多包含一个元素）
\(empty()\) 若容器为空，则返回 true；否则 false
\(size()\) 返回当前 set 容器中存有元素的个数
\(max\_size()\) 返回 set 容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同
\(insert()\) 向 set 容器中插入元素
\(erase()\) 删除 set 容器中存储的元素
\(swap()\) 交换 2 个 set 容器中存储的所有元素, 这意味着，操作的 2 个 set 容器的类型必须相同
\(clear()\) 清空 set 容器中所有的元素，即令 set 容器的 \(size()\) 为 0
\(emplace()\) 在当前 set 容器中的指定位置直接构造新元素,其效果和 \(insert()\) 一样，但效率更高
\(emplace\_hint()\) 在本质上和 \(emplace()\) 在 set 容器中构造新元素的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示新元素生成位置的迭代器，并作为该方法的第一个参数
\(count(val)\) 在当前 set 容器中，查找值为 val 的元素的个数，并返回,注意，由于 set 容器中各元素的值是唯一的，因此该函数的返回值最大为 1

multiset

mulitiset允许存储重复值，其他与set基本相同

红黑树

map, multimap, set, multiset的底层实现都是红黑树，红黑树是一种特殊的二叉搜索树，它具有以下的性质：

  1. 每一个结点染色为红色或黑色
  2. 根节点是黑色的
  3. 如果一个结点是红色的，那么它的孩子结点必须是黑色的
  4. 从一个结点到NULL指针的每一条路径必须包含相同数目的黑色结点

红黑树是弱平衡的二叉搜索树，它可以保证高度最多为 \(2log(N+1)\), 其插入、删除、查找操作时间复杂度均为 \(O(logN)\)

红黑树的具体实现比较复杂，不理解的话可以将其当成不严格平衡的“平衡二叉树”，但又能保证“平衡二叉树”不会出现较坏的情况

无序关联型容器

无序型容器也采用键值对pair的方式存储数据，但其底层采用了哈希表的方法存储，因此其查找的效率比红黑树为底层的关联型容器要高，但遍历效率不如有序关联型容器

unordered_map

unordered_map的模板定义如下:

1
2
3
4
5
6
template < class Key,                        //键值对中键的类型
           class T,                          //键值对中值的类型
           class Hash = hash<Key>,           //容器内部存储键值对所用的哈希函数
           class Pred = equal_to<Key>,       //判断各个键值对键相同的规则
           class Alloc = allocator< pair<const Key,T> >  // 指定分配器对象的类型
           > class unordered_map;

哈希函数和键相等规则只适用于基本数据类型，对于自定义类型的key需要自定义hash函数和pred规则并显式传递

1
2
3
4
5
6
/* 创建空的unordered_map */
unordered_map<string, string> h;
/* 通过重载=运算符赋初值 */
h = {{"GOOG","Google"},{"ORCL","Oracle"}};
/* 带初始值的map */
unordered_map<string, int> h{{"abc", 1}, {"xyz", 2}};

unordered_map特性

  • 关联: 关联容器中的元素是由键而不是在容器中的绝对位置来引用的
  • 无序: 无序容器使用哈希表组织其元素，允许通过key快速访问元素
  • 表: 每个元素都将键与映射值相关联, 键用于标识元素的映射值
  • key唯一: 容器中没有两个元素可以具有等效key(广义等于，即!comp(a,b) && !comp(b,a)为真)
  • Allocator-aware：容器使用分配器对象动态处理其存储需求

pred函数接受两个类型与key相同的参数，返回值为bool，若返回true，表示传入的两个key相同，反之不同

unordered_map成员函数

成员函数 功能
\(begin()\) 返回指向容器中第一个键值对的正向迭代器
\(end()\) 返回指向容器中最后一个键值对之后位置的正向迭代器
\(cbegin()\) 和 \(begin()\) 功能相同，只不过在其基础上增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对
\(cend()\) 和 \(end()\) 功能相同，只不过在其基础上，增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对
\(empty()\) 若容器为空，则返回 true；否则 false
\(size()\) 返回当前容器中存有键值对的个数
\(max\_size()\) 返回容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同
\(operator[key]\) 该模板类中重载了 [] 运算符，其功能是可以向访问数组中元素那样，只要给定某个键值对的键 key，就可以获取该键对应的值,注意，如果当前容器中没有以 key 为键的键值对，则其会使用该键向当前容器中插入一个新键值对
\(at(key)\) 返回容器中存储的键 key 对应的值，如果 key 不存在，则会抛出 out_of_range 异常
\(find(key)\) 查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 \(end()\) 方法返回的迭代器）
\(count(key)\) 在容器中查找以 key 键的键值对的个数
\(equal\_range(key)\) 返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围
\(emplace()\) 向容器中添加新键值对，返回一个pair类型，其中第一个值为新插入的位置的迭代器，第二个值为bool，表示插入是否成功(若插入重复值会插入失败)
\(emplace\_hint()\) 向容器中添加新键值对，效率比 \(insert()\) 方法高，返回迭代器
\(insert()\) 向容器中添加新键值对
\(erase()\) 删除指定键值对
\(clear()\) 清空容器，即删除容器中存储的所有键值对
\(swap()\) 交换 2 个 unordered_map 容器存储的键值对，前提是必须保证这 2 个容器的类型完全相等
\(bucket\_count()\) 返回当前容器底层存储键值对时，使用桶（一个线性链表代表一个桶）的数量
\(max\_bucket\_count()\) 返回当前系统中，unordered_map 容器底层最多可以使用多少桶
\(bucket\_size(n)\) 返回第 n 个桶中存储键值对的数量
\(bucket(key)\) 返回以 key 为键的键值对所在桶的编号
\(load\_factor()\) 返回 unordered_map 容器中当前的负载因子,负载因子，指的是的当前容器中存储键值对的数量（\(size()\)）和使用桶数（\(bucket\_count()\)）的比值，即 \(load\_factor() = size() / bucket\_count()\)
\(max\_load\_factor()\) 返回或者设置当前 unordered_map 容器的负载因子
\(rehash(n)\) 将当前容器底层使用桶的数量设置为 n
\(reserve()\) 将存储桶的数量（也就是 \(bucket\_count()\) 方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器
\(hash\_function()\) 返回当前容器使用的哈希函数对象

unordered_multimap

除了可以插入重复key的元素以外与unordered_map完全相同

unordered_set

定义如下

1
2
3
4
5
template < class Key,            //容器中存储元素的类型
           class Hash = hash<Key>,    //确定元素存储位置所用的哈希函数
           class Pred = equal_to<Key>,   //判断各个元素是否相等所用的函数
           class Alloc = allocator<Key>   //指定分配器对象的类型
           > class unordered_set;

与set类似，但底层是哈希表，通常只需指定第一个参数，但若是存储的key为自定义类型则需显式的传入hash函数和pred规则

1
2
3
4
5
6
7
8
9
10
/* 创建空的set容器 */
unordered_set<string> first;                                // empty
/* 带初值的set容器 */
unordered_set<string> second ( {"red","green","blue"} );    // init list
unordered_set<string> third ( {"orange","pink","yellow"} ); // init list
/* 复制set创建新的set */
unordered_set<string> fourth ( second );                    // copy
unordered_set<string> fifth ( cmerge(third,fourth) );       // move
/* 局部复制 */
unordered_set<string> sixth ( fifth.begin(), fifth.end() ); // range

unordered_set特性

  • 关联性：关联容器中的元素是由其键而不是其在容器中的绝对位置来引用的
  • 无序性：无序容器使用哈希表组织其元素，该哈希表允许通过其键快速访问元素
  • 集合性：元素的值也是用于标识它的键
  • 键唯一：容器中没有两个元素可以具有等效键

unordered_set成员函数

成员函数 功能
\(begin()\) 返回指向容器中第一个元素的正向迭代器
\(end()\) 返回指向容器中最后一个元素之后位置的正向迭代器
\(cbegin()\) 和 \(begin()\) 功能相同，只不过其返回的是 const 类型的正向迭代器
\(cend()\) 和 \(end()\) 功能相同，只不过其返回的是 const 类型的正向迭代器
\(empty()\) 若容器为空，则返回 true；否则 false
\(size()\) 返回当前容器中存有元素的个数
\(max\_size()\) 返回容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同
\(find(key)\) 查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器（等同 \(end()\) 方法返回的迭代器）
\(count(key)\) 在容器中查找值为 key 的元素的个数
\(equal\_range(key)\) 返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中值为 key 的元素所在的范围
\(emplace()\) 向容器中添加新元素，效率比 \(insert()\) 方法高
\(emplace\_hint()\) 向容器中添加新元素，效率比 \(insert()\) 方法高
\(insert()\) 向容器中添加新元素
\(erase()\) 删除指定元素
\(clear()\) 清空容器，即删除容器中存储的所有元素
\(swap()\) 交换 2 个 unordered_map 容器存储的元素，前提是必须保证这 2 个容器的类型完全相等
\(bucket\_count()\) 返回当前容器底层存储元素时，使用桶（一个线性链表代表一个桶）的数量
\(max\_bucket\_count()\) 返回当前系统中，unordered_map 容器底层最多可以使用多少桶
\(bucket\_size(n)\) 返回第 n 个桶中存储元素的数量
\(bucket(key)\) 返回值为 key 的元素所在桶的编号
\(load\_factor()\) 返回 unordered_map 容器中当前的负载因子,负载因子，指的是的当前容器中存储元素的数量（\(size()\)）和使用桶数（\(bucket\_count()\)）的比值，即 \(load\_factor() = size() / bucket\_count()\)
\(max\_load\_factor()\) 返回或者设置当前 unordered_map 容器的负载因子
\(rehash(n)\) 将当前容器底层使用桶的数量设置为 n
\(reserve()\) 将存储桶的数量（也就是 \(bucket\_count()\) 方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器
\(hash\_function()\) 返回当前容器使用的哈希函数对象

unordered_multiset

除了能存储重复元素以外，unordered_multiset与unordered_set完全相同

hashmap

无序型容器的底层均为哈希表，对哈希冲突采用链地址法(拉链法)，哈希表通常采用vector容器存储表，将vector中的空位/链表称为(bucket)桶, 负载因子表示键值对数目与桶的比值，一般负载因子达到1.0以后就会发生扩容并rehash, 一般认为hash的查找、插入、删除均为 \(O(1)\) 复杂度，但一个不合理的hash函数可能会使得hashmap的各项效率退化为 \(O(n)\)

适配器容器

指通过封装已有的容器使得满足某些特定的场合，模板参数一般由 <数据类型T, 底层容器类型Container> 组成

stack

Stack 是 LIFO(先进后出) 类型的数据结构，中文称为栈(zhan)，要求底层容器支持 empty, size, back, push_back, pop_back 操作，\(vector\) , \(deque\) , \(list\) 满足要求，默认使用 \(deque\)

1
2
3
4
5
6
7
8
deque<int> mydeque (3,100);          // deque with 3 elements
vector<int> myvector (2,200);        // vector with 2 elements

stack<int> first;                    // empty stack
stack<int> second (mydeque);         // stack initialized to copy of deque

stack<int,vector<int> > third;  // empty stack using vector
stack<int,vector<int> > fourth (myvector);

stack成员函数

成员函数 功能
\(empty()\) 当 stack 栈中没有元素时，该成员函数返回 true；反之，返回 false
\(size()\) 返回 stack 栈中存储元素的个数
\(top()\) 返回一个栈顶元素的引用，类型为 T& , 如果栈为空，程序会报错
\(push(const T\& val)\) 先复制 val，再将 val 副本压入栈顶, 这是通过调用底层容器的 \(push\_back()\) 函数完成的
\(push(T\&\& obj)\) 以移动元素的方式将其压入栈顶, 这是通过调用底层容器的有右值引用参数的 \(push\_back()\) 函数完成的
\(pop()\) 弹出栈顶元素
\(emplace(arg...)\) arg... 可以是一个参数，也可以是多个参数，但它们都只用于构造一个对象，并在栈顶直接生成该对象，作为新的栈顶元素
\(swap(stack < T > \& other\_stack)\) 将两个 stack 适配器中的元素进行互换，需要注意的是，进行互换的 2 个 stack 适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同

queue

Queue是 FIFO(先进先出) 类型的数据结构，中文称为队列，要求底层容器支持 empty, size, front, back, push_back, pop_front 操作，\(deque\) , \(list\) 满足要求，默认使用 \(deque\)

1
2
3
4
5
6
7
8
deque<int> mydeck (3,100);        // deque with 3 elements
list<int> mylist (2,200);         // list with 2 elements

queue<int> first;                 // empty queue
queue<int> second (mydeck);       // queue initialized to copy of deque

queue<int,list<int> > third; // empty queue with list as underlying container
queue<int,list<int> > fourth (mylist);

queue成员函数

成员函数 功能
\(empty()\) 如果 queue 中没有元素的话，返回 true
\(size()\) 返回 queue 中元素的个数
\(front()\) 返回 queue 中第一个元素的引用,如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的
\(back()\) 返回 queue 中最后一个元素的引用,如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的
\(push(const T\& obj)\) 在 queue 的尾部添加一个元素的副本,这是通过调用底层容器的成员函数 \(push\_back()\) 来完成的
\(emplace()\) 在 queue 的尾部直接添加一个元素
\(push(T\&\& obj)\) 以移动的方式在 queue 的尾部添加元素,这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的
\(pop()\) 删除 queue 中的第一个元素
\(swap(queue < T > \&other\_queue)\) 将两个 queue 容器适配器中的元素进行互换，需要注意的是，进行互换的 2 个 queue 容器适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同

priority_queue

priority_queue 是优先队列，队列中的最大/最小元素优先出队，要求底层容器支持 empty, size, front, push_back, pop_back 操作，\(deque\) , \(vector\) 满足要求，默认使用 \(vector\)

相比前两个适配型容器，priority_queue的模板参数增加了 Compare，即比较函数，形参为两个类型为T的元素(a, b) ，返回值为bool，规定若 a 在 b 之前则返回true，默认值为 less<T>(相当于 a < b), 即大顶堆，若设为 greater<T> 则为小顶堆

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
/* 自定义比较函数 */
class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (const int& lhs, const int&rhs) const
  {
    if (reverse) return (lhs>rhs);
    else return (lhs<rhs);
  }
};

int myints[]= {10,60,50,20};
/* 空优先队列 */
priority_queue<int> first;
/* 大顶堆(60在顶部) */
priority_queue<int> second (myints,myints+4);
/* 小顶堆(10在顶部) */
priority_queue<int, vector<int>, greater<int> > third (myints,myints+4);
// using mycomparison:
// less-than comparison
priority_queue<int,vector<int>,mycomparison> fourth;
// greater-than comparison
priority_queue<int,vector<int>,mycomparison> fifth (mycomparison(true));

priority_queue成员函数

成员函数 功能
\(empty()\) 如果 priority_queue 为空的话，返回 true；反之，返回 false
\(size()\) 返回 priority_queue 中存储元素的个数
\(top()\) 返回 priority_queue 中第一个元素的引用形式
\(push(const T\& obj)\) 根据既定的排序规则，将元素 obj 的副本存储到 priority_queue 中适当的位置
\(push(T\&\& obj)\) 根据既定的排序规则，将元素 obj 移动存储到 priority_queue 中适当的位置
\(emplace(Args\&\&... args)\) Args&&... args 表示构造一个存储类型的元素所需要的数据（对于类对象来说，可能需要多个数据构造出一个对象）, 此函数的功能是根据既定的排序规则，在容器适配器适当的位置直接生成该新元素
\(pop()\) 移除 priority_queue 容器适配器中第一个元素
\(swap(priority\_queue < T > \& other)\) 将两个 priority_queue 容器适配器中的元素进行互换，需要注意的是，进行互换的 2 个 priority_queue 容器适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同

常用算法

STL中的关系运算符

关系 功能
\(less < T >\) 底层采用 \(<\) 运算符实现升序排序
\(greater < T >\) 底层采用 \(>\) 运算符实现降序排序
\(less\_equal < T >\) 底层采用 \(<=\) 运算符实现升序排序
\(greater\_equal < T >\) 底层采用 \(>=\) 运算符实现降序排序

排序函数

函数名 用法
\(sort (first, last)\) 对容器或普通数组中 \([first, last)\) 范围内的元素进行排序，默认进行升序排序
\(stable\_sort (first, last)\) 和 \(sort()\) 函数功能相似，不同之处在于，对于 \([first, last)\) 范围内值相同的元素，该函数不会改变它们的相对位置
\(partial\_sort (first, middle, last)\) 从 \([first,last)\) 范围内，筛选出 \(middle-first\) 个最小的元素并排序存放在 \([first，middle)\) 区间中
\(partial\_sort\_copy (first, last, result\_first, result\_last)\) 从 \([first, last)\) 范围内筛选出 result_last ~ result_first 个元素排序并存储到 \([result\_first, result\_last)\) 指定的范围中
\(is\_sorted (first, last)\) 检测 \([first, last)\) 范围内是否已经排好序，默认检测是否按升序排序
\(is\_sorted\_until (first, last)\) 和 \(is\_sorted()\) 函数功能类似，唯一的区别在于，如果 \([first, last)\) 范围的元素没有排好序，则该函数会返回一个指向首个不遵循排序规则的元素的迭代器
\(void\;nth\_element (first, nth, last)\) 找到 \([first, last)\) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置,同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大

其中，

  • \(sort()\) 基于快速排序
  • \(stable\_sort()\) 基于归并排序
  • \(partial\_sort()\) 通过筛选出 \(middle-first\) 个元素并移动到 \([first，middle)\) 区间再进行排序，平均时间复杂度为 \(O(Nlog(M))\) (\(N\)是选取范围长度, \(M\)是排序元素数量), 带copy后缀的不移动而是复制到新容器中排序，平均时间复杂度为 \(O(Nlog(min(N,M)))\)
  • \(nth\_element\) 猜测是快速查找
  • 上述排序相关函数均支持自定义比较函数 comp

二分查找

函数 功能
\(lower\_bound(first,last,val)\) 返回指向 \([first,last)\) 范围内不小于val的的第一个元素的迭代器
\(upper\_bound(first,last,val)\) 返回指向 \([first,last)\) 范围内大于val的的第一个元素的迭代器
\(equal\_range(first,last,val)\) 返回pair类型，其值分别与 \(lower\_bound()\) 和 \(upper\_bound()\)的返回值相同，即返回与 val 值相同的范围的迭代器
\(binary\_search(first,last,val)\) 返回值为bool，在 \([firs,last)\) 范围内二分查找val，查找到则返回 true, 否则返回 false

注：二分查找的四个函数均支持第四个参数 comp 即自定义比较函数

最值

函数 功能
\(max(a,b)\) 返回 a,b 中大的那个，如果两个相等则返回 a
\(max\_element(first, last)\) 返回区间 \([first,last)\) 范围内的最大值的迭代器
\(min(a,b)\) 返回 a,b 中小的那个，如果两个相等则返回 a
\(min\_element(first, last)\) 返回区间 \([first,last)\) 范围内的最小值的迭代器
\(minmax(a,b)\) 返回 (小元素,大元素) 的 pair 对象，若ab相等则返回 (a,b)
\(minmax\_element(a,b)\) 返回区间 \([first,last)\) 范围内 (最小元素,最大元素) 的 pair 对象

注：最值的六个函数均支持第三个参数 comp 即自定义比较函数

计数and交换and反转

函数 功能
\(count(first,last,val)\) 返回区间 \([first,last)\) 范围内的 val 出现次数
\(swap(a,b)\) 交换 a,b 的值(大多数容器也能交换)
\(reverse(first,last)\) 反转区间 \([first,last)\) 范围中元素顺序

赋值函数

函数 功能
\(fill(first,last,val)\) 将 val 分配给区间 \([first,last)\) 范围内的所有元素
\(fill\_n(first,n,val)\) 将 val 分配给 first开始的 n 个元素
\(generate(first,last,gen)\) 连续调用 gen(无参数，返回元素值) 给区间 \([first,last)\) 范围内的元素赋值
\(generate\_n(first,n,gen)\) 连续调用 gen(无参数，返回元素值) 给 first开始的 n 个元素赋值
\(for\_each(first,last,fn)\) 对区间 \([first,last)\) 范围内的每个元素调用 fn(元素做参数，无返回值)

参考资料

--- ♥ end ♥ ---

欢迎关注我呀~