STL 笔记1

C++ Template 笔记

关于C++ Template这本书，作者是David VandeVoorde与 Nicolai M. Josuttis.书籍的链接

www./Templates/或http://www./tmplbook/。这本书以前的看过一篇，感觉很深入前沿，但是很多内容不清楚了，最近重新温习了一下STL源码剖析和C++ Template，感觉有必要做些笔记以供自己参考复习，因为一篇重看还是挺花时间的。   

STL 笔记1

空间分配器:
SGI STL提供了一个标准的配置器接口，接口是simple_alloc,只不过是把它做了一层隐藏。
SGI STL配置器其名称是alloc而非allocator，而且不接受任何参数。因此在使用时不能写成标准的写法：
   vector<int, std::allocator<int> iv;
应写成
   vector<int, std::alloc> iv


迭代器与traits技巧
   STL的核心在于：将数据容器(containers)和算法(algorithms)分开,彼此独立设计，最后再以一贴胶着剂将其合并。容器和算法的泛型化可以通过class template和function templates分别达到目标。设计两者之间的胶着剂则是最大的问题。
   迭代器(iterator)是一种smart pointer.
   Partial specialization (偏特化)的意义：
   如果class template拥有一个以上的template参数，可以针对其中部分(一个或者几个,但非全部)template参数进行特化工作。换句话说，可以在泛化设计中提供一个特化版本。<<泛型思维>>对Partial specialization的定义：“针对任何template参数更进一步的条件限制所设计出来的一个特化版本”.
   迭代器类型之一:value type
   迭代器类型之二：difference type
   迭代器类型之三：reference type
   迭代器类型之四：pointer type
   迭代器类型之五：iterator_category




容器(containers)：序列式容器(sequence containers)和关联式容器(associate containers)
  
序列式容器(sequence containers):


vector:
at() 函数 返回当前Vector指定位置loc的元素的引用. at() 函数 比 [] 运算符更加安全, 因为它不会让你去访问到Vector内越界的元素.


list:
merge()        合并两个list
remove_if()    按指定条件删除元素
sort()         给list排序
splice()       合并两个list
unique()       删除list中重复的元素


deque:
      采用一块所谓的map(注意，不是STL的map容器)作为主控。这里所谓map是一小块连续空间，其中每个元素(此处称为一个节点，node)都是指针，指向另一段连续线性空间，称为缓冲区。缓冲区才是deque的内存。
stack：
     允许新增元素，移除元素，取得最顶端元素.但除了最顶端外，没有任何其他方法可以存取stack的其他元素.stack不提供走访功能，也不提供迭代器。
SGI STL便以deque作为缺省情况下的stack底部结构。STL stack往往不被归为container(容器)，而被归为container adapter. List 也可以作为stack的底层容器。


queue：
以SGI STL 的deque为缺省接口。


heap:
heap并不归属STL容器组件，它是个幕后英雄，扮演priority queue的助手。


关联式容器(associate containers):
标准的STL关联式容器分为set集合和map集合，以及这两大类的衍生体multiset和multimap,这些容器都是以RB-tree为底层机制完成。此外SGI STL 还提供了一个不在标准规格之列的关联式容器：hash table 以及以hash table为底层机制的hash_set,hash_map,hash_multiset,hash_multimap.
一般而言，关联式容器的内部结构是一个balanced binary tree(平衡二叉树),以便获得良好的搜寻效率。balanced binary tree有许多类型，包括AVL-tree，RB-tree，AA-tree。
RB-tree提供两种插入操作：insert_unique()和insert_equal()，前者表示被插入的节点的键值key必须是唯一的，后者表示可以重复。
注意：RB-tree一开始就要求指定所谓的KeyOfValue仿函数，用来从value中提取key值。
对于关联式容器，使用其本身所提供的find函数查找比使用STL算法find更有效率，因为stl算法find()只是循序搜寻。企图通过迭代器来改变set是不允许的，因为set的所有迭代器都是只读的迭代器。


map:
map的所有元素都是pair，同时拥有value和key，第一个元素被视为键值，第二个元素被视为实值。Map不允许两个元素有相同的key。因为 map元素的key值关系到map的元素排列规则，因此是不能修改它其宗的key值，这样会破坏map组织。但是可以修改value值。


hash_set：
以hashtable为底层机制，其没有自动排序功能。


hash_map:
以hashtable为底层机制，其没有自动排序功能。




STL 算法
所有的STL算法都作用在由迭代器[first,last)所标出的区间上，所谓质变算法，指运算过程中会更改区间内(迭代器所指)的元素内容.
许多STL算法不只支持一个版本，这一类算法的某个版本采用缺省运算行为，另一个版本提供额外参数，接受外界传入一个仿函数(functor).有些算法 直接这样区分不同的版本，附从的那个总是以_if作为结尾。如replace(),使用内建的equality操作符进行比对操 作,replace_if()则以接受到得仿函数()进行比较行为。


质变算法通常提供两个版本：一个是in-place版，就地改变其操作对象；另一个是Copy版本，将操作对象的内容复制一份版本，然后在副本上进行修改并返回该副本。