【笔记】STL的七种武器（一）顺序容器

5.STL 中有用于操作迭代器的三个函数模板，它们是：

• advance(p, n)：使迭代器 p 向前或向后移动 n 个元素。
• distance(p, q)：计算两个迭代器之间的距离，即迭代器 p 经过多少次 + + 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。
• iter_swap(p, q)：用于交换两个迭代器 p、q 指向的值。

< CONTAINER >顺序容器

0.　　vector 　　deque　　list

顺序容器的取舍，一般应遵循下面的原则：

高效的随即存取，而不在乎插入和删除的效率，使用vector

大量的插入和删除，而不关心随即存取，则应使用list

随即存取，而且需要两端数据的插入和删除，则应使用deque

1.常用算法函数

a.front();                 a.back(); 

a.size();                  a.clear();   

a.push_front(x);      a.pop_front();

a.push_back(x);      a.pop_back();

a.insert(it, x);           

a.erase(it);               a.erase(first, last)

2.vector 例题：

back and forth 倒牛奶[USACO]

图的表示和存储

3.deque 

扑克游戏： 题目加题解在这

4.list 循环链表

List容器的每个节点都含有 前驱元素指针域 、 数据域 、 后继元素指针域 。

在链表的任意位置进行元素的插入、删除和查找操作速度是较快的。

由于list对象的结点并不要求在一段连续的内存中，所以对于迭代器，只能通过“++”或者“–”的操作，不能对其进行+N或者-N的操作。

操作：

一）创建list对象：

　　list l　或　list l(10); //创建具有10个整形元素的list对象l 。

（二）插入元素：

　　push_back()　　push_front()　　insert()

（三）遍历元素：

（1）前向遍历：以前向迭代器的方式遍历；

（2）反向遍历：使用反向迭代器进行遍历。

（四）删除元素：

（1）remove(元素值)，删除链表中的元素，值相同的元素都会被删除；

（2）pop_front() 　　pop_back()

（3）erase()删除迭代器位置的元素；

（4）clear()清空链表容器。

（五）查找元素：需要添加#include

　　find(迭代器1，迭代器2，元素)

　　函数返回一个迭代器值，若该值被找到则返回该值所在的迭代器值，若没有找到则返回end()迭代器的位置。

（六）l.sort()实现升序排序

list例题：

士兵队列训练问题