stl库的简单应用
记性不好，贴着怕忘了。。。
有stack、queue、priority_queue、map…（未完待续）
随便p了张图
[hermit auto=”0″ loop=”0″ unexpand=”0″ fullheight=”0″]netease_songs#:26620638[/hermit]
先普及一下基础知识。。。
容器是储存元素的东西，C++中的容器类包括“顺序存储结构”和“关联存储结构”，前者包括vector，list，deque等；后者包括set，map，multiset，multimap等。若需要存储的元素数在编译器间就可以确定，可以使用数组来存储，否则，就需要用到容器类了。
1、vector
连续存储结构，每个元素在内存上是连续的；
支持高效的随机访问和在尾端插入/删除操作，但其他位置的插入/删除操作效率低下；
2、deque
连续存储结构，即其每个元素在内存上也是连续的，类似于vector，不同之处在于，deque提供了两级数组结构，第一级完全类似于vector，代表实际容器；另一级维护容器的首位地址。
这样，deque除了具有vector的所有功能外，还支持高效的首端插入/删除操作。
3、list
非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。
支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针，开销也比较大。
顺序性容器
vector
从后面快速的插入与删除，直接访问任何元素
deque
从前面或后面快速的插入与删除，直接访问任何元素
list
双链表，从任何地方快速插入与删除
关联容器
set
快速查找，不允许重复值
multiset
快速查找，允许重复值
map
一对多映射，基于关键字快速查找，不允许重复值
multimap
一对多映射，基于关键字快速查找，允许重复值
1.stack
头文件：<stack>
stack模板类需要两个模板参数，一个是元素类型，一个容器类型，但只有元素类型是必要的，在不指定容器类型时，默认的容器类型为deque。
例子
stack<int> s1;
stack<string> s2;
操作
入栈，如例：s.push(x);
出栈，如例：s.pop();//注意，出栈操作只是删除栈顶元素，并不返回该元素。
访问栈顶，如例：s.top()
判断栈空，如例：s.empty()，当栈空时，返回true。
访问栈中的元素个数，如例：s.size()
2.queue
头文件：<queue>
与stack模板类很相似，queue模板类也需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque类型。
例子
queue<int> q1;
queue<string> q2;
操作
入队，如例：q.push(x); 将x接到队列的末端。
出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问队首元素，如例：q.front()，即最早被压入队列的元素。
访问队尾元素，如例：q.back()，即最后被压入队列的元素。
判断队列空，如例：q.empty()，当队列空时，返回true。
访问队列中的元素个数，如例：q.size()
3.priority_queue
在<queue>头文件中，还定义了另一个非常有用的模板类priority_queue(优先队列）。优先队列与队列的差别在于优先队列不是按照入队的顺序出队，而是按照队列中元素的优先权顺序出队（默认为大者优先，也可以通过指定算子来指定自己的优先顺序）。
priority_queue模板类有三个模板参数，第一个是元素类型，第二个容器类型，第三个是比较算子。其中后两个都可以省略，默认容器为vector，默认算子为less，即小的往前排，大的往后排（出队时序列尾的元素出队）。
操作
入队，如例：q.push(x); 将x接到队列的末端。
出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问队首元素，如例：q.top()，即最早被压入队列的元素。
访问队尾元素，如例：q.back()，即最后被压入队列的元素。
判断队列空，如例：q.empty()，当队列空时，返回true。
访问队列中的元素个数，如例：q.size()
例子
最基本的：priority_queue<int> Q;
优先队列最基本的功能就是出队时不是按照先进先出的规则，而是按照队列中优先级顺序出队。
知识点：1、一般存放实型类型，可比较大小
2、默认情况下底层以Vector实现
3、默认情况下是大顶堆，也就是大者优先级高，后面可以自定义优先级比较规则
次基本的功能：int a[5]={3,4,5,2,1}; priority_queue<int> Q(a,a+5);
可以将一个存放实型类型的数据结构转化为优先队列，这里跟优先队列的构造函数相关。
上面那个默认构造一个空的优先队列，什么都使用默认的。
而这里使用的是
priority_queue(InputIterator first,InputIterator last)
就是给出了一个容器的开口和结尾，然后把这个容器内容拷贝到底层实现(默认vector)中去构造出优先队列。这里也使用了一个默认的比较函数，也是默认大顶堆
第三基本的功能：typedef pair<long,int> Pair;priority_queue< Pair,vector< Pair >,greater< Piar > > Q;
这个里面定义了一个制定存放元素(Node),底层实现以vector实现（第二个参数）,优先级为小顶堆(第三个参数)。
前两个参数没什么说的，很好理解，其中第三个参数，默认有三写法：
小顶堆：greater<TYPE>
大顶堆：less<TYPE>
最常用的功能：
1.重载小于号
运算符重载是通过创建运算符函数实现的，运算符函数定义了重载的运算符将要进行的操作。运算符函数的定义与其他函数的定义类似，惟一的区别是运算符函数的函数名是由关键字operator和其后要重载的运算符符号构成的。
通俗的讲，就是当小于号执行时，前后都是这个结构体，就调用这里的内容。。。
重载运算符的格式
<返回类型说明符> operator <运算符符号>(<参数表>)
{
<函数体>
}
重载小于号还有两种方法，一种是在结构体内重载，一种是在外重载。
在结构体外（推荐使用这种，以为这样可以与sort，set通用）
#include <iostream>
#include <queue>
using namespace std;
struct Node
{
int x, y;
Node( int a= 0, int b= 0 ):
x(a), y(b) {}
};
bool operator<( Node a, Node b )
{
if( a.x== b.x ) return a.y> b.y;
return a.x> b.x;
}
int main()
{
priority_queue<Node> q;
for( int i= 0; i< 10; ++i )
q.push( Node( rand(), rand() ) );
while( !q.empty() ){
cout << q.top().x << ' ' << q.top().y << endl;
q.pop();
}
return 0;
}
在结构体内
struct node
{
friend bool operator< (node n1, node n2)
{
return n1.priority < n2.priority;
}
int priority;
int value;
};
2.用comp代替算子（greater，less），在comp里重载括号
如
#include <cstdio>
#include <queue>
using namespace std;
struct Node
{
int x,y;
Node(int a = 0,int b = 0):x(a),y(b){} //相当于makepair，方便push
};
struct cmp
{
bool operator()(Node a,Node b){
if (a.x == b.x)
return a.y>b.y;
return a.x>b.x;
}
};
int main(){
priority_queue<Node,vector<Node>,cmp > q;
for (int i = 0; i < 10;++i)
{
q.push(Node(rand(),rand()));
}
while (!q.empty())
{
cout<<q.top().x<<" "<<q.top().y<<endl;
q.pop();
}
}
4.map
1、map简介
map是一类关联式容器，它是模板类。关联的本质在于元素的值与某个特定的键相关联，而并非通过元素在数组中的位置类获取。它的特点是增加和删除节点对迭代器的影响很小，除了操作节点，对其他的节点都没有什么影响。对于迭代器来说，不可以修改键值，只能修改其对应的实值。
2、map的功能
1、自动建立Key － value的对应。key 和 value可以是任意你需要的类型，但是需要注意的是对于key的类型，唯一的约束就是必须支持<操作符。
2、根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。
3、快速插入Key – Value 记录。
4、快速删除记录
5、根据Key 修改value记录。
6、遍历所有记录。
3、map的定义
使用map得包含map类所在的头文件：#include <map>
map对象是模板类，需要关键字和存储对象两个模板参数，基本的定义模式如下：
map<int, string> ma;
这样就定义了一个以int为键，值为string的map对象ma。
4、在map中添加元素
使用下标操作符获取元素，然后给元素赋值
map<string, int> word_count; // 定义了一个空的map对象word_count;
word_count[“hello world”] = 1;
程序说明：
1.在word_count中查找键为hello world的元素，没有找到.
2.将一个新的键-值对插入到word_count中，他的键是const string类型的对象，保存hello world。而他的值则采用直初始化，这就意味着在本例中指为0.
3.将这个新的键-值对插入到word_count中
4.读取新插入的元素，并将它的值赋为1.
使用下标访问map与使用下标访问数组或者vector的行为是截然不同的：使用下标访问不存在的元素将导致在map容器中添加一个新的元素，他的键即为该下标值。
5、查找并获取map中的元素
使用下标获取元素存在一个很危险的副作用：如果该键不在map容器中，那么下标操作会插入一个具有该键的新元素。（重要）
因此引入map对象的查询操作：
map.count(k) : 返回map中键k的出现次数(对于map而言，由于一个key对应一个value，因此返回只有0和1，因此可以用此函数判断k是否在map中)
map.find(k) : 返回map中指向键k的迭代器，如果不存在键k，则返回超出末端迭代器。
所以获取方法就是先查询一下，如果存在再获取值，要不就会创建新的元素
int occurs = 0;
if( word_count.cout("foobar") )
occurs = word_count["foobar"];
int occurs = 0;
map<string, int>::iterator it = word_count.find("foobar");
if( it != word_count.end() )
occurs = it ->second;
6、从map中删除元素
移除某个map中某个条目用erase()
该成员方法的定义如下
iterator erase(iterator it); //通过一个条目对象删除
iterator erase(iterator first, iterator last); //删除一个范围
size_type erase(const Key& key); //通过关键字删除
clear()就相当于 enumMap.erase(enumMap.begin(), enumMap.end());
7、 map对象的迭代遍历
与其他容器一样，map同样提供begin和end运算，以生成用于遍历整个容器的迭代器。
一个样例程序
转自http://www.cnblogs.com/JCSU/articles/1996876.html（懒得写了）
/************************************************************************
*
* Map的特点: 1、存储Key-value对
* 2、支持快速查找，查找的复杂度基本是Log(N)
* 3、快速插入，快速删除，快速修改记
*
/************************************************************************/
#include <stdio.h>
#pragma warning(disable:4786)
#include <string>
#include <map> //包含头文件
using namespace std;
//输出map中的记录
#define PRINTMAP(iterSuffix, mapName)\
{\
PRJ_MAP_STRING2INT_WORDREC::iterator iter##iterSuffix = mapName##.begin();\
for (; iter##iterSuffix != mapName##.end(); ++iter##iterSuffix)\
{\
printf("\"%s\" -> total: %d\n", iter##iterSuffix->first.c_str(), iter##iterSuffix->second);\
}\
printf("\n");\
}
/************************************************************************
* 数据类型定义
/************************************************************************/
typedef map<string, int> PRJ_MAP_STRING2INT_WORDREC;//定义map类型的别名
/************************************************************************/
/* 全局函数
/************************************************************************/
void main()
{
map<string, int> mapWordRecPrep; /* 定义map类型的变量 */
PRJ_MAP_STRING2INT_WORDREC mapWordRecVerb; /* 用别名定义map类型的变量 */
//插入记录
mapWordRecPrep["the"] = 100; /* 数组方式 */
mapWordRecPrep["so"] = 50;
mapWordRecVerb["find"] = 1;
mapWordRecVerb["seen"] = 2;
mapWordRecVerb["jump"] = 3;
mapWordRecVerb["swim"] = 4;
mapWordRecVerb.insert(map<string, int>::value_type("look", 5)); /* value_type方式 */
mapWordRecVerb.insert(pair<string, int>("walk", 6)); /* pair方式 */
/* value_type和pair方式不出现覆盖现象 */
printf("Insert method: value_type\n");
pair<map<string, int>::iterator, bool> inserted;
inserted = mapWordRecVerb.insert(map<string, int>::value_type("walk", 7));
printf("%s\n", true == inserted.second ? "Insert success!" : "Insert failed!");
PRINTMAP(Ver, mapWordRecVerb);
/* 数组方式出现覆盖现象*/
printf("Insert method: array\n");
mapWordRecVerb["walk"] = 7;
PRINTMAP(Ver, mapWordRecVerb);
//查找记录
map<string, int>::iterator iter = mapWordRecPrep.find("so");
printf("%s\n", iter == mapWordRecPrep.end() ? "Not find!" : "Find!");
//删除记录
map<string, int>::iterator iterV = mapWordRecVerb.find("seen");
if (iterV != mapWordRecVerb.end())
{
mapWordRecVerb.erase(iterV); /* 迭代器方式删除 */
printf("\nDelete word \"seen\" done!\n");
PRINTMAP(Verb, mapWordRecVerb);
}
int n = mapWordRecVerb.erase("swim"); /* 关键字方式删除 */
printf("\nDelete word \"swim\" done!\n");
PRINTMAP(Verb, mapWordRecVerb);
mapWordRecVerb.erase(mapWordRecVerb.begin(), mapWordRecVerb.end()); /* 成片删除 */
printf("\nDelete all word done!\n");
PRINTMAP(Verb, mapWordRecVerb);
//map的其它函数
if (mapWordRecVerb.empty() && 0 == mapWordRecVerb.size()) /* 判断map是否为空 */
{
printf("mapWordRecVerb is empty!\n\n");
}
PRINTMAP(Pre, mapWordRecPrep)
mapWordRecPrep.clear(); /* 清空map */
PRINTMAP(Pre, mapWordRecPrep)
if (mapWordRecPrep.empty() && 0 == mapWordRecPrep.size())
{
printf("mapWordRecPrep is empty!\n\n");
}
}
输出结果：
Insert method: value_type
Insert failed!
“find” -> total: 1
“jump” -> total: 3
“look” -> total: 5
“seen” -> total: 2
“swim” -> total: 4
“walk” -> total: 6
Insert method: array
“find” -> total: 1
“jump” -> total: 3
“look” -> total: 5
“seen” -> total: 2
“swim” -> total: 4
“walk” -> total: 7
Find!
Delete word “seen” done!
“find” -> total: 1
“jump” -> total: 3
“look” -> total: 5
“swim” -> total: 4
“walk” -> total: 7
Delete word “swim” done!
“find” -> total: 1
“jump” -> total: 3
“look” -> total: 5
“walk” -> total: 7
Delete all word done!
mapWordRecVerb is empty!
“so” -> total: 50
“the” -> total: 100
mapWordRecPrep is empty!
未完待续