The three parts of STL:

• Containers:
• class templates, common data structures;

• Algorithms:
• Functions that operate on ranges of elements;

• Iterators:
• Generalization of pointers, access elements in a uniform manner.

• 原理：基于OOP的思想，设计者在设计 Containers 和 Algorithms 的时候，希望尽可能的解耦，所以这两者不知道彼此之间的存在，需要一个中间的桥梁： Iterators（一个泛化的指针的概念）。

Containers

• Sequential
• 就是一个线性结构，或者说线性表
• 类型：
• Array ( static ) （静态数组）
• Vector ( dynamic ) （动态数组）
• deque ( double-ended queue ) （双端队列）
• forward_list ( singly-linked ) （单相列表）
• list ( doubly-linked ) （双向列表）

• Associative （红黑树）
• map 、 set 等，用来建立数据间的对应关系；
• 类型：
• set ( collection of unique keys )
• map ( collection of key-value pairs )
• multiset 、 multimap

• Unordered associative （哈希表）
• 同上，区别在于 Unordered associative 内部的数据是无序的，可能采用的是 Hash map 等；
• Hashed by keys;
• 类型：
• unordered_set
• unordered_map
• unordered_multiset
• unordered_multimap

• Adaptors
• 本身不会独立存在，是在其他容器的基础上做了封装之后给别人使用的；
• 类型：
• stack
• queue
• priority_queue

1. Vector

Basic operations of vector

• Constructor / destructor

• Element access
• [] ：直接像普通数组一样访问下标，不会做越界检查！
• at ：一样访问下标，但是会做越界检查！
• front
• back
• data

• Iterators
• begin ：注意区间都是前闭后开的，从 begin 开始到 end 结束
• end
• cbegin
• cend

• Capacity
• empty ：看 vector 是不是空的；
• size ： vector 的大小；
• capacity ：这个 vector 最多放多少个元素；
• reverse ：指定最大容量；

• Modifiers
• clear ：全部清空；
• insert ：任意一个位置插入新元素；
• erase ：任意一个位置删除元素；
• push_back ：在尾部插入新数据

Using vector

2. list

• 本质就是双向链表；

Using list

3. map

• Collection of key-value pairs;

• lookup by key, and retrieve a value;

• example: a telephone book, map<string, string>

Using the map

• 注意，如果 map 在查找某个元素的时候不存在，实际上会悄悄将其插入进去， key 就是 default

• 所以，更安全的做法是在使用中括号查询前先看看这个东西是否存在

Algorithms

Iterators

• connect containers and algorithms

• talk about it later
• after templates and operator overloading

Typedefs

• Annoying to type long names
• map<Name, list<PhoneNum>> phonebook ;
• map<Name, list<PhoneNum>>::iterator finger

• Simplify with typedef
• typedef map<Name, list<PhoneNum>> PB
• PB phonebook
• PB::iterator finger

• C++11: auto using

Using your own classes

• 所有算法在使用自己定义的 class 的时候，有一定要求：

• Might need:
• assignment operator, operator = ()
• default constructor

• For sorted types, like set , map … 就是 key 要能进行小于的比较
• less-than operator, operator<()

Pitfalls1 - access safety

使用 vector 的时候要小心越界的问题，尤其是直接访问下标的时候

• Access an invalid element of an vector

• using push_back() for dynamic expansion

• Preallocate with constructor

• Reallocate with Resize()

使用 map 的时候要小心默认插入

Pitfalls - silent insertion

• invalidation inserting into map<>

• Using count() or contains() to check for a key without creating a new entry

在C++11以前的性能问题：

Pitfalls - size() on list<>

• C++ 11 以前会消耗线性时间

• 但是 myList.empty() 永远是常数时间

迭代器的越界问题

Pitfalls - invalid iterator

• 例如，如果擦出了某个迭代器指向的元素，但是又用 li++ 访问下一个元素，就会报错；

• 正确的做法是使用 erase() 的返回值