STL

1.C++ Standard Libraty和Standard Template Library的区别

2.STL体系结构基础介绍

2.1六大部件

2.2六大部件的关系

一般不会写分配器，默认使用默认分配器

2.3复杂度，Complexity，Big-oh

2.4前闭后开区间

2.5range-based for statement

2.6auto keyword

3.容器之分类与各种测试

3.1容器 — 结构与分类

序列式容器关联式容器无序容器

**Array：**初始空间设多大就是多大，而不是根据元素的多少来分配空间。（前闭后闭）

**Vector：**根据插入多少元素来分配空间。（前闭后开）

**Deque：**前后都可以插入元素。（前开后开）

**List：**双向环状链表。（两个指针）

**Forward-list：**单向链表。（一个指针）

**Set/Multiset：**高度平衡二叉树，key和value无分别。

Map/Multimap：和Set的唯一区别就是，key和value区分开，可通过key来找元素，而Map不能有重复的元素，Multimap可以有重复的元素，Set也同理。

**Hash Table：**由不同篮子组成，每个篮子代表不同的链表。

3.2测试程序辅助函数

3.3使用容器array

Array必须先设置一个确定的空间大小

clock():程序从运行开始到调用该函数的时间

3.4使用容器vector

size()：真正的元素个数

capacity()：容量

3.5使用容器list

3.6使用容器forward_list

3.6使用容器slist

**slist：**单向链表

3.7使用容器deque

3.8使用容器stack

3.9使用容器queue

3.10使用容器multiset

3.11使用容器multimap

3.12使用容器unordered_multiset

3.13使用容器unordered_multimap

3.14使用容器set

3.15使用容器map

3.16使用容器unordered_set

3.17使用容器unordered_map

4.分配器之测试

4.1使用分配器allocater

5.源代码之分布（VC，GCC）

5.1标准库版本，Visual C++

5.2标准库版本，GNU C++

6.OOP（面向对象编程） vs. GP（泛式编程）

sort在类里

list的迭代器是连续的，而sort算法只有无需迭代器

sort在类外

7.技术基础：操作符重载and模板（泛化，全特化，偏特化）

7.1操作符重载

7.2Class Templates，类模板

7.3Function Templates，函数模板

7.4Member Templates，成员模板

7.5Specialization，特化

7.6Partial Specialization，偏特化

泛化：传入的是任意的type

偏特化：传入的是任意type的指针

8.分配器

allocate调用operator new，然后operator new调用malloc

deallocate调用operator delete，然后operator delete调用free

额外开销：cookie（夹心饼干），红色，上下两块，各占4个字节，总共八个字节

9.容器之间的实现关系与分类

10.深度探索list

10.1G2.9容器list

除了array和vector，其他容器的iterator都要是类，因为需要智能指针

10.2list's iterator

10.3G4.9容器list

11.迭代器的设计原则和Iterator Traits的作用与设计

12.vector深度探索

13.array、forward_list深度探索

13.1array

array不可扩充

13.2forward_list

14.deque、queue和stack深度探索

14.1deque

本质：vector

扩充后，将旧容器的元素copy到新容器的中段

14.2queue

14.3stack

15.RB-tree深度探索

16.set、multiset深度探索

16.1set

根据key排序

16.2set，in VC6

16.3multiset

优先使用容器自身提供的算法，因为是特化的，更适合该容器

17.map、multimap深度探索

17.1容器map

17.2multimap

18.hashtable深度探索

55%53=2，2%53=2，于是这两个元素都放到2号位，串联起来

19.unordered容器概念

只是名字换了而已

20.算法的形式

21.迭代器的分类（category）

22.迭代器分类（category）对算法的影响

先用某个函数判断出迭代器种类，然后根据迭代器种类调用相对应的算法，提高了算法的效率

并非强制，只是暗示

23.算法源代码剖析（11个例子）

23.1accumulate

23.2for_each

23.3repalce,replace_if,replace_copy

23.4count,count_if

23.5find,find_if

23.6sort

23.7关于reverse iterator,rbegin(),rend()

23.8binary_search

24.仿函数和函数对象

24.1仿函数functors

小括号产生临时对象

24.2仿函数functors的可适配（adaptable）条件

条件：继承去回答问题

24.3函数对象

函数对象：仿函数临时创造的对象

25.存在多种Adapter

适配器：把东西记起来，以便后面使用

25.1容器适配器

25.2函数适配器

25.3迭代器适配器

25.3X适配器:ostream_iterator

26.一个万用的hash function

27.Tuple

t.head()->第一个元素

t.tail()->第一个后面的所有元素

t.tail().head()->第二个元素

Files

STL（侯捷）.md

Latest commit

History