C++ STL

本文是阅读《STL 源码刨析》 和 《泛型编程与 STL》的笔记

graph TB
	A[new]
	B[new op]
	C[op new]
	D[placement new]
	E[manual dtor]
	F[Banlance Tree]
	G[AVL Tree]
	H[4 roates]
	I[2-3 Tree]
	J[RB Tree]
	K[Algs]
	L[sort]
	M[quick/insert/heap]
	N[adaptor]
	O[b/i/f]
	P[io itr]
	
	A-->B
	A-->C
	A-->D
	B-->C
	D-->E
	F-->G
	G-->H
	F-->I
	I-->J
	K-->L
	L-->M
	N-->O
	N-->P

GCC 中使用的 STL 实现一般都源自 SGI

Concept

Concept 是描述类型的一组条件，如果某个类型满足所有条件则说类是此 concept 的一个模型（model）

比如，如果想使用 stl 中的 find 算法，find 的参数需要支持提领（*ptr）和迭代器自增（itr++）这样的特性，对于 find 的参数而言，这就是 concept，其他简单 concept 可以是：copyable/assignable/equal cmp able 等

Concept 与继承

vector 迭代器支持随机访问，而 list 的迭代器不支持链表的随机访问，单向列表的迭代器甚至不支持后退操作（itr--）

从分析可知 vecotr 迭代器的 concept 条件比 list 的迭代器多，而 list 又比单向链表多，因此 concept 有包含和被包含的关系。可以使用继承关系描述 concept 这种包含与被包含

C++20 之后

C++ 20 之前 concept 只是概念，C++ 20 之后可以用代码定义 concept

C++ 20 引入了 concept 相关的语法和组件，具体可以参考：Constraints and concepts 。官方对 concept 的定义：

Named sets of requirements are called concepts. Each concept is a predicate, evaluated at compile time, and becomes a part of the interface of a template where it is used as a constraint

Concept 示例 1

#include <string>
#include <cstddef>
#include <concepts>

template<typename T>
concept Hashable = requires(T a) {
    { std::hash<T>{}(a) } -> std::convertible_to<std::size_t>;
};
struct meow {};
template<Hashable T> void f(T) {}
 
int main() {
  using std::operator""s;
  f("abc"s);   // OK, std::string satisfies Hashable
  //f(meow{}); // Error: meow does not satisfy Hashable
}

Concept 示例 2

template <class T> concept Integral = std::is_integral<T>::value;
template <class T> concept SignedIntegral = Integral<T> && std::is_signed<T>::value;
template <class T> concept UnsignedIntegral = Integral<T> && !SignedIntegral<T>;

allocator

allocator 的存在与 STL 的设计有关，随着 C++ 标准的进步，alloc 也在不断的发展，alloc 的特性如下：

1. 特殊场景下自定义 alloc 可以提高性能，比如使用特殊算法减少内存碎片
   1. Intel cpu 提供了6种内存模式，使用 alloc 可以适配这几种模式，参考
   2. 在嵌入式领域很多设备在启动后会持续运行很久（数月或者数年）。因为资源有限，内存碎片是不能容忍的，所以嵌入式领域常使用定制化的 allocator，使用内存池相关的概念以减少内存碎片，比如 boost pool 等工具
   3. 常规领域比如 IT/互联网 行业，服务重启的比较频繁且当前大部分服务都运行在 64bits CPU 上（进程虚拟内存空间非常大），内存碎片化的影响并不明显
   4. 当代 linux 下的 c/c++ 程序一般直接调用系统提供的 malloc 工具。linux 底层使用 ptmalloc 提供内存分配，ptmalloc 在进程空间使用与 SGI alloc 类似的方式管理内存，内存碎片的问题已经大大改善，参考。所以 C++ 标准库中实现的内存分配器默认直接使用了 ptmalloc
2. 某些场景下可以使用非内存空间保存数据，此时可以通过修改 alloc 实现相应功能

C++11 以后标准库中的 alloc 慢慢弃用了一些特性，比如 rebind 函数等

allocator 接口

为了实现内存的分配与管理，allocator 有一个确定的接口，比如：allocator/deallocator、constructor/destroy，其中constructor 与 placement new 功能类似，destroy 调用对象的析构函数；allocator/deallocator 和 malloc/free 功能类似

1. destroy

   并不是所有对象都有析构函数(trivial dtor)，有些对象可以不用调用析构方法，直接 free 存储即可。destroy 接口通过 traits 技巧为不同属性的对象选择不同类型的析构方法

内存碎片与分配开销

分配开销不可避免但可减少，比如分配较大的内存空间然后划分为小块进行管理；内存碎片也不可避免但可以通过一定的手段来减少，比如复用。SGI 的 alloc 通过层次化内存分配减少了这两类问题

SGI 的 alloc 内存分配器以 8 字节为最小划分单位，支持 16 种（8Bytes～128Bytes）内存大小，新申请的内存将自动对齐到 8 字节，大于 128 字节的内存申请一般使用系统级函数，比如 malloc。alloc 同时支持一次申请多个大小固定的内存空间，此时使用的可能依旧是 alloc 而不是 malloc

New OP / OP New / Placement New

参考：https://blog.csdn.net/linuxheik/article/details/80449059 ，New 大概有三种类型：

1. New OP 指的是 new 关键字，不可重载

2. OP New 指的是 new 操作符，和 operator+(...) 等运算符功能类似，是可以重载的。编译器默认为需要的对象生成三个 OP New

3. Placement New 也是操作符，不过不允许重载

执行 New OP 分为三步（New OP 转化为 OP New 的调用）：

1. 调用类的 OP New 操作符分配内存，编译器默认给每个需要的类生成一个默认的 OP New
2. 调用构造函数，此时也调用了 Placement New 类似的功能，因为直接在已有内存中构造
3. 返回对象指针

具体使用如下代码片段：

#include <iostream>

class B {
 public:
  void set(int n) { _num = n; }
  int  get()      { return _num; }
 private:
  int _num{0};
};

int main() {
  // 直接将对象构造在栈空间中，减少了内存分配的损耗
  char mem[10 * sizeof(B)] = {0};
  B* pb_1 = new (mem) B;
  B* pb_2 = new (mem + sizeof(B)) B;

  pb_1->set(1); pb_2->set(2);
  std::cout << pb_1->get() << std::endl; // 1
  std::cout << pb_2->get() << std::endl; // 2

  // 使用 placement new 需要自己调用析构函数
  pb_1->~B(); pb_2->~B();
}

set_new_handler

C++ 提供了内存分配失败的个性化处理机制，主要是通过调用标准库提供的 set_new_handler 函数实现

SGI alloc

分为两层（如果申请的内存大于128则直接调用第一层系统函数），维护有内存池

alloc 以链表的形式内部使用指针链接所有可用的空白块。因为是链表所以新增空白块十分方便

因为默认最小块是 8 字节，所以内存对齐的问题在分配的同时已经解决

这里需要注意与 《Modern CPP design》中内存分配器实现的区别，二者有相似的地方，但区别还是挺大的

POD 类型对 copy 性能的影响

STL

STL 六大组件

graph TB
	A[容器]
	B[算法]
	C[迭代器]
	D[适配器/stack]
	E[内存分配器]
	F[防函数]

容器

注意：下图中部分非标准容器已经成为标准

C++11 之后引入了可变模版参数，简化了 STL 的很多操作，也为 STL 带来了很多新特性，比如：

1. vector::emplace_back，支持就地初始化，减少了构造次数，参考 。其他容器也有此类接口
2. list 是双向链表（但不保证是环状的），为节省内存在C++11之后可以使用单向链表 forward_list

序列化容器

vector

成员函数示例：

  void pop_back() {
    --_M_finish;         // 尾端标记前移，指针
    destroy(_M_finish);  // 全局函数
  }

  iterator erase(iterator __first, iterator __last) {
    iterator __i = copy(__last, _M_finish, __first);
    destroy(__i, _M_finish);
    _M_finish = _M_finish - (__last - __first);
    return __first;
  }
  void clear() { erase(begin(), end()); }

vector insert 的流程

vector 插入方法在不考虑存储空间是否充足的前提下，插入元素的个数会触发不同插入流程

1. 插入元素个数大于插入点后元素个数，使用一次 copy 即可
2. 插入元素个数小于插入点后元素个数，需要使用两次 copy。这是因为 copy 函数操作的空间重叠时可能造成未知的行为。系统级别的 memmove 如果是从左到右移动数据，则会造成数据的相互覆盖。使用两次 copy 避免了相互覆盖的风险

list

list 和 vector 一个非常明显的区别就是前者插入与删除其他元素都不会使已有迭代器失效，但 vector 就不一定

list 比较少用的方法：splice/transfer（非公开）/merge 等

list 未提供随机迭代器所以对 list 对排序不能使用 std::sort ，需要使用 list::sort ，list 内部使用归并法实现排序。按照 SGI STL 中 list 对实现，list 最多支持 \(2^{64}\) 个元素的排序

deque

stack & queue

因为 stack/queue 的底层依赖于其他容器（默认使用 deque），所以 stack/queue 一般称为 container adapter

heap

heap 和 BST 的区别和明显，heap 只需要满足根节点大于子节点即可，没有 BST 对左右子树的大小要求

priority_queue

基于 heap

关联容器

平衡树

平衡树是 STL 中很多关联容器的基础，比如 set/map 等，平衡树有多种，比如 2-3树/AVL/RB

AVL 树

AVL 树的实现可参考 这里

AVL 树是一种近似的平衡树，AVL 只保证根节点的两棵子树高度相差不超过 1，不保证树的高度一定是 \(log(N)\)，但可以保证树的对数深度

平衡树保持平衡的关键是旋转，如下图所示左侧的树不平衡，那直接左旋使用中间节点作为父节点即可，递归的执行此类过程即可保证树的平衡性

AVL 树一共有 4 种不平衡状态（参考），旋转机制如下图所示（L 和 R 分别表示 left 和 right，LL 表示向左子树插入左节点）：

RB 树

STL 中大部分关联容器底层都基于 RB 树，比如 set/map/multimap 等。简化了整个 STL 的复杂度。红黑树可以利用 2-3 树 原理进行解释，RB 树的实现原理和 AVL 树的旋转类似，这里不再详细介绍

平衡树有双向迭代器，迭代过程是对树的中序遍历，所以对整个树进行一次遍历，其时间复杂度是：

\[O(NlogN) \]

以 ptr++ 为例，其迭代器实现代码如下：

  void _M_increment()
  {
    // 有右子树，找右子树的最左节点
    if (_M_node->_M_right != 0) { 
      _M_node = _M_node->_M_right;
      while (_M_node->_M_left != 0)
        _M_node = _M_node->_M_left;
    }
    // 没有右子树，找不是右节点的父节点
    else {
      _Base_ptr __y = _M_node->_M_parent;
      while (_M_node == __y->_M_right) {
        _M_node = __y;
        __y = __y->_M_parent;
      }
      // 根节点无右子树的情况
      if (_M_node->_M_right != __y)
        _M_node = __y;
    }
  }

STL 算法

算法，问题之解法也

sort

默认排序一般用快排，递归过深则用插入排序，再差则直接用堆排序。这样安排有数据/cache局部性原理的考虑

避免快排极端情况下的 \(O(n^2)\) 的时间复杂度，另一种情况是提前使用随机算法打乱所有数据

适配器

各类适配器使用示例

#include <iterator> // for iterator adapters
#include <deque>
#include <algorithm> // for copy()
#include <iostream>

using namespace std;

int main() {
    // 将outite绑定到cout，每次对outite指派一个元素，就后接一个“ ”
    ostream_iterator<int> outite(cout, ",");

    int ia[] = {0, 1, 2, 3, 4, 5};
    deque<int> id(ia, ia + 6);

    // 将所有元素拷贝到outite，即cout
    copy(id.begin(), id.end(), outite);
    cout << endl;

    // 将ia[]的部分元素拷贝到id内，使用front_insert_iterator
    // front_insert_iterator会将assign操作给push_front操作
    // vector不支持push_front操作，所以不以vector做示范对象
    copy(ia + 1, ia + 3, front_inserter(id));
    copy(id.begin(), id.end(), outite);
    cout << endl;

    // 将ia[]的部分元素拷贝到id内，使用back_insert_iterator
    copy(ia + 1, ia + 3, back_inserter(id));
    copy(id.begin(), id.end(), outite);
    cout << endl;

    // 搜寻元素5所在位置
    deque<int>::iterator ite = find(id.begin(), id.end(), 5);
    // 将ia[]的部分元素拷贝到id内，使用insert_iterator
    copy(ia + 1, ia + 3, inserter(id, ite));
    copy(id.begin(), id.end(), outite);
    cout << endl;

    // 将所有元素逆向拷贝到outite
    // rbegin()和rend()与reverse_iterator有关
    copy(id.rbegin(), id.rend(), outite);
    cout << endl;

    // 将inite绑定到cin，将元素拷贝到inite，知道eos出现
    istream_iterator<int> inite(cin), eos; // eos: end-of-stream
    copy(inite, eos, inserter(id, id.begin()));
    // 输入数字，停止时可以输入任意字符
    copy(id.begin(), id.end(), outite);
}

front/insert/back_inserter

以 stl copy 函数为例说明这些 inserter 适配器的作用：

template<class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result) {
  while (first!=last) {
    *result = *first;
    ++result; ++first;
  }
  return result;
}

如果没有适配器，我们需要自行递增 result 。下面以 back_inserter 的实现来说明这几个适配器的实现方法：

template <class _Container>
class back_insert_iterator {
protected:
  _Container* container; // 底层容器
public:
  // 与容器绑定起来
  explicit back_insert_iterator(_Container& __x) : container(&__x) {}
  back_insert_iterator<_Container>& operator=(
  								const typename _Container::value_type& __value) { 
    container->push_back(__value); // back inserter
    // container->push_front(__value) // front inserter
    // iter = container->insert(iter, __value); iter++; // insert inserter
    return *this;
  }
};

// 辅助函数 back_inserter
template <class _Container>
inline back_insert_iterator<_Container> back_inserter(_Container& __x) {
  return back_insert_iterator<_Container>(__x);
}

stream 适配器

以 ostream_iterator/istream_iterator 实现为例说明实现方法：

ostream_iterator

template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> >
class ostream_iterator {
public:
  ostream_iterator(ostream_type& __s) : _M_stream(&__s), _M_string(0) {}
  ostream_iterator(ostream_type& __s, const _CharT* __c) : _M_stream(&__s), _M_string(__c)  {}
  ostream_iterator<_Tp>& operator=(const _Tp& __value) { 
    *_M_stream << __value;
    if (_M_string) *_M_stream << _M_string;
    return *this;
  }
private:
  ostream_type* _M_stream;
  const _CharT* _M_string;
};

istream_iterator

template <class _Tp, class _Dist>
class istream_iterator {
protected:
  istream* _M_stream;
  _Tp _M_value;
  bool _M_end_marker;
  void _M_read() {
    _M_end_marker = (*_M_stream) ? true : false;
    if (_M_end_marker) *_M_stream >> _M_value; // 关键
    // 输入后状态可能改变，再判断一次
    // 读到eof或不符合类别时，stream处于false状态
    _M_end_marker = (*_M_stream) ? true : false;
  }
public:
  istream_iterator() : _M_stream(&cin), _M_end_marker(false) {}
  istream_iterator(istream& __s) : _M_stream(&__s) { _M_read(); }
  // 以上两行用法：
  //  istream_iterator<int> eos;          造成 end_maker 为false
  //  istream_iterator<int> initer(cin);  引发read，等待输入
  reference operator*() const { return _M_value; }
  istream_iterator<_Tp, _Dist>& operator++() { 
    _M_read(); 
    return *this;
  }
  istream_iterator<_Tp, _Dist> operator++(int)  {
    istream_iterator<_Tp, _Dist> __tmp = *this;
    _M_read();
    return __tmp;
  }
};

Utils

STL Algos

ref：https://en.cppreference.com/w/cpp/algorithm

STL Functional

ref：https://en.cppreference.com/w/cpp/utility/functional