学习备忘录：
总体分类：
- 标准STL序列容器：vector、string、deque和list。
- 标准STL关联容器：set、multiset、map和multimap。
- 非标准序列容器: slist和rope。slist是一个单向链表，rope本质上是一个重型字符串。
- 非标准关联容器: hash_set、hash_multiset、hash_map和hash_multimap。
list就是数据结构中的双向链表；vector是一种动态数组，是基本数组的类模板；
deque是一个double-ended queue，双端队列；因此在实际使用时；
如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：
1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2、如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3、如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。
1 列表(list) <list>
STL中的list就是一双向链表，可高效地进行插入删除元素。
list不支持随机访问。所以没有 at(pos)和operator[]。
list对象list1, list2分别有元素list1(1,2,3),list2(4,5,6)。list<int>::iterator it;
| list成员 | 说明 |
| constructor | 构造函数 |
| destructor | 析构函数 |
| operator= | 赋值重载运算符 |
| assign | 分配值 |
| front | 返回第一个元素的引用 |
| back | 返回最后一元素的引用 |
| begin | 返回第一个元素的指针(iterator) |
| end | 返回最后一个元素的下一位置的指针 |
| rbegin | 返回链表最后一元素的后向指针(reverse_iterator or const) |
| rend | 返回链表第一元素的下一位置的后向指针 |
| push_back | 增加一元素到链表尾 |
| push_front | 增加一元素到链表头 |
| pop_back | pop_back()删除链表尾的一个元素 |
| pop_front | 删除链表头的一元素 |
| clear | 删除所有元素 |
| erase | 删除一个元素或一个区域的元素(两个重载) |
| remove | 删除链表中匹配值的元素(匹配元素全部删除) |
| remove_if | 删除条件满足的元素(遍历一次链表)，参数为自定义的回调函数 |
| empty | 判断是否链表为空 |
| max_size | 返回链表最大可能长度 |
| size | 返回链表中元素个数 |
| resize | 重新定义链表长度(两重载函数) |
| reverse | 反转链表 |
| sort | 对链表排序，默认升序 |
| merge | 合并两个有序链表并使之有序 |
| splice | 对两个链表进行结合(三个重载函数) 结合后第二个链表清空 |
| insert | 在指定位置插入一个或多个元素(三个重载函数) |
| swap | 交换两个链表(两个重载) |
| unique | 删除相邻重复元素 |
1.list构造函数
list<int> L0; // 空链表
list<int> L1(9); // 建一个含个默认值是的元素的链表
list<int> L2(5,1); // 建一个含个元素的链表，值都是
list<int> L3(L2); // 建一个L2的copy链表
list<int> L4(L0.begin(), L0.end());//建一个含L0一个区域的元素 2. assign()分配值，有两个重载
L1.assign(4,3); // L1(3,3,3,3)
L1.assign(++list1.beging(), list2.end()); // L1(2,3) 3．operator= 赋值重载运算符
L1 = list1; // L1(1,2,3) 4. front()返回第一个元素的引用
int nRet = list1.front() // nRet = 1 5. back()返回最后一元素的引用
int nRet = list1.back() // nRet = 3 6. begin()返回第一个元素的指针(iterator)
it = list1.begin(); // *it = 1 7. end()返回最后一个元素的下一位置的指针(list为空时end()=begin())
it = list1.end();
--it; // *it = 3 8.rbegin()返回链表最后一元素的后向指针(reverse_iterator or const)
list<int>::reverse_iterator it = list1.rbegin(); //*it = 3 9. rend()返回链表第一元素的下一位置的后向指针
list<int>::reverse_iterator it = list1.rend(); // *(--riter) = 1 10.push_back()增加一元素到链表尾
list1.push_back(4) // list1(1,2,3,4) 11. push_front()增加一元素到链表头
list1.push_front(4) // list1(4,1,2,3) 12. pop_back()删除链表尾的一个元素
list1.pop_back() // list1(1,2)
13.pop_front()删除链表头的一元素
list1.pop_front() // list1(2,3) 14．clear()删除所有元素
list1.clear(); // list1空了,list1.size() =０ 15.erase()删除一个元素或一个区域的元素(两个重载函数)
list1.erase(list1.begin()); // list1(2,3)
list1.erase(++list1.begin(),list1.end()); // list1(1) 16. remove()删除链表中匹配值的元素(匹配元素全部删除)
list对象L1(4,3,5,1,4)
L1.remove(4); // L1(3,5,1); 17.remove_if()删除条件满足的元素(遍历一次链表)，参数为自定义的回调函数
// 小于2的值删除
bool myFun(const int& value) { return (value < 2); }
list1.remove_if(myFun); // list1(3) 18.empty()判断是否链表为空
bool bRet = L1.empty();
//若L1为空，bRet = true，否则bRet = false。 19.max_size()返回链表最大可能长度
list<int>::size_type nMax = list1.max_size();
// nMax = 1073741823 20．size()返回链表中元素个数
list<int>::size_type nRet = list1.size(); // nRet = 3 21.resize()重新定义链表长度(两重载函数)
list1.resize(5) // list1 (1,2,3,0,0)用默认值填补
list1.resize(5,4) // list1 (1,2,3,4,4)用指定值填补 22.reverse()反转链表:
list1.reverse(); // list1(3,2,1) 23.sort()对链表排序，默认升序(可自定义回调函数)
list对象L1(4,3,5,1,4)
L1.sort(); // L1(1,3,4,4,5)
L1.sort(greater<int>()); // L1(5,4,4,3,1) 24.merge()合并两个有序链表并使之有序
// 升序
list1.merge(list2); // list1(1,2,3,4,5,6) list2现为空
// 降序
L1(3,2,1), L2(6,5,4)
L1.merge(L2, greater<int>()); // list1(6,5,4,3,2,1) list2现为空 25.splice()对两个链表进行结合(三个重载函数) 结合后第二个链表清空
list1.splice(++list1.begin(),list2);
// list1(1,4,5,6,2,3) list2为空
list1.splice(++list1.begin(),list2,list2.begin());
// list1(1,4,2,3); list2(5,6)
list1.splice(++list1.begin(),list2,++list2.begin(),list2.end());
//list1(1,5,6,2,3); list2(4) 26.insert()在指定位置插入一个或多个元素(三个重载函数)
list1.insert(++list1.begin(),9); // list1(1,9,2,3)
list1.insert(list1.begin(),2,9); // list1(9,9,1,2,3);
list1.insert(list1.begin(),list2.begin(),--list2.end());//list1(4,5,1,2,3); 27.swap()交换两个链表(两个重载)
list1.swap(list2); //list1（4，5，6） list2（1，2，3） 28. unique()删除相邻重复元素
L1(1,1,4,3,5,1)
L1.unique();// L1(1,4,3,5,1) bool same_integral_part (double first, double second)
{ return ( int(first)==int(second) ); }
L1.unique(same_integral_part);
2 双端队列(deque) <deque>
连续存储的指向不同元素的指针所组成的数组<deque>
和list 相比 deque 没有的操作： splice,remove,remove_if,unique,merge,sort ,reverse
多了的操作： at operator[] 其余基本一致；
简单样例：
#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque <int> d;
d.push_back(1); // 尾部插入
d.push_back(2);
d.push_back(3);
d.push_front(10);
d.insert(d.begin()+1, 88);
//以数组方式遍历
for(int i = 0; i <= 5; i++)
cout << d[i] << ' '; cout << endl;
// 以反向迭代器方式遍历
deque <int> :: reverse_iterator rit;
for(rit = d.rbegin(); rit != d.rend(); rit++)
cout << *rit << ' ';cout << endl;
// 前向迭代器方式遍历
deque <int> :: iterator it;
for(it = d.begin(); it != d.end(); it++)
cout << *it << ' ';cout << endl;
d.erase(d.begin()+1);
for(it = d.begin(); it != d.end(); it++)
cout << *it << ' ';cout << endl;
d.clear();cout << d.size();
return 0;
} 3 向量(vector) <vectore>
＃include <vector>，vector是一种动态数组，是基本数组的类模板。其内部定义了很多基本操作。
既然这是一个类，那么它就会有自己的构造函数， vector 和deque 相比少了 push_front,pop_front操作
多了 capacity reserve 操作
参考：
http://blog.csdn.net/gumingyaotangwei/article/details/7415338
（list 部分原创为）
http://www.cnblogs.com/fangyukuan/archive/2010/09/21/1832364.html
转自：http://www.cnblogs.com/skyming/archive/2012/04/01/2427854.html
![POJ 1284 Primitive Roots (欧拉函数&原根定理)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)