STL

• // 标准模板库 是一种类模板

THree Parts of STL

1. Containers
• class templates,common data structures

2. Algorithms
• functions that operate on ranges of containers

3. Iterators (迭代器)
• Generalizaiton of pointers(指针的推广)——用来访问各种container下的元素，统一了访问方式;这样Algorithms就可以针对各种container进行操作，而不依赖于容器类型，相当于在Algorithm与Container之间做了一个中间层的桥梁

Containers

1. Sequencial –顺序
• array –数组(static) > 与数组不同的是，array是一个独立类型，可以作为一个完整的参数去传递，Eg:在函数传参的过程中，传统静态数组只能通过传递首地址指针的方式来传递，但是array可以一整个类型传入进去;
• vector –向量(dynamic) > vector与array不同的是它是动态的，vector可以根据插入、删除元素，来自动增长容量;
• deque –双端队列 > 与vector很像,不同是vector只能在末端增长，但是deque可以在两端增长;
• forward_list –单向链表
• list –双向链表

2. Associative –结合(一般内部有顺序)
• set –集合 > 可以快速作查找等操作;set的底层往往是红黑树
• map –映射 > 与set相比，它不是只有value而是一系列的键值对，可以实现key直接查找，本质还是红黑树不过带着键;
• multiset –多重集合(value能不能重复)
• multimap –多重映射(key能不能重复)

3. Unordered – 无序 (底层就是哈希表 hashed by keys)
• unordered_set
• unordered_map
• unordered_multiset
• unordered_multimap

4. Adaptors –适配
• stack –栈
• queue –队列 ….

Vector

Basic Operations for Vector

• Constructors & Destructors

• Accessing Elements
• at (at 会检查越界 []不会), [], front(), back(), data(), ···

• Iterators
• begin(),end(),cbegin(),cend() – cbegin()与cend()返回的是const迭代器

• Capacity
• empty(), size(), reserve(), capacity() > capacity()返回的是当前vector的底层总容量，size()返回的是当前vecto中r的元素个数

• Modifiers
• clear(), insert(), erase(), push_back(), pop_back(), resize(), swap()

List

Map

• 底层是红黑树，查找和删除都很快

如果在上述程序中，cin终端输入的key不是map中的值，比如输入了tom ，那么map中就会自动添加一个键值对，tom:0 ，然后total就会加上0，所以total最后值不会受到影响，但是map里面会多一对tom: 0的键值对。

所以其实可以在while里面添加一条判断语句，来判断读入的item在不在map里面，如下:

利用map的silent insert

Alogorithms

• for_each, find, count 以不改变值的查找为主——遍历，查找，统计

• copy, fill, transform replace, rotate

• set_difference, set_union

• sort, partial_sort, nth_union

• min_element, max_element

• accumulate, partial_sum

Using your own classes

针对你自己的类型作一些定制的操作

• assignment operator(赋值操作)

• less-than operator(比较操作)

access safety

• 注意就算是vector也不要下标越界

• use push_back() for dynamic expansion

for checking if empty

1. size() == 0
• This might be slow(linear time)

2. empty() == 0
• Constant time
• empty() returns a boolean value

Iterator

Generalizaiton of pointers(指针的推广)——用来访问各种container下的元素，统一了访问方式;这样Algorithms就可以针对各种container进行操作，而不依赖于容器类型，相当于在Algorithm与Container之间做了一个中间层的桥梁

• 就是一个可以用于各种container的指针,Eg:

• 注意：—————— 是相当于 元素 指针！而不是container中的元素本身，可以理解为指针

如果你要有一些访问的时候，要注意比如：map<string, int>::iterator it;,这时候这个迭代器it就指向map中的一个键值对元素了，但是如果你要访问比如说 it 的(key,value) 中的key 的值 ，就要用it->first 但是如果你用的是 auto &it : students 的引用变量 就可以用直接访问 it.first

invalid iterator after erase()

erase() returns an iterator to the next element of the one you erased , but the one you erased is invalid now.

• Wrong code：

• Right code：
• the L.erase will automatically return the next iterator of li.