Lecture 1 STL Primer

Standard Template Library The Standard Template Library (STL) is a software library for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called algorithms,containers, functional, and iterators. The STL provides a ready-made set of common classes for C++, such as containers and associative arrays, that can be used with any built-in type and with any user-defined type that supports some elementary operations (such as copying and assignment). STL algorithms are independent of containers, which significantly reduces the complexity of the library. The STL achieves its results through the use of templates. This approach provides compile-time polymorphism that is often more efficient than traditional run-time polymorphism. Modern C++ compilersare tuned to minimize any abstraction penalty arising from heavy use of the STL. The STL was created as the first library of generic algorithms and data structures for C++, with four ideas in mind: generic programming, abstractness without loss of efficiency, the Von Neumann computation model, and value semantics.

vector stack queue

Stacks, Queues, and Deques A stack is a last in, first out (LIFO) data structure Items are removed from a stack in the reverse order from the way they were inserted A queue is a first in, first out (FIFO) data structure Items are removed from a queue in the same order as they were inserted A deque is a double-ended queue—items can be inserted and removed at either end

Array implementation of stacks To implement a stack, items are inserted and removed at the same end (called the top) Efficient array implementation requires that the top of the stack be towards the center of the array, not fixed at one end To use an array to implement a stack, you need both the array itself and an integer The integer tells you either: Which location is currently the top of the stack, or How many elements are in the stack

Pushing and popping 0 1 2 3 4 5 6 7 8 9 17 23 97 44 stk: top = 3 or count = 4 If the bottom of the stack is at location 0, then an empty stack is represented by top = -1 or count = 0 To add (push) an element, either: Increment top and store the element in stk[top], or Store the element in stk[count] and increment count To remove (pop) an element, either: Get the element from stk[top] and decrement top, or Decrement count and get the element in stk[count]

After popping 0 1 2 3 4 5 6 7 8 9 17 23 97 44 stk: top = 2 or count = 3 When you pop an element, do you just leave the “deleted” element sitting in the array? The surprising answer is, “it depends” If this is an array of primitives, or if you are programming in C or C++, then doing anything more is just a waste of time If you are programming in Java, and the array contains objects, you should set the “deleted” array element to null Why? To allow it to be garbage collected!

Sharing space Of course, the bottom of the stack could be at the other end top = 6 or count = 4 17 23 97 44 0 1 2 3 4 5 6 7 8 9 stk: Sometimes this is done to allow two stacks to share the same storage area topStk2 = 6 17 23 97 44 49 57 3 0 1 2 3 4 5 6 7 8 9 stks: topStk1 = 2

Error checking There are two stack errors that can occur: Underflow: trying to pop (or peek at) an empty stack Overflow: trying to push onto an already full stack For underflow, you should throw an exception If you don’t catch it yourself, Java will throw an ArrayIndexOutOfBounds exception You could create your own, more informative exception For overflow, you could do the same things Or, you could check for the problem, and copy everything into a new, larger array

STL 容器 容器：与数据类型无关的数据结构 特点：大量使用模板特化技术，实现数据结构与数据的分离 这里列出几种常用容器： list – 双端链表 vector – 向量 stack – 栈 queue – 队列 set – 有序集 map – 映射

STL list 包含头文件：#include <list> 模板原型：list<元素类型, 分配器> 竞赛使用时默认的分配器100%够用了，这之后的介绍都会忽略它 内部实现：双端链表 定义实例： list<int> listObj; // 这样就定义了一个存放整数的list实例

STL list 常用操作： .push_back(元素) // 在表尾添加元素 .push_front(元素) // 在表头添加元素 .pop_back() // 从表尾删除一个元素 .pop_front() // 从表头删除一个元素 .back() // 获取当前表尾元素 .front() // 获取当前表头元素 list1.merge(list2) // 合并list2到list1，若两个list均有序，则合并结果也保证有序 .insert(迭代器, 元素) // 在迭代器指定的位置前插入元素

STL list .remove(值) // 按值删除元素 .erase(迭代器) // 删除迭代器指定的位置处的元素 .empty() // 判断list是否为空，返回值：空：true，非空：false .size() // 获取list中的元素个数 .clear() // 清空list 注意：list不支持按下标访问

STL vector 包含头文件：#include <vector> 模板原型：vector<元素类型> 定义实例： vector<int> vecObj;

STL vector 常用操作： .reserve(长度) // 预先分配指定长度 .push_back(元素) // 在表尾添加元素 .pop_back() // 从表尾删除一个元素 vec1[下标] // 按下标访问元素 .insert(位置，元素) // 在指定位置前插入元素 .erase(位置) // 删除指定位置处的元素 .empty() // 判断vector是否为空，返回值：空：true，非空：false .size() // 获取vector中的元素个数 .clear() // 清空vector

STL stack 包含头文件：#include <stack> 模板原型：stack<元素类型> 内部实现：默认是deque，而deque又由数组链表实现 定义实例： stack<int> stackObj;

STL stack 常用操作： .push(元素) // 将元素压入栈 .pop() // 将栈顶元素弹出 .top() // 获取当前栈顶元素 .empty() // 判断stack是否为空，返回值：空：true，非空：false .size() // 获取stack中的元素个数 清空方法： while (!stk.empty()) stk.pop();

STL queue 包含头文件：#include <queue> 模板原型：queue<元素类型> 定义实例： queue<int> queueObj;

STL queue 常用操作： .push(元素) // 将元素排入队列 .pop() // 队头元素出队 .front() // 获取当前队头元素 .back() // 获取当前队尾 .empty() // 判断队列是否为空，返回值：空：true，非空：false .size() // 获取队列中的元素个数 清空方法： while (!que.empty()) que.pop();

STL set 包含头文件：#include <set> 模板原型：set<元素类型, 比较仿函数> 内部实现：红黑树（O(logn) 的插入删除、查询） 定义实例： set<int> setObj; // 内部元素从小到大排序 set<int, greater<int> > setObj; // 内部元素从大到小有序，greater仿函数在functional头文件中定义

STL set 自定义仿函数： struct MyFFunc { bool operator ()(const DType &a, const DType &b) const { // return 1 表示a “小于”b // return 0 表示a “大于等于”b } set<DType, MyFFunc> setObj;

STL set 常用操作： .insert(元素) // 插入元素 .erase(迭代器) // 删除迭代器所指的元素 .empty() // 判断set是否为空，返回值：空：true，非空：false .size() // 获取set中的元素个数 .count(元素) // 返回set中指定值的元素的个数，对于set，该函数只返回0或1 .clear() // 清空set .lower_bound(元素) // 返回指向第一个>=给定元素的迭代器

STL set .upper_bound(元素) // 返回指向第一个>给定元素的迭代器 注意：set不支持按下标访问

STL map 包含头文件：#include <map> 模板原型：map<key类型, value类型> 内部实现：红黑树 定义实例： map<string, int> mapObj; // 其中的每个元素都是键值(key, value)对

STL map 常用操作： .insert(pair<key_type, value_type>(key, value)) // 插入键值对，例子： // .insert(pair<string, int>(“str1”, 1); .find(key) // 查找指定的key对应的键值对，返回指向键值对 // 的迭代器，若找不到则返回mapObj.end() .clear() // 清空map

STL map 注意在find方法返回的迭代器中，用.first获取key，.second获取value 例子： #define TMAP map<string, int> TMAP mapObj; mapObj.insert(“str1”, 1); TMAP::iterator it = mapObj.find(“str1”); it->first // “str1” it->second // 1 // 如果找不到，it == mapObj.end()

STL 迭代器 简单地理解，迭代器==高级指针 作用：操作、访问容器中的元素 创建一个指向List<int>中第一个元素的迭代器： List<int>::iterator it = listObj.begin();

STL 迭代器 从迭代器拿到元素：*it //与指针求值类似 使用迭代器遍历容器： #define TVEC vector<int> TVEC vecObj; for (TVEC::iterator it = vecObj.begin(); it != vecObj.end(); ++it) //DoSomething 此外，按容器不同，迭代器的使用会有差别，如map的迭代器用it->first拿到key，用it->second拿到value等等

STL 算法 STL的<algorithm>头文件中有许多常用算法的高效实现，这里介绍竞赛常用的几个。 sort – 排序 stable_sort – 稳定排序 next_permutation – 产生当前排列的下一个排列 unique – 去重 lower_bound – 返回第一个大于等于给定元素的元素位置 upper_bound -返回第一个大于给定元素的元素位置

STL 算法 sort 原型：sort(容器起始位置，容器结束位置，比较函数） 起始位置和结束位置可用迭代器或数组地址表示 比较函数（相当于小于号）写法： bool cmp(数据类型 a, 数据类型 b) { // 若a“小于”b则返回true，否则返回false } 此外对于自定义类型（结构体、类），也可以通过重载小于号的方式实现“小于”关系。

STL 算法 sort 使用举例： // 对于vector<int> vec sort(vec.begin(), vec.end()); // 默认按升序排列 // 对于数组 int arr[10]; sort(arr, arr +10); // 默认按升序排列

STL 算法 stable_sort 原型：stable_sort(容器起始位置，容器结束位置，比较函数） 用法与sort一致，与sort的区别主要在于： 对于如下序列：2 1 5 3 3 1，stable_sort保证橙色的1在排序后仍然位于白色的1之前，橙色的3在排序后仍然位于白色的3之前。

STL 算法 next_permutation 原型：bool next_permutation(容器起始位置，容器结束位置） 用法： // 得到下一个排列 int arr[] = {1, 2, 3}; next_permutation(arr, arr + 3); // 此后arr为{1, 3, 2}

STL 算法 next_permutation 枚举全排列： int arr[] = {1, 2, 3}; do { // DoSomething } while (next_permutation(arr, arr + 3));

STL 算法 unique 原型：iterator unique(容器起始位置，容器结束位置) 用法： int arr[] = {1, 2, 2, 3, 1}; sort(arr, arr + 5); // 使用前先排序 int bound = ((int)unique(arr, arr + 5) – (int)arr) / sizeof(int); // 得到去重之后最后一个元素的位置+1 // 此后[0, bound) 位置之间的元素为{1, 2, 3}

STL 算法 lower_bound 原型：iterator lower_bound(容器起始位置，容器结束位置, 参考值) 用法： int arr[] = {1, 2, 2, 3, 1}; sort(arr, arr + 5); // 使用前先排序 int pos = ((int)lower_bound(arr, arr + 5, 2) – (int)arr) / sizeof(int); // 得到第一个>=2的元素在arr中的位置

STL 算法 upper_bound 原型：iterator upper_bound(容器起始位置，容器结束位置, 参考值) 用法： int arr[] = {1, 2, 2, 3, 1}; sort(arr, arr + 5); // 使用前先排序 int pos = ((int)upper_bound(arr, arr + 5, 2) – (int)arr) / sizeof(int); // 得到第一个>2的元素在arr中的位置

Practices Using STL to write some programes

参考站点 http://www.cplusplus.com/reference/stl/ 度娘、谷歌

Thank you!