2020-07-28 11acf3ea978a41cafbf0d046034a6d13 99+ 8 分钟 1.2 k 0次访问

C++STL知识点简析

STL

一、STL 简介

Standard Template Library，标准模板库，是 C++ 的标准库之一，一套基于模板的容器类库，还包括许多常用的算法，提高了程序开发效率和复用性。STL 包含 6 大部件：容器、迭代器、算法、仿函数、适配器和空间配置器。

容器：容纳一组元素的对象。
迭代器：提供一种访问容器中每个元素的方法。
函数对象：一个行为类似函数的对象，调用它就像调用函数一样。
算法：包括查找算法、排序算法等等。
适配器：用来修饰容器等，比如 queue 和 stack，底层借助了 deque。
空间配置器：负责空间配置和管理。

二、STL 空间配置器

对象构造前的空间配置和对象析构后的空间释放，由 <stl_alloc.h> 负责，SGI 对此的设计哲学如下：

向 system heap 申请空间。
考虑多线程状态。
考虑内存不足时的应变措施。
考虑过多“小型区块”可能造成的内存碎片问题。

考虑小型区块造成的内存破碎问题，SGI 设计了双层级配置器：

第一级直接使用 allocate() 调用 malloc()、deallocate() 调用 free()，使用类似new_handler 机制解决内存不足（抛出异常），配置无法满足的问题（如果在申请动态内存时找不到足够大的内存块，malloc 和 new 将返回 NULL 指针，宣告内存申请失败）。
第二级视情况使用不同的策略，当配置区块大于 128 bytes 时，调用第一级配置器，当配置区块小于 128 bytes 时，采用内存池的方式：配置器维护 16 个（128/8）自由链表，负责 16 种小型区块的配置能力。内存池以 malloc 配置而得，如果内存不足转第一级配置器处理。

1、第二级空间配置器详解

第二级空间配置器实际上是一个内存池，维护了 16 个自由链表。自由链表是一个指针数组，有点类似 hash 桶，它的数组大小为 16，每个数组元素代表所挂的区块大小，比如 free_list[0] 代表下面挂的是 8 bytes 的区块，free_list[1] 代表下面挂的是 16 bytes 的区块。依次类推，直到 free_list[15] 代表下面挂的是 128 bytes 的区块。

2、空间配置器存在的问题

自由链表所挂区块都是 8 的整数倍，因此当我们需要非 8 倍数的区块，往往会导致浪费。
由于配置器的所有方法，成员都是静态的，都存放在静态区。释放时机就是程序结束，这样会导致自由链表一直占用内存，自己进程可以用，其他进程却用不了。

三、STL 各种容器

vector
可变大小的数组。支持快速随机访问，在尾部之外的位置插入和删除元素可能会很慢。
deque
双端队列。支持快速随机访问，在头尾位置插入/删除速度很快。
list
只支持双向顺序访问。在 list 任何位置插入/删除速度很快。
forward_list
单向链表。只支持单向顺序访问。在 forward_list 任何位置插入/删除速度很快。
array
固定大小的数组。支持快速随机访问，不能添加或者删除元素。
string
与 vector 相似的容器，专门存储字符。随机访问快。在尾位置插入/删除速度很快。

支持随机访问的容器：vector、deque、array、string。

支持在任意位置插入/删除元素：list、forward_list。

在尾部插入元素：vector、string、deque（头部也可以）。

vector

1、vector 的底层原理

vector 底层是一个动态数组，包含三个迭代器，start 和 finish 之间是已经被使用的空间范围，end_of_storage 是整块连续空间包括备用空间的尾部。

当空间不够装下数据（vec.push_back(val)）时，会自动申请另一片更大的空间（1.5 倍或者 2 倍），然后把原来的数据拷贝到新的内存空间，接着释放原来的那片空间（vector 内存增长机制）。

当释放或者删除（vec.clear()）里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。

因此，对 vector 的任何操作一旦引起了空间的重新配置，指向原 vector 的所有迭代器会都失效了。

2、vector 中的 reserve() 和 resize() 的区别

resize(n)
调整容器的长度大小，使其能容纳 n 个元素。如果 n 小于容器的当前的 size，则删除多出来的元素。否则，添加采用值初始化的元素。
resize(n，t)
多一个参数 t，将所有新添加的元素初始化为 t。
reserve(n)
预分配 n 个元素的存储空间。

reserve() 是直接扩充到已经确定的大小，可以减少多次开辟、释放空间的问题（优化 push_back()），其次还可以减少多次要拷贝数据的问题。reserve() 只是保证 vector 中的空间大小（capacity）最少达到参数所指定的大小 n。reserve() 只有一个参数。

resize() 可以改变有效空间的大小，也有改变默认值的功能。capacity 的大小也会随着改变。resize() 可以有多个参数。

3、容器的 capacity（容量）与 size（长度）的区别

size 指容器当前拥有的元素个数，而 capacity 则指容器在必须分配新存储空间之前可以存储的元素总数，也可以说是预分配存储空间的大小。

resize() 函数和容器的 size 息息相关。调用 resize(n) 后，容器的 size 即为 n。至于是否影响 capacity，取决于调整后的容器的 size 是否大于 capacity。

reserve() 函数和容器的 capacity 息息相关。调用 reserve(n) 后，若容器的 capacity < n，则重新分配内存空间，从而使得 capacity 等于n。如果 capacity >=n 呢？capacity 无变化。

从两个函数的用途可以发现，容器调用 resize() 函数后，所有的空间都已经初始化了，所以可以直接访问。而 reserve() 函数预分配出的空间没有被初始化，所以不可访问。

4、迭代器失效的情况

当插入一个元素到 vector 中，由于引起了内存重新分配，所以指向原内存的迭代器全部失效。

当删除容器中一个元素后，该迭代器所指向的元素已经被删除，那么也造成迭代器失效。erase 方法会返回下一个有效的迭代器，所以当我们要删除某个元素时，需要 it = vec.erase(it);。

5、vector 的元素类型可以是引用吗？

vector 的底层实现要求连续的对象排列，引用并非对象，没有实际地址，因此 vector 的元素类型不能是引用。

6、正确释放 vector 的内存（clear()、swap()、shrink_to_fit()）

vec.clear();              // 清空内容，但是不释放内存。
vector<int>().swap(vec);  // 清空内容，且释放内存，得到一个全新的 vector。
vec.shrink_to_fit();      // 请求容器降低其 capacity 和 size 匹配。
vec.clear(); vec.shrink_to_fit();  // 清空内容，且释放内存。

std::vector::clear()

Removes all elements from the vector (which are destroyed), leaving the container with a size of 0.

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    cout << "size:" << v.size() << endl;
    cout << "capacity:" << v.capacity() << endl;

    v.clear();
    cout << "after clear size:" << v.size() << endl;
    cout << "after clear capacity:" << v.capacity() << endl;
    return 0;
}
//输出
size:5
capacity:6
after clear size:0
after clear capacity:6

A reallocation is not guaranteed to happen, and the vector capacity is not guaranteed to change due to calling this function. A typical alternative that forces a reallocation is to use swap.

std::vector::swap

Exchanges the content of the container by the content of x, which is another vector object of the same type. Sizes may differ.

After the call to this member function, the elements in this container are those which were in x before the call, and the elements of x are those which were in this. All iterators, references and pointers remain valid for the swapped objects.

Notice that a non-member function exists with the same name, swap, overloading that algorithm with an optimization that behaves like this member function.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> foo;
    foo.push_back(1);
    foo.push_back(2);
    foo.push_back(3);
    foo.push_back(4);
    foo.push_back(5);

    std::vector<int> bar;  
    bar.push_back(1);
    bar.push_back(2);


    std::cout << "foo size:" << foo.size() << std::endl;
    std::cout << "foo capacity:" << foo.capacity() << std::endl;

    std::cout << "bar size:" << bar.size() << std::endl;
    std::cout << "bar capacity:" << bar.capacity() << std::endl;
    foo.swap(bar);

    std::cout << "after swap foo size:" << foo.size() << std::endl;
    std::cout << "after swap foo capacity:" << foo.capacity() << std::endl;

    std::cout << "after swap bar size:" << bar.size() << std::endl;
    std::cout << "after swap bar capacity:" << bar.capacity() << std::endl;

    return 0;
}
//输出：
foo size:5
foo capacity:6
bar size:2
bar capacity:2
after swap foo size:2
after swap foo capacity:2
after swap bar size:5
after swap bar capacity:6

swap 之后，不仅仅是 size 变化了，capacity 也是变化了。用 swap 实现真正的 clear。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    cout << "size:" << v.size() << endl;
    cout << "capacity:" << v.capacity() << endl;

    vector<int>().swap(v);
    cout << "after swap size:" << v.size() << endl;
    cout << "after swap capacity:" << v.capacity() << endl;
    return 0;
}
//输出：
size:5
capacity:6
after swap size:0
after swap capacity:0

C++11 推出了 shrink_to_fit 方法，也可以达到正确释放 vector 的内存的目的。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    cout << "size:" << v.size() << endl;
    cout << "capacity:" << v.capacity() << endl;

    v.clear();
    v.shrink_to_fit();
    cout << "after swap size:" << v.size() << endl;
    cout << "after swap capacity:" << v.capacity() << endl;
    return 0;
}
//输出：
size:5
capacity:6
after swap size:0
after swap capacity:0

7、vector 扩容为什么要以 1.5 倍或者 2 倍扩容？

根据查阅的资料显示，考虑可能产生的堆空间浪费，成倍增长倍数不能太大，使用较为广泛的扩容方式有两种，以 2 倍的方式扩容，或者以 1.5 倍的方式扩容。

以 2 倍的方式扩容，导致下一次申请的内存必然大于之前分配内存的总和，导致之前分配的内存不能再被使用，所以最好倍增长因子设置为（1-2）之间：

$$k\sum_{i=0}^{n}2^i = k(2^{n+1} - 1) < k2^{n+1} $$

8、vector 的常用函数

vector<int> vec(10, 100);           // 创建10个元素,每个元素值为100
vec.resize(r, vector<int>(c, 0));   // 二维数组初始化
reverse(vec.begin(), vec.end())     // 将元素翻转
sort(vec.begin(), vec.end());       // 排序，默认升序排列
vec.push_back(val);                 // 尾部插入数字
vec.size();                         // 向量大小
find(vec.begin(), vec.end(), 1);    // 查找元素
iterator = vec.erase(iterator)      // 删除元素

9、vector 实例

#include<iostream>
#include<vector>
using namespace std;
 
void main()
{
	vector<int> a;
	a.reserve(10);
	cout << "a的容量:"<< a.capacity() << " ;a的大小:"<< a.size() << endl;
	/*
	for (int i = 0; i < 10; i++ ){
     a.push_back(i); //新元素这时才构造
	 }
	*/
 
	vector<int> b;
	b.resize(10);
	cout << "b的容量:"<< b.capacity() << " ;b的大小:" << b.size() << endl;
	cout << "b[7]=" <<b[7] << endl;
	vector<int> b1;
	b1.resize(10,7);
	cout << "b1的容量:"<< b1.capacity() << " ;b1的大小:" << b1.size() << endl;
	cout << "b1[7]=" <<b1[7] << endl;
 
	vector<int> c;
	cout << "c的容量:"<< c.capacity() << " ;c的大小:" << c.size() << endl;
	vector<int> d(10);
	cout << "d的容量:"<< d.capacity() << " ;d的大小:" << d.size() << endl;
	cout << "d[7]="<< d[7] << endl;
	vector<int> d1(10,7);
	cout << "d1的容量:"<< d1.capacity() << " ;d1的大小:" << d1.size() << endl;
	cout << "d1[7]="<< d1[7] << endl;
}

a的容量:10 ;a的大小:0
b的容量:10 ;b的大小:10
b[7]=0
b1的容量:10 ;b1的大小:10
b1[7]=7
c的容量:0 ;c的大小:0
d的容量:10 ;d的大小:10
d[7]=0
d1的容量:10 ;d1的大小:10
d1[7]=7

10、vector 中 push_back 的时间复杂度分析

vector 是 STL 中的一种序列式容器，采用的数据结构为线性连续空间，它以两个迭代器 start 和 finish 分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 end_of_storage 指向整块连续空间（含备用空间）的尾端，结构如下所示:

template <class T Alloc = alloc>
class vector
{
   ...

   protected:
       iterator start;             // 表示目前使用空间的头
       iterator finish;            // 表示目前使用空间的尾
       iterator end_of_storage;    // 表示可用空间的尾
   ...
}

该函数首先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器 finish，使 vector 变大。如果没有备用空间了，就扩充空间，重新配置、移动数据，释放原空间。

其中判断是否有备用空间，就是判断 finish 是否与 end_of_storage 相等。如果 finish != end_of_storage，说明还有备用空间，否则已无备用空间。

当执行 push_back 操作，该 vector 需要分配更多空间时，它的容量（capacity）会增大到原来的 m 倍。现在我们用均摊分析方法来计算 push_back 操作的时间复杂度。

假定有 n 个元素，倍增因子为 m。那么完成这 n 个元素往一个 vector 中的 push_back 操作，需要重新分配内存的次数大约为 log_m(n)，第 i 次重新分配将会导致复制 m^i （也就是当前的 vector.size() 大小）个旧空间中元素，因此 n 次 push_back 操作所花费的总时间约为 n*m/(m - 1)。

很明显这是一个等比数列。那么 n 个元素，n 次操作，每一次操作需要花费时间为 m / (m - 1)，这是一个常量。

所以，我们采用均摊分析的方法可知，vector 中 push_back 操作的时间复杂度为常量时间。

在 STL 中，vector 的每次扩容都是 2 倍，也就是 m=2。这样，n 次总的时间约为 n*2/(2-1) = 2n；那么每一操作要花的时间就是 2，因此是常量级。

list

1、list 的底层是一个双向链表，以结点为单位存放数据，结点的地址在内存中不一定连续，每次插入或删除一个元素，就配置或释放一个元素空间。

2、list 不支持随机存取，如果需要大量的插入和删除，而不关心随机存取，建议使用 list。

1、list 常用函数

list.push_back(elem);	// 在尾部加入一个数据
list.pop_back();        // 删除尾部数据
list.push_front(elem);	// 在头部插入一个数据
list.pop_front();       // 删除头部数据
list.size();	        // 返回容器中实际数据的个数
list.sort();            // 排序，默认由小到大 
list.unique();          // 移除数值相同的连续元素
list.back();            // 取尾部迭代器
list.erase(iterator);   // 删除一个元素，参数是迭代器，返回的是删除迭代器的下一个位置

deque

1、deque 的底层原理

deque 是一个双向开口的连续线性空间（双端队列），在头尾两端进行元素的插入跟删除操作都有理想的时间复杂度。

2、什么情况下用 vector，什么情况下用 list，什么情况下用 deque？

vector 可以随机存储元素（即可以通过公式直接计算出元素地址，而不需要挨个查找），但在非尾部插入删除数据时，效率很低，适合对象简单，对象数量变化不大，随机访问频繁。除非必要，我们尽可能选择使用 vector 而非 deque，因为 deque 的迭代器比 vector 迭代器复杂很多。

list 不支持随机存储，适用于对象大，对象数量变化频繁，插入和删除频繁，比如写多读少的场景。

需要从首尾两端进行插入或删除操作的时候需要选择 deque。

3、deque 常用函数

deque.push_back(elem);	// 在尾部加入一个数据。
deque.pop_back();       // 删除尾部数据。
deque.push_front(elem);	// 在头部插入一个数据。
deque.pop_front();      // 删除头部数据。
deque.size();	        // 返回容器中实际数据的个数。
deque.at(idx);	        // 传回索引idx所指的数据，如果idx越界，抛出out_of_range。

priority_queue 优先级队列

1、priority_queue 的底层原理

其底层是用堆来实现的。在优先队列中，队首元素一定是当前队列中优先级最高的那一个。

2、priority_queue 的常用函数

priority_queue<int, vector<int>, greater<int>> pq;   // 最小堆
priority_queue<int, vector<int>, less<int>> pq;      // 最大堆
pq.empty();   // 如果队列为空返回真
pq.pop();     // 删除对顶元素
pq.push(val); // 加入一个元素
pq.size();    // 返回优先队列中拥有的元素个数
pq.top();     // 返回优先级最高的元素

map、set、multiset、multimap

1、map 、set、multiset、multimap 的底层原理

map、set、multiset、multimap 的底层实现都是红黑树。

对于 STL 里的 map 容器，count 方法与 find 方法，都可以用来判断一个 key 是否出现，mp.count(key) > 0 统计的是 key 出现的次数，因此只能为 0/1，而 mp.find(key) != mp.end() 则表示 key 存在。

2、map 、set、multiset、multimap 的特点

set 和 multiset 会根据特定的排序准则自动将元素排序，set 中元素不允许重复，multiset 可以重复。

map 和multimap 将 key 和 value 组成的 pair 作为元素，根据 key 的排序准则自动将元素排序（因为红黑树也是二叉搜索树，所以 map 默认是按 key 排序的），map 中元素的 key 不允许重复，multimap 可以重复。

map 和 set 的增删改查速度为都是 O(logn)，是比较高效的。

3、为何 map 和 set 的插入删除效率比其他序列容器高，而且每次 insert 之后，以前保存的 iterator 不会失效？

因为存储的是结点，不需要内存拷贝和内存移动。

因为插入操作只是结点指针交换，结点内存没有改变。而 iterator 就像指向结点的指针，内存没变，指向内存的指针也不会变。

4、为何 map 和 set 不能像 vector 一样有个 reserve 函数来预分配数据？

因为在 map 和 set 内部存储的已经不是元素本身了，而是包含元素的结点。也就是说 map 内部使用的 Alloc 并不是 map<Key, Data, Compare, Alloc> 声明的时候从参数中传入的 Alloc。

5、map、set、multiset、multimap 的常用函数

it map.begin(); 　        // 返回指向容器起始位置的迭代器（iterator） 
it map.end();             // 返回指向容器末尾位置的迭代器 
bool map.empty();         // 若容器为空，则返回true，否则false
it map.find(k);           // 寻找键值为k的元素，并用返回其地址
int map.size();           // 返回map中已存在元素的数量
map.insert({int,string}); // 插入元素

// 遍历删除
for (it = map.begin(); it != map.end(); )
{
    if (it->second == "target")
        map.erase(it++) ; // erase之后，令当前迭代器指向其后继。
    else
        ++it;
}

unordered_map、unordered_set

1、unordered_map、unordered_set 的底层原理

unordered_map 的底层是一个防冗余的哈希表（采用除留余数法）。哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，时间复杂度为 O(1)；而代价仅仅是消耗比较多的内存。

使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数（一般使用除留取余法），也叫做散列函数），使得每个元素的 key 都与一个函数值（即数组下标，hash 值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照 key 为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。

但是，不能够保证每个元素的 key 与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。一般可采用拉链法解决冲突：

2、哈希表的实现

#include <iostream>
#include <vector>
#include <list>
#include <random>
#include <ctime>
using namespace std;

const int hashsize = 12;

//定一个节点的结构体
template<typename T, typename U>
struct HashNode 
{
    T _key;		//键
    U _value;	//值
};

//使用拉链法实现哈希表类
template <typename T, typename U>
class HashTable
{
public:
    HashTable() : vec(hashsize) {}//类中的容器需要通过构造函数来指定大小
    ~HashTable() {}
    bool insert_data(const T &key, const U &value);
    int hash(const T &key);
    bool hash_find(const T &key);
private:
    vector<list<HashNode<T, U>>> vec;//将节点存储到容器中
};

//哈希函数（除留取余）
template <typename T, typename U>
int HashTable<T, U>::hash(const T &key)
{
    return key % 13;
}

//哈希查找
template <typename T, typename U>
bool HashTable<T, U>::hash_find(const T &key)
{
    int index = hash(key);//计算哈希值
    for (auto it = vec[index].begin(); it != vec[index].end(); ++it)
    {
        if (key == it -> _key)//如果找到则打印其关联值
        {
            cout << it->_value << endl;//输出数据前应该确认是否包含相应类型
            return true;
        }
    }
    return false;
}

//插入数据
template <typename T, typename U>
bool HashTable<T, U>::insert_data(const T &key, const U &value)
{
    //初始化数据
    HashNode<T, U> node;
    node._key = key;
    node._value = value;
    for (int i = 0; i < hashsize; ++i)
    {
        if (i == hash(key))//如果溢出则把相应的键值添加进链表
        {
            vec[i].push_back(node);
            return true;
        }
    }
}

int main(int argc, char const *argv[])
{
    HashTable<int, int> ht;
    static default_random_engine e;
    static uniform_int_distribution<unsigned> u(0, 100);
    long long int a = 10000000;
    for (long long int i = 0; i < a; ++i)
        ht.insert_data(i, u(e));
    clock_t start_time = clock();
    ht.hash_find(114);
    clock_t end_time = clock();
    cout << "Running time is: " << static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC * 1000 <<
        "ms" << endl;//输出运行时间。
    system("pause");
    system("pause");
    return 0;
}

3、unordered_map 与 map 的区别与使用场景

构造函数
unordered_map 需要 hash 函数、等于函数；map 只需要比较函数（小于函数）。
存储结构
unordered_map 采用 hash 表存储，map 一般采用红黑树（RB Tree）实现。因此它们的 memory 数据结构是不一样的。

总体来说，unordered_map 查找速度会比 map 快，而且查找速度基本和数据数据量大小相关，属于常数级别；而 map 的查找速度是 O(log(n)) 级别，并不一定常数就比 O(log(n)) 小。hash 还有 hash 函数的耗时，如果你考虑效率，特别是在元素达到一定数量级时，考虑 unordered_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，unordered_map 可能会让你陷入尴尬，特别是当你的 unordered_map 对象特别多时，你就更无法控制了，而且 unordered_map 的构造速度较慢。

4、unordered_map、unordered_set 的常用函数

unordered_map.begin();			// 返回指向容器起始位置的迭代器（iterator） 
unordered_map.end();			// 返回指向容器末尾位置的迭代器 
unordered_map.cbegin();			// 返回指向容器起始位置的常迭代器（const_iterator） 
unordered_map.cend();			// 返回指向容器末尾位置的常迭代器 
unordered_map.size();			// 返回有效元素个数 
unordered_map.insert(key);		// 插入元素 
unordered_map.find(key);		// 查找元素，返回迭代器
unordered_map.count(key);		// 返回匹配给定主键的元素的个数

四、STL 迭代器的底层机制和失效的问题

迭代器的底层原理

迭代器是连接容器和算法的一种重要桥梁，通过迭代器可以在不了解容器内部原理的情况下遍历容器。它的底层实现包含两个重要的部分：萃取技术和模板偏特化。

萃取技术（traits）可以进行类型推导，根据不同类型可以执行不同的处理流程，比如容器是 vector，那么 traits 必须推导出其迭代器类型为随机访问迭代器，而 list 则为双向迭代器。

例如 STL 算法库中的 distance 函数，distance 函数接受两个迭代器参数，然后计算他们两者之间的距离。显然对于不同的迭代器计算效率差别很大。比如对于 vector 容器来说，由于内存是连续分配的，因此指针直接相减即可获得两者的距离；而 list 容器是链式表，内存一般都不是连续分配，因此只能通过一级一级调用 next() 或其他函数，每调用一次再判断迭代器是否相等来计算距离。vector 迭代器计算 distance 的效率为 O(1)，而 list 则为 O(n)，n 为距离的大小。

使用萃取技术（traits）进行类型推导的过程中会使用到模板偏特化。模板偏特化可以用来推导参数，如果我们自定义了多个类型，除非我们把这些自定义类型的特化版本写出来，否则我们只能判断他们是内置类型，并不能判断他们具体属于是个类型。

template <typename T>
struct TraitsHelper {
     static const bool isPointer = false;
};

template <typename T>
struct TraitsHelper<T*> {
     static const bool isPointer = true;
};

if (TraitsHelper<T>::isPointer)
     ...... // 可以得出当前类型int*为指针类型
else
     ...... // 可以得出当前类型int非指针类型

一个理解 traits 的例子

// 需要在T为int类型时，Compute方法的参数为int，返回类型也为int，
// 当T为float时，Compute方法的参数为float，返回类型为int
template <typename T>
class Test {
public:
     TraitsHelper<T>::ret_type Compute(TraitsHelper<T>::par_type d);
private:
     T mData;
};

template <typename T>
struct TraitsHelper {
     typedef T ret_type;
     typedef T par_type;
};

// 模板偏特化，处理int类型
template <>
struct TraitsHelper<int> {
     typedef int ret_type;
     typedef int par_type;
};

// 模板偏特化，处理float类型
template <>
struct TraitsHelper<float> {
     typedef float ret_type;
     typedef int par_type;
};

当函数，类或者一些封装的通用算法中的某些部分会因为数据类型不同而导致处理或逻辑不同时，traits 会是一种很好的解决方案。

迭代器的种类

输入迭代器：是只读迭代器，在每个被遍历的位置上只能读取一次。例如上面 find 函数参数就是输入迭代器。
输出迭代器：是只写迭代器，在每个被遍历的位置上只能被写一次。
前向迭代器：兼具输入和输出迭代器的能力，但是它可以对同一个位置重复进行读和写。但它不支持 operator–，所以只能向前移动。
双向迭代器：很像前向迭代器，只是它向后移动和向前移动同样容易。
随机访问迭代器：有双向迭代器的所有功能。而且，它还提供了“迭代器算术”，即在一步内可以向前或向后跳跃任意位置，包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种 Iterator 的所有操作，并另外支持 it + n、it - n、it += n、 it -= n、it1 - it2 和 it[n] 等操作。

迭代器失效的问题

插入操作

对于 vector 和 string，如果容器内存被重新分配，iterators、pointers、references 失效；如果没有重新分配，那么插入点之前的iterator 有效，插入点之后的 iterator 失效；
对于 deque，如果插入点位于除 front 和 back 的其它位置，iterators、pointers、references 失效；当我们插入元素到 front 和 back 时，deque 的迭代器失效，但 reference 和 pointers 有效；
对于 list 和 forward_list，所有的 iterator、pointer 和 refercnce 有效。

删除操作

对于 vector 和 string，删除点之前的 iterators、pointers、references 有效；off-the-end 迭代器总是失效的；
对于 deque，如果删除点位于除 front 和 back 的其它位置，iterators、pointers、references 失效；当我们插入元素到 front 和 back 时，off-the-end 失效，其他的 iterators、pointers、references 有效；
对于 list 和 forward_list，所有的 iterator、pointer 和 refercnce 有效。
对于关联容器 map 来说，如果某一个元素已经被删除，那么其对应的迭代器就失效了，不应该再被使用，否则会导致程序无定义的行为。

五、STL 容器的线程安全性

5.1、线程安全的情况

多个读取者是安全的。多线程可能同时读取一个容器的内容，这将正确地执行。当然，在读取时不能有任何写入者操作这个容器；
对不同容器的多个写入者是安全的。多线程可以同时写不同的容器。

5.2、线程不安全的情况

在对同一个容器进行多线程的读写、写操作时；
在每次调用容器的成员函数期间都要锁定该容器；
在每个容器返回的迭代器（例如通过调用 begin 或 end）的生存期之内都要锁定该容器；
在每个在容器上调用的算法执行期间锁定该容器。

参考原文:
STL详解

本文标题：C++STL知识点简析
本文作者：beyondhxl
本文链接：https://www.beyondhxl.com/post/2835216b.html
版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！