文章目录
认识headers
C++ 标准库（STL大部分属于C++标准库） —STL和标准库的关系
STL各组件应用实例
STL体系结构基础介绍
1.容器帮助我们吧内存的问题解决，需要一个分配器来支持容器，容器是一个模板类，有一些操作是自己做，更多的是独立出来成为算法。算法和容器之间的桥梁是迭代器，迭代器是一种泛化的指针
STL分为六大组件：
容器(container)：常用数据结构，大致分为两类，序列容器，如vector，list，deque，关联容器，如set，map。在实现上，是类模板(class template)
迭代器(iterator)：一套访问容器的接口，行为类似于指针。它为不同算法提供的相对统一的容器访问方式，使得设计算法时无需关注过多关注数据。（“算法”指广义的算法，操作数据的逻辑代码都可认为是算法）
算法(algorithm)：提供一套常用的算法，如sort，search，copy，erase … 在实现上，可以认为是一种函数模板(function template)。
配置器(allocator)：为容器提供空间配置和释放，对象构造和析构的服务，也是一个class template。
仿函数(functor)：作为函数使用的对象，用于泛化算法中的操作。
配接器(adapter)：将一种容器修饰为功能不同的另一种容器，如以容器vector为基础，在其上实现stack，stack的行为也是一种容器。这就是一种配接器。除此之外，还有迭代器配接器和仿函数配接器。
STL 六大组件的交互关系
Container 通过 Allocator 取得数据储存空间
Algorithm 通过 Iterator 存取 Container 内容
Functor 可以协助 Algorithm 完成不同的策略变化
Adapter 可以修饰或套接 Functor、Iterator。
vector<> 尖括号说明是一个模板
//一个例子说明六大部件
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;
int main()
{
int ia[6] = {27, 210, 12, 47, 109, 83};
vector<int, allocator<int>> vi(va,ia + 6);//<>符号表示模板，allocator<int>是一个分配器模板，一般vector都会自动默认使用分配器
cout << count_if(vi.begin(), vi.end(),
not1(bind2nd(less<int>(), 40)));
return 0;
}
//vector是一个容器containers
//count_if是一个算法algorithm，计算vi里面的个数
//vi.begin(), vi.end()是一个迭代器iterator
//less<int>是一个仿函数function
//bind2nd是一个适配器function adapter，绑定第二个参数为40
//notl是一个适配器function adapter,表示否定
//整个表达，vi大于等于40的个数
容器规定：“前闭后开”区间（涵盖第一个不涵盖最后一个） [)
引用代表其自身
容器之分类与各种测试
容器种类：
1.顺序容器Sequence Containers
Array（固定元素个数）C++11
Vector（尾部个数可以扩充）
Deque（头尾个数可以扩充）
List（双向链表）
Forward-List（单向链表）C++11
2.关联容器Associative Containers：元素有key和value，适合做快速的查找
底层实现是红黑树，可以自动左右平衡
Set/Multiset（key=value）
Map/Multimap(key对应value；multimap允许重复元素，map不允许有重复)
不定序容器Unordered Containers（属于关联容器）
HashTable Separate chaining（不定序容器使用hashtable）：同放一个内存，内存放这几个数据的链表
使用array
tips1: array.data()返回数组在内存中起点的地址
tips2: 二分查找的数组肯定是已经经过排序的，否则无法使用二分查找
tips1: try和catch是在抓取异常的发生，如果发生异常一定要abort退出程序
tips2: ::find表明是全局函数，如果不加的话程序最后也会去全局找
tips3:vector扩充是在别的地方找到一块内存，然后把原来的搬过去，找到的那一块必须是两倍大
使用list
tips1:动态内存
tips2:标准库提供全局sort，list容器自己也有sort，容器自己的sort一定是比较快（197行）
使用forward_list
使用deque
tips1:一段叫做一个buffer，指针走到一段buffer末尾，++操作符重载自动走到下一段，所以deque是分段连续
tips2:list每次扩充一个节点，效率最高，但是查找很慢；vector每次扩充两倍；deque扩充一个buffer
tips3:deque没有自己的sort，只能用全局sort
tips4:关联式容器的查找都非常快
使用stack,queue
tips1:stack和queue底层是通过deque实现的,从设计模式上来说,这两种容器本质上是deque的适配器.
tips2:这两个容器的元素进出是有严格顺序的,因此stack和queue不支持有关迭代器的操作.比如stack,防止iterator改变其先进后出的独特特性
**使用multiset **
tips1：multiset自带的find函数比全局find要快，但是insert要慢一点
使用multimap
tips:因为multimap支持重复的key,因此不能使用重载的[]运算符进行插入
**使用unordered_multiset/map **
tips1:unordered_multiset和unordered_multimap底层是使用hash+链表实现的.
tips2:unordered_multiset和unordered_multimap的元素个数小于篮子数目,若元素数目达到篮子个数,则容器扩容,将篮子数组扩充约一倍.
使用set /map
tips1:map可以用[],因为key不会重复
使用unordered_set /map
分配器之测试
容器的背后需要分配器支持其对内存的使用
STL容器默认的分配器是std::allocator,除此之外gcc额外定义了几个分配器,其头文件均在目录ext下.
gcc额外定义的分配器均位于__gnu_cxx命名空间下.分配器一般用于构建容器,不会直接使用.因为分配器想要直接使用也不好用(使用free关键字时不需要指定回收内存的大小,而分配器的deallocate函数需要指定回收内存大小).
STL容器源码分析
STL设计模式:OOP和GP
整个C++标准库并不是用面向对象实现的，而是泛型编程
OOP(Object-Oriented Programming)和GP(Generic Programming)是STL容器设计中使用的两种设计模式.
1.OOP的目的是将数据和方法绑定在一起,例如对std::list容器进行排序要调用std::list::sort方法（sort放到list里面）.
2.GP的目的是将数据和方法分离开来,例如对std::vector容器进行排序要调用std::sort方法.
为什么list不能像vector和deque一样去用全局的sort，这种不同是因为std::sort方法内部调用了iterator的-运算，如果要运用需要满足一定的条件,std::list的iterator没有实现-运算符,而std::vector的iterator实现了-运算符.
运算符重载与模板特化
实现STL的两大基础就是运算符重载和模板特化.
特化又叫做全特化，即完整的特化，相对应的是局部的特化。偏特化：有两个模板参数，只指定其中一个，这是数量上的偏特化，还有范围上的偏特化
分配器
VC6.0的默认分配器std::allocator定义如下,可以看到VC6.0的分配器只是对::operator new和::operator delete的简单封装
allocator()创建一个临时对象
gcc2.9中的分配器std::allocator与VC6.0的实现类似,但std::allocator并非gcc2.9的默认分配器,观察容器源码,可以看到,gcc2.9的默认分配器为std::alloc.
做法是减少malloc的使用，因为malloc带有额外的开销，malloc每次分配的内存有大有小，所以需要cookie去记录，但容器里面元素的大小是一样的，所以似乎不需要吧每个元素的大小都记录。
std::alloc内部维护一个链表数组,数组中的每个链表保存某个尺寸的对象（以8的倍数增长）,减少了调用malloc的次数,从而减小了malloc带来的额外开销.每个容器元素的大小都被调整为8的倍数（比如50->56）
在gcc4.9以后,默认分配器变为std::allocator,变回了对::operator new和::operator delete的简单封装.gcc2.9中的std::alloc更名为__gnu_cxx::__pool_alloc.
容器
list
1.在32位电脑上，一个指针4个字节
2.因为链表是一个非连续空间，所以iterator不能够是一个指针，但要模拟指针的操作（除了vector和array之外，所有容器的iterator必须是一个class，才能够完成足够聪明的动作）
3.为实现前闭后开的特性,在环形链表末尾加入一个用以占位的空节点,并将迭代器list::end()指向该节点.
iterator要模拟指针，即箭头符号，，++，–甚至+=，-=操作符。迭代器__list_iterator重载了指针的,->,++,–等运算符,并定义了iterator_category、value_type、difference_type、pointer和pointer5个关联类型(associated types),这些特征将被STL算法使用.
为了模仿整数i++不能连续做两次即（i++）++,所以i++的返回值是self。而++i是返回引用&
————————————————————————————————————————————————————————————————————————
iterator需要遵循的原则
1.算法需要知道iterator有哪些性质，因为他要做动作
2.下面的rotate例子中，iterator_category指的是其移动性质，有的iterator可以++，有的可以–，有的可以跳着走
difference_type：两个iterator之间的距离应该用什么type去表现
value_type：iterator所指元素本身的类型，如string等
另外两种性质reference和pointer从来没有被使用过
STL的算法传入的参数的一般是迭代器或指针,在算法内部,需要根据传入的迭代器或指针推断出迭代器的关联类型(associated types).
有时候呼叫的是一个指针，而不是泛化的指针iterator，但指针不能回答关联的问题，所以需要traits
1.迭代器的5个关联类型在类中均有定义,但是指针类型的关联类型需要根据指针类别进行确定,为了使STL算法同时兼容迭代器和一般指针,就在迭代器(指针)和算法之间加一个中间层萃取器(traits).
2.迭代器萃取器iterator_traits能够兼容迭代器和一般指针,获取其5个关联类型:iterator_category、value_type、difference_type、pointer和pointer.
在实现上,iterator_traits类使用模板的偏特化,对于一般的迭代器类型,直接取迭代器内部定义的关联类型;对于指针和常量指针进行偏特化,指定关联类型的值.
// 针对一般的迭代器类型,直接取迭代器内定义的关联类型
template<class I>
struct iterator_traits {
typedef typename I::iterator_category iterator_category;
typedef typename I::value_type value_type;
typedef typename I::difference_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
// 针对指针类型进行特化,指定关联类型的值
template<class T>
struct iterator_traits<T *> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
};
// 针对指针常量类型进行特化,指定关联类型的值
template<class T>
struct iterator_traits<const T *> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type; // value_tye被用于创建变量,为灵活起见,取 T 而非 const T 作为 value_type
typedef ptrdiff_t difference_type;
typedef const T* pointer;
typedef const T& reference;
};
想要在算法内获取关联类型的值,只需像下面这样写:
template<typename T>
void algorithm(...) {
typename iterator_traits<I>::value_type v1;
}
vector
1.容器vector的迭代器start指向第一个元素,迭代器finish指向最后一个元素的下一个元素,这两个迭代器对应begin()和end()的返回值,维持了前闭后开的特性.
2.vector对使用者是连续的,因此重载了[]运算符.
3.vector的实现也是连续的,因此使用指针类型做迭代器(即迭代器vector::iterator的实际类型是原生指针T*).