STL源码剖析 -- 读书笔记

2. 空间配置器(allocator)定义于<memory>中

3. 迭代器(iterator)最总要的作用就是对operator* 和 operator->进行重载(overloading)工作。

4. auto_ptr：用来包装原生指针(native pointer)的对象，内存漏洞(memory leak)问题可藉此获得解决。

5. Partial Specialization (偏特化) ：如果 class template 拥有一个以上的 template 参数，我们可以针对其中某个（或数个，但非全部）template 参数进行特化工作。换句话说，我们可以在泛化设计中提供一个特化版本（也就是将泛化版本中的某些 template 参数赋予明确的指定）。

6.容器（内缩方式来表示基层与衍生层的关系，这里的衍生，不是派生(inheritance)关系，而是内含(containment)关系。例如：heap内含一个vector，priority-queue内含一个heap、stack和queue都内含一个deque，set/map/multiset/multimap 都内含一个RB_tree，hash_x 都内含一个hashtable。）

　　序列式容器（Sequence Containers）：

 　　　　array(build-in) C++内建

 　　　　vector

　　　　　　<1> vector中增加新元素时，如果超过了当时的容量，则容量会扩充至两倍。如果容量仍不足，就扩张至足够大的容量。

　　　　　　<2> 对vector的任何操作，一旦引起空间重新配置，指向元vector的所有的迭代器就都失效了。

　　　　　　<3> 关于erase，erase有两种

　　　　　　　　erase(iterator position) 删除位置为position的元素。

　　　　　　　　erase(iterator __first, iterator __last)的删除区间为[__first, __last)。

　　　　　　<4> 关于insert，insert有三种

　　　　　　　　插入完成后，新节点将位于哨兵迭代器(__position)所指节点的前方——这是STL对于“插入操作”的标准规范。

　　　　　　　　insert(iterator __position, const value_type& __x) ：在__position之前插入x

　　　　　　　　insert(iterator __position, size_type __n, const value_type& __x)：在__position之前插入n个x

　　　　　　　　insert(iterator __position, _InputIterator __first, _InputIterator __last)：在__position之前插入[__first, __last)的元素

　　　　　　heap：以算法形式呈现(xxx_heap)

　　　　　　　　<1> STL提供的heap操作，只有make_heap(), pop_heap(), sort_heap()三个操作

　　　　　　　　　　1、 关于make_heap(), 有两个版本

　　　　　　　　　　　　make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last);

　　　　　　　　　　　　make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp);

　　　　　　　　　　2、 关于push_heap(), 也有两个版本，push_heap中[__first, last - 1)中的元素为一个合法堆，last - 1 处元素相当于入堆得元素。

　　　　　　　　　　　　push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

　　　　　　　　　　　　push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

　　　　　　　　　　3、 关于pop_heap(), 也有两个版本，pop_heap之后，出堆的元素在__last-1位置

　　　　　　　　　　　　pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

　　　　　　　　　　　　pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

　　　　　　　　<2> 关于heap应当的改进，希望能够加入修改堆中元素值的功能。可以命名为update();

　　　　　　　　priority-queue

　　　　　　　　　　<1> priority_queue 用 heap 实现的 vector序列。

　　　　　　　　　　<2> priority_queue 不提供迭代器。

　　　　list

　　　　slist：非标准

　　　　deque

　　　　　　stack：配置器

　　　　　　　　<1> stack 往往不被归类为 container(容器)，而被归类为 container adapter。

　　　　　　queue：配置器

　　关联式容器（Associative Containers）：

　　　　RB-tree：非公开

　　　　　　set

　　　　　　map

　　　　　　multiset

　　　　　　multimap

　　　　hashtable：非标准

　　　　　　参照hash_map中的写法应该这样定义

　　　　　　　　hashtable<pair<const key_type, value_type>,   

　　　　　　　　　　　　　  key_type,   

　　　　　　　　　　　　　　hash<key_type>,   

　　　　　　　　　　　　　  _Select1st<pair<const key_type,value_type> >,  

　　　　　　　　　　　　     equal_to<key_type>,  

　　　　　　　　　　　　　  allocator<value_type>   

　　　　　　　　　　　　　　> ht(50, hash<key_type>(), equal_to<key_type>());

　　　　　　hash_set：非标准

　　　　　　hash_map：非标准

　　　　　　hash_multiset：非标准

　　　　　　hash_multimap：非标准

7. 算法(Algorithms)

8. 配接器(Adapter)