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.

Containers

• Sequential（线性表） array ( static ) 静态数组 vector ( dynamic ) 动态数组 deque ( double-ended queue ) 双端队列 forward-list ( singly-linked ) 单相列表 list ( doubly-linked ) 双向列表

• Associate （红黑树） set ( collections of unique keys ) map ( collections of key-value pairs ) multiset, multimap 允许重复

• Unordered associative （哈希表） hashed by keys
• unordered_set
• unordered_map
• unordered_multiset
• unordered_multimap

• Adaptors 本身不会独立存在，是在其他容量的基础上做了封装之后使用的 stack, queue, priority_queue

vector

Basic operations for vector

• Constructor / Destructor

• Element access
• at 会做越界检查
• operator[] 不会做越界检查
• front
• back
• data 访问值

• lterators
• begin
• end
• cbegin
• cend

• Capacity
• empty ： 检查是否非空
• size ： vector 的大小
• capacity ：最多能放多少元素
• reverse ：指定最大容量

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

Example

list

Example

map

• Collection of key-value pairs.

• lookup by key, and retrieve a value.

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

Example

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

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

Algorithms

• Works on a range defined as [first, last).

• for_each, find, count, ...

• copy, fill, transform, replace, rotate, ...

• sort, partial_sort, nth_element, ...

• set_difference, set_union, ...

• min_element, max_element, ...

• accumulate, partial_sum, ...

• ...

Iterators

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

• Might need:
• assignment operator, operator = () ：赋值运算符
• default constructor ：默认构造函数

• For sorted types, like set , map …
• less-than operator, operator<() ：小于运算符
• 是什么？ 这是当你写 objectA < objectB 时调用的函数。它需要返回一个 bool 值，告诉程序 objectA 是否“小于”objectB。
• 为什么需要？ 像 set 和 map 这样的容器，其核心功能就是自动为存入的元素排序。为了能排序，它们必须知道任意两个元素谁应该排在前面。它们默认的比较规则就是使用 < 运算符。

Pitfalls