C++ STL六大组件

STL包含六大组件：容器、分配器、算法、迭代器、适配器、仿函数。其中适配器有容器适配器、迭代器适配器、仿函数适配器。

比如：count_if(v.begin(), v.end(), not1(bind2nd(less<int>(), 40)))

它的作用是计算容器v里大于40的元素个数。其中v是一个容器，count_if属于算法，begin()和end()属于迭代器，not1和bind2nd属于适配器，less<int>()属于仿函数。

分配器allocator

分配器有allocate和deallocate函数，其中allocate调用::operator new，deallocate调用::operator delete。而这两个函数里默认都是调用malloc和free。当分配的内存比较小的时候，cookie占的比例较大，从而会降低内存利用率。

GNU2.9默认不是allocator而是alloc，十六条链表，链表首尾有cookie，每条链表管理的单元大小按照8的倍数增长，省掉每个元素的两个cookie。但是4.9默认的是allocator，原来的alloc改名为__pool_alloc，也就是__gnu_cxx::__pool_alloc<>

迭代器iterator

iterator是一个类，用了typedef来取别名 ，通过重载操作符来模拟指针

关于++和--的重载：规定无参的是前缀++（返回引用），有个int参数的是后缀++（返回值），对list_iterator就是prev和next。标准规定可++++i而不可i++++。具体实现时，用后缀++调用前缀++即可。

迭代器需要遵守的5个原则

其实就是5个typedef

• iterator_category：表明此迭代器是可以++，还是--，还是可以跳跃。比如bidirectional_iterator_tag可加可减
• value_type：元素类型
• difference_type：相邻迭代器之间的距离，比如ptrdiff_t
• reference和pointer：即T&和T*，暂未使用

原生的指针应该也属于一种迭代器，为了兼容，采用一个萃取机iterator_traits作为中间层，算法将迭代器（可能是原生指针）交给萃取机，萃取机返回迭代器的类型信息，比如iterator_traits<_RandomAccessIterator>::difference_type。为了实现对原生指针的支持，使用了缩小范围的偏特化。

template<typename I>
struct iterator_traits{
    typedef typename I::iterator_category    iterator_category;
    typedef typename T::value_type           value_type;
    typedef typename T::difference_type      difference_type;
    typedef typename T::pointer              pointer;
    typedef typename T::reference            reference;
}

template<typename T>
struct iterator_traits<T*>{	// 针对原生指针类型进行偏特化
    typedef random_access_iterator_iterator_tag iterator_category;
    typedef T               value_type;
    typedef ptrdiff_t       difference_type;
    typedef T*              pointer;
    typedef T&              reference;
}

template<typename T>
struct iterator_traits<const T*>{	// 针对原生常指针类型进行偏特化
    typedef random_access_iterator_iterator_tag iterator_category;
    typedef T               value_type;	// 没有声明为const，因为这个是用来声明临时变量的
    typedef ptrdiff_t       difference_type;
    typedef const T*        pointer;
    typedef const T&        reference;
}

迭代器提供这几个typedef来让算法知道容器的访问方式，从而可以让算法可以选择最合适的方式进行计算。

比如distance函数：对于random_access_iterator_tag，可以直接使用减法计算结果，而对于其他的只能一步一步递增来计算

比如copy函数：对于字符串指针，直接memmove。如果是最慢的input_iterator_tag，只能一个一个复制，循环结束条件是!=last，而random_access_iterator_tag可以直接算出循环次数。如果是其他指针而且拷贝赋值不重要（类型萃取出trivial op=，比如没有指针的类，就不需要调用），直接memmove，否则同random_access_iterator_tag

关于iterator_tag

存在继承链：random_access_iterator_tag -> bidirectional_iterator_tag -> forward_iterator_tag -> input_iterator_tag，而output_iterator_tag为单独一支（可以写但是不能读）。这个继承链实现了一种向上兼容的关系，比如random_access_iterator_tag是派生最远的，支持随机访问，自然也可以进行父类的双向访问。

array、vector和deque都是random_access_iterator_tag，list、rbtree和hashtable都是bidirectional_iterator_tag，forward_list是forward_iterator_tag。

关于type_traits

在旧版里，需要这样写

struct __true_type{};
struct __false_type{};

template<class T>
struct __type_traits{
    typedef __true_type  has_trivial_default_constructor;
    typedef __false_type is_POD_type; // plain old data
}

通过为自定义类型进行特化，从而实现指定的属性。

比如对于destory函数，如果判断出has_trivial_destructor就不用调用析构函数。

但是在新版里不需要自行特化，已经有相关函数可以直接进行判断，可以直接输出is_xxx<T>::value。

比如is_void：内部首先会通过偏特化移除T的const和volatile，之后如果能进入void的特化版本自然就是void类型

比如is_integral：模板是false_type，然后对于各种基本类型都特化为true_type

但是还有很多萃取的底层都看不到源代码，比如__is_enum、__is_union、__is_class和__is_pod，猜想可能是由编译器生成相关信息。

容器container

容器大致分为三种

• 顺序容器：array、vector、deque、list、forward_list
• 关联容器：set、map
• 无序容器：unordered_map/set/multimap/multiset

list

双向环状bidirectional_iterator_tag，为了实现end()，设置一个空节点

vector

typedef value_type* iterator，有start，finish和end_of_storage三个指针

采用两倍扩容，相关函数由于与insert共用，所以在复制时会把新空间也进行复制（如果只是从push_back跟踪进来会看不明白），在搬运元素的过程中会调用大量的复制构造函数和析构函数（除非元素类型对应的函数是trivial的）

deque

表面上连续（是random_access_iterator_tag），实际上是分段连续的，各分段buffer（定长数组）由一个指针数组map（动态数组）进行索引。

deque的迭代器里有cur（指向当前元素）、first和last（指向当前buffer的首尾）、node（map中对应当前buffer的索引）

deque中包含start和finish，分别指向第一个buffer的第一个元素和最后一个buffer的最后，还有map的头指针和map长度

deque如何插入元素

• 如果是后插，直接向map后面添加一个新开辟的buffer。

• 如果是前插，如果map前面有空位置，则直接在前面添加新的buffer，否则需要对map进行扩容，开辟新的空间之后，把原map复制到到新空间的中间部分，然后再插入。

• 如果是插在中部，则需要移动元素，而且元素可以向前移也可以向后移，为了尽量减少元素移动，先计算插入点之前的元素个数，如果小于总个数的一半，则移动前面的元素，否则移动后面的，腾出空间后再插入。

deque如何模拟连续空间

全都依靠迭代器实现

difference_type deque::iterator::operator-(const self& x) const{
    return difference_type(buffer_size()) * (node - x.node - 1)	// 两者间的buffer里的元素个数
        + (cur - first) + (x.last - x.cur);	// 各自所在buffer的元素个数
}

• 重载++和--，判断是否到达边界，是则设置node到下一段或前一段，并重设first、last、cur

• 重载+=和+（后者调前者）：如果cur+off或大于超出边界，计算跨越的buffer数量再移动cur（-=也可以用，off考虑负数）

queue & stack

默认底层容器是deque，通过对deque的成员函数进行封装，改造出需要的接口。这两种容器就属于容器适配器。

除了默认容器，stack底层可以选择list或者vector，而 queue底层只能选择list。如果代码里没有用到pop函数，则底层容器可以使用vector（因为模板特化在用到的时候才会编译生成，vector只是没有pop_front()）。

rbtree

红黑树，属于一种平衡二叉搜索树。迭代本应该不允许进行修改，但是为了方便map修改data，所以并没有禁止。rbtree有两种插入方式：insert_unique不允许重复，insert_equal允许重复，分别对应不带multi前缀和带multi前缀的关联容器。

注意它的模板参数有个value，这个是键和值的组合。KeyOfValue用来从value中取出key，Compare用于比较key，这两个都是仿函数

set & multiset

底层采用rbtree，value就是key，取key用的是identity函数（就是传入什么返回什么），使用const_iterator从而限制了不可修改。也属于容器适配器

map & multimap

typedef pair<const Key, T> value_type从而不允许修改key，可以改data，取key是select1st函数（返回pair->first）

注意使用operator []时默认会在找不到key时创建一个默认的data并插入

hashtable

采用开链法处理冲突（VS里甚至是双向链表），当总元素个数达到篮子容量时进行扩容，新的大小为原大小的倍数附近的质数（可能硬编码提前算好了），并rehashing

hash函数也是仿函数，比如对字符串可以从0开始逐个*5+c，hash()%n

unordered_xxx

底层都是hashtable

tuple

可以存放任意类型任意个数的元素，比如tuple<int,float,string> t(41,6.3,"hah")，也可以auto tt=make_tuple(41,5,2,"hah")

可以用get<N>(t)读写元组t的N号元素，可以直接cout << t。tie(i,f,s)=t把右边元组里的元素逐个赋值给左边的变量，tuple_size<TP>::value取得元素个数，tuple_element<1,TP>::type取得1号元素的类型

算法algorithm

都是模板函数，通过iterator来访问容器里的数据，所有的算法最终都是在比较大小。

关于泛型编程（GP）：OOP是把数据和函数关联在一起，而GP是分开（用全局函数处理数据，通过迭代器）。后者实现把容器和算法分开，特殊的容器就需要自己实现，比如list不能随机访问，只能自己实现sort。使用算法的时候尽量用类实现的，然后考虑全局的（比如set自己的find当然更快）。

• accumulate：从init初值开始逐个进行二元运算（默认加法），返回累计结果

• for_each：对每个元素调用一元运算，可以用范围for代替

• replace：把所有的old_value都替换成new_value；replace_if：满足某条件(predicate)则替换为new_value；replace_copy：等于old_value的都复制到result里

• count：统计value的个数（关联和无序容器自带的更快）；count_if：统计满足条件的个数

• find，find_if：都是顺序查找，关联和无序容器同样更快

• sort：关联容器自然已排序，list和forward_list有自带的sort（因为它们不是random_access）

• binary_search：实际是调用lower_bound（找第一个>=的，而upper_bound是找第一个>的），在二分开始前先比较下首尾元素可以更快

• copy

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

  后面会常常用到这份代码

仿函数functor

重载operator()，为传递给算法使用，具体的操作符也可以由类自行重载实现

分为算术运算（plus、minus）、逻辑运算（logic_and）、相对关系（equal_to、less、greater）

跟迭代器一样，仿函数也有一些typedef。基类unary_function和binary_function已经有argument_type,first_argument_type,second_argument_type,result_type，继承自这个两种类型，也就实现了这些typedef，可以被适配器适配

适配器adapter

并不是单独出现，主要用于修饰，比如iterator、container、functor都有，起到桥梁的作用，使用已有的类的功能（继承或组合），比如修饰functor形成的还是functor

容器适配器

比如stack、queue，调用了内涵的顺序容器（默认deque）的函数

函数适配器

bind2nd

比如bind2nd(less<int>(), 40)绑定仿函数的第二个操作数为40，也即表示小于40。

实现是根据实参推导创建并返回binder2nd类对象（使用op的traits创建ctor实参），在binder2nd类中其中就用到仿函数基类的traits定义成员变量，其ctor里记录创建时的参数值（这里是less<int>对象和40），然后这个类也重载了operator()，所以返回的也是仿函数。适配后的仿函数的返回值为result_type。而且binder2nd类也是继承自binary_function，可以继续被适配。

not1

实参推导构造unary_negate实例并返回，也是仿函数，返回值为!pred（ctor保存的仿函数对象，调用后取反）

bind

新版推荐用bind取代原各种bind，比如bind(less<int>(), _1, 40)即可实现bind2nd(less<int>(), 40)。bind可以绑定函数对象、甚至一般函数、成员函数和数据。

在namespace std::placeholders 里面有_1,_2等占位符，比如bind(myfunc,_1, 6)表示第一个不绑定，只绑定第二个参数。bind之后生成的对象自然参数会少些，甚至可以bind(myfunc,_2,_1)把两个参数换位。bind<int>(mf,_1,_2)则把返回值绑成int。

绑定成员函数要这样bind(&MyClass::func,_1)，想绑定对象实例需要bind(&MyClass::func, myobj)，否则还要传入实例才能调用。绑定成员数据就是取数据。

迭代器适配器

• reverse_iterator

  创建对象保存正向的it，其中也有五个关联类型，然后重载operator*是正向的it退一步再取值（*--tmp），--和++分别相反

• inserter

  保存容器指针和it，重载operator=，改为调用容器的insert，从而不会越界赋值（内部的iter也要++跟外部同步），从而在不修改copy函数源代码的情况下实现不同的功能（调用copy可能出现目标空间不足，如果目标iterator改为inserter(mylist,it)就可以自动开辟空间）

X适配器

• ostream_iterator

  重载了operator*和operator++

  ostream_iterator<int> out_it(cout,",");
  copy(v.begin(), v.end(), out_it); // 输出并用","分隔

• istream_iterator

  创建之后立刻调用>>等待输入一个值到缓冲区，同理可以绑定文件。不绑定cin则可以作为eos（end of stream）

  istream_iterator<int> iit(cin), eos;
  copy(iit,eos,inserter(v, v.begin())); // 直接读入到v