«STL源码剖析»这本书读书时候看过一遍，但是时隔三四年实在是有点忘了，加上最近刷LeetCode的时候，发现其实很多都能用上，所以想着再重新梳理一遍。候杰的书太老了，但是老不代表不经典，依然可以指导我们学习。但是因为知道这本书是比较老的书，所以源码剖析就要真的看现代的源码，来让我们对书中可能的错误甄别出来。我是用的STL来自版本为14.28.29333的MSVC编译器，使用vim加上universal-ctags配合查找源代码。

allocator

空间分配器主要实现了allocate、deallocate、construct、destroy四个主要函数，两个对未分配内存控制的函数uninitialize_fill和uninitialize_copy，除此之外还有一些类型别名的定义，用于萃取器的。

template <class _Alloc>
struct allocator_traits : conditional_t<_Is_default_allocator<_Alloc>::value, _Default_allocator_traits<_Alloc>,
                              _Normal_allocator_traits<_Alloc>> {};

通过allocator_traits可以选择不同的萃取器。

Type Traits

STL中的Type Traits非常有用，比如std::copy中利用std::is_trivially_constructible来区分是否用了默认构造函数，从而实现tag dispatching

iterator

迭代器本质上就是包装了指针，实现了递增、递减、解引用、[]等操作，同时还按照规范定义了比如value_type等的类型别名，才能够被iterator_traits使用。很重要的类型别名是iterator_category_tag，实现了tag dispatching才能实现算法的泛型。

input iterator
output iterator
forward iterator
bidirectional iterator
random access iterator

这五种迭代器都有iterator_catogory支持tag dispatching,很多迭代器帮助函数就是通过tag dispathing实现的，比如

advance
next/prev
distance
iter_swap

这其中的所有迭代器帮助函数并不都是常数复杂度的，不同迭代器计算的复杂度不同，需要留意。

template <class _Alvbase_wrapped>
class _Vb_iterator: public _Vb_const_iterator<_Alvbase_wrapped>
{
public:
  using _Mybase = _Vb_const_iterator<_Alvbase_wrapped>;
  ...
  using iterator_category = random_access_iterator_tag;
  ...

  _NODISCARD reference operator *() const noexcept{…}
  _Vb_iterator& operator ++() const noexcept{…}
  _Vb_iterator& operator --() const noexcept{…}
  …
}

上述代码是std::vector的迭代器实现方法，因为其iterator_category是随机存取迭代器标签类即random_access_iterator_tag，所以需要实现几乎所有的操作。

迭代器的实现是在容器里的，或者说和容器配套的；但是有个iterator_base基类，

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : input_iterator_tag {};
struct bidirectional_iterator_tag : forward_iterator_tag {};
struct random_access_iterator_tag : bidirectional_iterator_tag {};

以上来自微软STL的xutility文件，可以看到tag本质就是类类型；

有一些迭代器在STL中已经定义好了。输入迭代器有istream_iterator和istreambuf_iterator，输出迭代器有ostream_iterator和ostreambuf_iterator。

如果要自定义迭代器，那么要符合iterator_traits的要求

template <class _Iter>
struct _Iterator_traits_base<_Iter,
  void_t<
    typename _Iter::iterator_category,
    typename _Iter::value_type,
    typename _Iter::difference_type,
    tyepname _Iter::pointer,
    typename _Iter::reference
  >>
  {
    using iterator_category = typename _Iter::iterator_category;
    using value_type = typename _Iter::value_type;
    using difference_type = typename _Iter::difference_type;
    using pointer = typename _Iter::pointer;
    using reference = typename _Iter::reference;
  };

也就是要满足以上五个关联类型，然后还要满足特定迭代器类型对应的运算符操作。

除此之外最重要的两个类型是std::true_type和std::false_type，这两个继承自std::integral_constant类模板。

_STD_BEGIN
// STRUCT TEMPLATE integral_constant
template <class _Ty, _Ty _Val>
struct integral_constant {
    static constexpr _Ty value = _Val;

    using value_type = _Ty;
    using type       = integral_constant;

    constexpr operator value_type() const noexcept {
        return value;
    }

    _NODISCARD constexpr value_type operator()() const noexcept {
        return value;
    }
};

容器

vector

增删困难，查改方便，迭代器可以用指针替代。但是比较特别的是vector<bool>并不是容器，因为该类型是按照比特位来存储bool值的，但是指针操作最小也是指向字节，因此没有办法通过指针操作进行赋值和解引用，

using _Vbase = unsigned int; // word type for vector<bool> representation

template<class _Alloc>
struct allocator_traits: conditional_t<_Is_default_allocator<_Alloc>::value, _Default_allocator_traits<_Alloc>, _Normal_allocator_traits<_Alloc>> {};

template<class _Alloc, cllass _Value_type>
using _Rebind_alloct_t = tpyename allocator_traits<_Alloc>::template rebind_alloc<_Value_type>;

尽可能不要使用vector<bool>，或者使用deque<bool>替代。

list

增删方便，查改困难，只需要一个迭代器可满足需求，且双向链表的首位相连，意思是最后一个元素的next指针指向了第一个元素。

deque

通过指针数组实现的，每个指针又指向了类型T对应的数组。

std::stack和std::queue都是std::deque的适配器。

常见算法

数值算法

有些算法如果更改函数对象，可以有不同的效果。比如accumulate并不一定就是范围内所有元素相加，也可以是相乘或者相减。

accumulate
adjacent_difference
partial_sum
inner_product
min,max,equal,mismatch
fill,fill_n
swap,iter_swap
lexicographical_compare
copy,copy_backward

copy函数是非常典型的利用泛化和特化的算法。针对于内置类型，通过std::is_trivially_copyable来对拷贝执行memcopy操作；针对非trivial类型再判断是否指针，还是特定迭代器，利用tag dispatching区分指针再进行更细致的操作。比如vector的迭代器其实就是T*并不是继承自std::iterator，所以会调用特化的copy版本。

count,count_if
find,find_if,find_end,find_first_of
adjacent_find
generate,generate_n
remove,remove_copy,remove_if,remove_copy_if
replace,replace_copy,replace_if,replace_copy_if
rotate,rotate_copy
reverse,reverse_copy
unique,unique_copy
search,search_n
transform
merge,inplace_merge
partition

还有一些特定用途的算法

binary_search,lower_bound,upper_bound,equal_range用于二叉查找
next_permutation,prev_permutation用于排列组合
random_shuffle随机重排
nth_element 保证[first,nth)和[nth,last)两者被nth分割为小于nth的序列和大于nth的序列，但是序列各自都是没有排序的。

set算法

都是以set开头命名的

set_union
set_intersection
set_difference
set_symmetric_difference

函数对象

指针能够实现的功能有限，且不能够很好的和容器和算法进行配合操作。函数对象可以分为三种：

算术运算
关系运算
逻辑运算

只支持一元操作和二元操作，更多元就不支持了。本质原因是所有的函数对象都是继承自unary_function和binary_function的。和迭代器类似，为了支持萃取器和类型计算，需要标准化定义一些关联类型。

// STRUCT TEMPLATE unary_function
template <class _Arg, class _Result>
struct unary_function { // base class for unary functions
     using argument_type = _Arg;
     using result_type   = _Result;
 };

以上定义来自微软Windwos文件中的xstddef头文件中，定义了一元操作符的关联类型。

// STRUCT TEMPLATE binary_function
template <class _Arg1, class _Arg2, class _Result>
struct binary_function { // base class for binary functions
    using first_argument_type  = _Arg1;
    using second_argument_type = _Arg2;
    using result_type          = _Result;
};

以上定义来自微软Windwos文件中的xstddef头文件中，定义了二元操作符的关联类型。我们还可以将二元操作符通过配接器转换为一元操作符，通过binder1st来实现，如下代码来自微软functional头文件：

 // CLASS TEMPLATE binder1st
template <class _Fn>
class binder1st : public unary_function<typename _Fn::second_argument_type,
                        typename _Fn::result_type> { // functor adapter _Func(stored, right)
public:
    using _Base         = unary_function<typename _Fn::second_argument_type, typename _Fn::result_type>;
    using argument_type = typename _Base::argument_type;
    using result_type   = typename _Base::result_type;
    binder1st(const _Fn& _Func, const typename _Fn::first_argument_type& _Left) : op(_Func), value(_Left) {}

    result_type operator()(const argument_type& _Right) const {
      return op(value, _Right);
   }

     result_type operator()(argument_type& _Right) const {
        return op(value, _Right);
    }

protected:
    _Fn op;
    typename _Fn::first_argument_type value; // the left operand
};

算术运算函数对象

除了否定运算为一元运算，其他都是二元运算。

plus
minus
multiplies
divides
modules
negate

关系运算函数对象

全部都是二元运算符。

equal_to
not_equal_to
greater
greater_equal
less
less_equal

逻辑运算函数对象

logical_and
logical_or
logical_not

适配器

分为三种，容器适配器，迭代器适配器，函数对象适配器。

容器适配器

两者都是deque的适配器。

queue
stack

迭代器适配器

总共有六种迭代器的适配器。

insert_iterator，back_insert_iterator,front_insert_iterator是output_iterator的适配器
reverse_iterator,有唯一的保护成员时_BidIt current{}，模板参数是迭代器_BidIt
istream_iterator,ostream_iterator,相比与普通的迭代器，增加了一个istream_type*成员，所以有流的功能。
sregex_iterator,sregex_token_iterator，正则表达式匹配时在多个匹配对象之间选择
move_iterator
raw_storage_iterator

适配器有些需要从迭代器计算得到，典型的比如move_iterator移动迭代器mp=make_move_iterator(ip)，其中ip是input_iterator输入迭代器

istream_iterator的构造函数中就会执行>>读入操作。ostream_iterator和std::copy联合起来用很有意思,ostream_iterator的赋值运算符会调用<<操作符，其他运算符都是返回当前指向位置，所以和std::copy能够产生效果。

函数对象适配器

标准库中的函数对象是有要求的，必须用适配器去处理普通的函数对象。函数对象适配器的目的是让各种运算符、成员函数、函数指针都能够适配标准库的用法。

运算符都要继承自unary_function和binary_function
成员函数都要通过函数模板mem_fun的处理，有趣的是如果是成员函数是虚函数，还能够实现多态；但要求容器元素类型是指针，因为引用元素的容器是不能存在的，无法分配内存
函数指针都要通过函数模板ptr_fun的处理

其中Windows的STL的函数模板mem_fun如下所示：

// FUNCTION TEMPLATE mem_fun
template <class _Result, class _Ty>
_NODISCARD mem_fun_t<_Result, _Ty> mem_fun(_Result (_Ty::*_Pm)()) {
    return mem_fun_t<_Result, _Ty>(_Pm);
}

template <class _Result, class _Ty, class _Arg>
_NODISCARD mem_fun1_t<_Result, _Ty, _Arg> mem_fun(_Result (_Ty::*_Pm)(_Arg)) {
   return mem_fun1_t<_Result, _Ty, _Arg>(_Pm);
}

template <class _Result, class _Ty>
_NODISCARD const_mem_fun_t<_Result, _Ty> mem_fun(_Result (_Ty::*_Pm)() const) {
    return const_mem_fun_t<_Result, _Ty>(_Pm);
}

template <class _Result, class _Ty, class _Arg>
_NODISCARD const_mem_fun1_t<_Result, _Ty, _Arg> mem_fun(_Result (_Ty::*_Pm)(_Arg) const) {
    return const_mem_fun1_t<_Result, _Ty, _Arg>(_Pm);
}

这里返回的类型如mem_fun_t等其实都是继承自unary_function的类型。而mem_fun1_t是继承自binary_function的类型，因为该成员函数有一个参数_Arg。

其中Windows的STL的宏ptr_fun如下所示：

// FUNCTION TEMPLATE ptr_fun
#define _PTR_FUN(CALL_OPT, X1, X2, X3)                                                                      \
    template <class _Arg, class _Result>                                                                    \
    _NODISCARD pointer_to_unary_function<_Arg, _Result, _Result(CALL_OPT*)(_Arg)> ptr_fun(                  \
        _Result(CALL_OPT* _Left)(_Arg)) {                                                                   \
        return pointer_to_unary_function<_Arg, _Result, _Result(CALL_OPT*)(_Arg)>(_Left);                   \
    }                                                                                                       \
    template <class _Arg1, class _Arg2, class _Result>                                                      \
    _NODISCARD pointer_to_binary_function<_Arg1, _Arg2, _Result, _Result(CALL_OPT*)(_Arg1, _Arg2)> ptr_fun( \
        _Result(CALL_OPT* _Left)(_Arg1, _Arg2)) {                                                           \
        return pointer_to_binary_function<_Arg1, _Arg2, _Result, _Result(CALL_OPT*)(_Arg1, _Arg2)>(_Left);  \
     }
_NON_MEMBER_CALL(_PTR_FUN, X1, X2, X3)
#undef _PTR_FUN

而对于函数指针，则有两个辅助类型，pointer_to_unary_function和pointer_to_binary_function，这两个类其实都是继承自unary_function和binary_function的。