优先队列

1.可以插入一个数值。 2.取出最小/大数值，获得数值，并且删除。 头文件&说明 #include<queue>usingnamespacestd;

复杂度：对每个元素，插入和删除只是修改了堆顶和堆底，不需要所有的都排序，只是需要再次调整好堆，因此时间复杂度都是O(logN)

常用格式：

priority_queue <node> q; //node是一个结构体 //结构体里重载了‘<’小于符号 priority_queue <int,vector<int>,greater<int> > q; //不需要#include<vector>头文件 //注意后面两个“>”不要写在一起，“>>”是右移运算符 priority_queue <int,vector<int>,less<int> >q;  //less是从大到小，greater是从小到大

基本操作（以q为例）：

q.size();//返回q里元素个数 q.empty();//返回q是否为空，空则返回1，否则返回0 q.push(k);//在q的末尾插入k q.pop();//删掉q的第一个元素 q.top();//返回q的第一个元素 q.back();//返回q的末尾元素

默认的优先队列（结构体，重载小于）

struct node { int x,y; bool operator < (const node & a) const { return x<a.x; } };

这个node结构体有两个成员，x和y，它的小于规则是x小者小， 它是按照重载后的小于规则，从大到小排序的。参考：http://blog.csdn.net/c20182030/article/details/70757660

练题 :  PKU3253  POJ2431

 二叉搜索树

可以进行如下操作的数据结构：1.插入一个数值    2.查询是否包含某个数值    3.删除某个数值

操作的复杂度：不论哪一种操作，其复杂度均与树的高度有关，故设其有n个元素，则平均每次操作需要O(logn)时间复杂度。

在STL中的操作：set（使用二叉搜索树维护的集合的容器）    map（维护键和键对应的数值的容器）

SET

set，顾名思义是“集合”的意思，在set中元素都是唯一的，而且默认情况下会对元素自动进行升序排列

set容器的常用操作

使用时注意包含头文件<set> std::set and std::multiset associative containers s.begin() 　返回set容器的第一个元素，迭代器指向二叉搜索树最左边的结点 s.end() 　　　　 返回set容器的最后一个元素，迭代器指向二叉搜索树最右边的结点 s.clear() 删除set容器中的所有的元素 s.empty() 　　　 判断set容器是否为空 s.insert() 插入一个元素 s.erase() 删除一个元素，参数可为元素或指定位置的迭代器，功能不同 s.size() 　　　　返回当前set容器中的元素个数

set容器的创建

#include <iostream> #include <set> #include <functional> using namespace std; set<int> s; int main(){ set<int > seta; //默认是小于比较器less<int>的set set<int, greater<int> > setb; //创建一个带大于比较器的set，需包含头文件functional int a[5] = {1,2,3,4,5}; set<int > setc(a,a+5); //数组a初始化一个set； set<int > setd(setc.begin(),setc.end()); //setc初始化一个set //上述两例均为区间初始化 set<int > sete(setd); //拷贝构造创建set return 0; }

删除过程

如何删除某位置元素：http://blog.csdn.net/qq_36509464/article/details/52994182

查找

s.find() 查找一个元素，如果容器中不存在该元素，返回值等于s.end()

STL常用的其他操作

s.lower_bound() 返回第一个大于或等于给定关键值的元素 s.upper_bound() 返回第一个大于给定关键值的元素 s.equal_range() 返回一对定位器，分别表示 第一个大于或等于给定关键值的元素 和 第一个大于给定关键值 的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于 s.end() 自定义比较函数 #include <iostream> #include <set> #include <functional> using namespace std; struct cmp{ bool operator () (const int &a, const int &b){ return a > b; } }; set<int, cmp>s; //自定义排序函数构造set void setprint(int cnt){ cout << "Test output :" << cnt << ":" << endl; for(set<int,cmp>::iterator it = s.begin(); it!= s.end(); it++) cout << *it << " "; puts(""); return ; } int main(){ s.insert(1); s.insert(2); s.insert(6); setprint(1);                // 6 2 1 return 0; } 至于求并、交、差、对称差等操作，暂不细说，使用时要包含头文件”algorithm”。 

可以存放重复键值的则为multiset，还有此外还有unordered_set和unordered_multiset，为set和multiset的无序版，使用时要包含头文件”unordered_set”。

MAP

头文件：#include <map>

map技术的原理：将键值和对应数据封装成一个结构对象，并将此对象插入到红黑树，完成一个元素的添加。同时，也要提供一个仅使用键值进行比较的函数对象，将它传递给红黑树。由此，就可利用红黑树的操作，将map元素数据插入到二叉树中的正确位置，也可以根据键值进行元素的删除和检索。map提供了一对一的数据检索功能，每个键值只能在map中出现一次。

最基本的map的构造方法：map<int, string> mapStudent;

2.数据的插入

在构造map容器后，我们就可以往里面插入数据了。这里讲两种简单实用的插入数据的方法：

第一种：用insert函数插入pair数据，下面举例说明(以下代码虽然是随手写的，应该可以在VC和GCC下编译通过，大家可以运行下看什么效果，在VC下请加入这条语句，屏蔽4786警告  ＃pragma warning (disable:4786) )

#include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent.insert(pair<int, string>(1, “student_one”)); mapStudent.insert(pair<int, string>(2, “student_two”)); mapStudent.insert(pair<int, string>(3, “student_three”)); map<int, string>::iterator iter;                               //::iterator是stl库中的迭代器 for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++) { Cout<<iter->first<<” ”<<iter->second<<end; } }

第二种. 用数组方式插入数据

#include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent[1] = “student_one”; mapStudent[2] = “student_two”; mapStudent[3] = “student_three”; map<int, string>::iterator iter; for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++) { Cout<<iter->first<<” ”<<iter->second<<end; } }

两种插入方法的不同：用insert函数插入数据，在数据的插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是插入数据不了的，但是用数组方式就不同了，它可以覆盖以前该关键字对应的值。

3.map中数据的查找

下面介绍三种用以在map中查找数据的方法

第一种：用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了。

第二种：用find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器

#include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent.insert(pair<int, string>(1, “student_one”)); mapStudent.insert(pair<int, string>(2, “student_two”)); mapStudent.insert(pair<int, string>(3, “student_three”)); map<int, string>::iterator iter; iter = mapStudent.find(1); if(iter != mapStudent.end()) { Cout<<”Find, the value is ”<<iter->second<<endl; } Else { Cout<<”Do not Find”<<endl; } }

第三种：使用lower_bound()和upper_bound函数()所分别返回的值来确定数据是否存在。

lower_bound函数用法，这个函数用来返回要查找关键字的下界(是一个迭代器)

upper_bound函数用法，这个函数用来返回要查找关键字的上界(是一个迭代器)

"前闭后开"是STL容器的设计原则，lower_bound(v)可以理解为[v, inf)范围内的第一个元素。而upper_bound(v)则可以理解为(-inf, v]的最后一个元素。

所以[lower_bound(v), upper_bound(v) )这个前闭后开区间恰好就是所有的v构成的区间。

4.数据的清空与判空

清空map中的数据可以用clear()函数，判定map中是否有数据可以用empty()函数，它返回true则说明是空map

5.数据的删除

这里要用到eraser函数，注意：STL中的区间均为前闭后开的区间

#include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent.insert(pair<int, string>(1, “student_one”)); mapStudent.insert(pair<int, string>(2, “student_two”)); mapStudent.insert(pair<int, string>(3, “student_three”)); //如果你要演示输出效果，请选择以下的一种，你看到的效果会比较好 //如果要删除1,用迭代器删除 map<int, string>::iterator iter; iter = mapStudent.find(1); mapStudent.erase(iter); //如果要删除1，用关键字删除 Int n = mapStudent.erase(1);//如果删除了会返回1，否则返回0 //用迭代器，成片的删除 //一下代码把整个map清空 mapStudent.earse(mapStudent.begin(), mapStudent.end()); //成片删除要注意的是，也是STL的特性，删除区间是一个前闭后开的集合 //自个加上遍历代码，打印输出吧 }

6.其他一些函数用法

这里有swap,key_comp,value_comp,get_allocator等函数，感觉到这些函数在编程用的不是很多，略过不表，有兴趣的话可以自个研究

     7.关于排序

       这里要讲的是一点比较高深的用法了,排序问题，STL中默认是采用小于号来排序的，以上代码在排序上是不存在任何问题的，因为上面的关键字是int型，它本身支持小于号运算，在一些特殊情况，比如关键字是一个结构体，涉及到排序就会出现问题，因为它没有小于号操作，insert等函数在编译的时候过不去，下面给出两个方法解决这个问题

第一种：重载小于号，如下： Typedef struct tagStudentInfo { Int nID; String strName; Bool operator < (tagStudentInfo const& _A) const { //这个函数指定排序策略，按nID排序，如果nID相等的话，按strName排序 If(nID < _A.nID) return true; If(nID == _A.nID) return strName.compare(_A.strName) < 0; Return false; } }StudentInfo, *PStudentInfo; //学生信息 第二种：仿函数的应用，这个时候结构体中没有直接的小于号重载，程序说明 #include <map> #include <string> Using namespace std; Typedef struct tagStudentInfo { Int nID; String strName; }StudentInfo, *PStudentInfo; //学生信息 Classs sort { Public: Bool operator() (StudentInfo const &_A, StudentInfo const &_B) const { If(_A.nID < _B.nID) return true; If(_A.nID == _B.nID) return _A.strName.compare(_B.strName) < 0; Return false; } }; Int main() { //用学生信息映射分数 Map<StudentInfo, int, sort>mapStudent; StudentInfo studentInfo; studentInfo.nID = 1; studentInfo.strName = “student_one”; mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90)); studentInfo.nID = 2; studentInfo.strName = “student_two”; mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80)); }

8.outro

由于STL是一个统一的整体，map的很多用法都和STL中其它的东西结合在一起，比如在排序上，这里默认用的是小于号，即less<>，如果要从大到小排序呢，这里涉及到的东西很多，在此无法一一加以说明。

还要说明的是，map中由于它内部有序，由红黑树保证，因此很多函数执行的时间复杂度都是log₂N的，如果用map函数可以实现的功能，而STL  Algorithm也可以完成该功能，建议用map自带函数，效率高一些。

另外在空间方面：由于map的每个数据对应红黑树上的一个节点，这个节点在不保存你的数据时，是占用16个字节的，一个父节点指针，左右孩子指针，还有一个枚举值（标示红黑的，相当于平衡二叉树中的平衡因子）。

LIST(链表)

由于list是链式存储，因此不能随机访问，也即不支持索引访问。头文件#include<list>声明一个int型的list：list<int> a；

1.list的构造函数： list<int>a{1,2,3} list<int>a(n) //声明一个n个元素的列表，每个元素都是0 list<int>a(n, m) //声明一个n个元素的列表，每个元素都是m list<int>a(first, last) //声明一个列表，其元素的初始值来源于由区间所指定的序列中的元素，first和last是迭代器 2.begin()与end() 通过调用list容器的成员函数begin()得到一个指向容器起始位置的iterator，可以调用list容器的end()函数来得到list末端下一位置。

3.push_back()和push_front()使用push_back()是从list的末端插入，而push_front()是从list的头端插入。

4.empty()

判空

5.reisize()

调用resize(n)将list的长度改为只容纳n个元素，超出的元素将被删除。如果n比list原来的长度长，那么默认超出的部分元素置为0。也可以用resize(n, m)的方式将超出的部分赋值为m。

list<int>b{1, 2, 3, 4}; b.resize(2); list中输出元素：1,2 list<int>b{1, 2, 3, 4}; b.resize(6); list中输出元素：1,2,3,4,0,0 list<int>b{1, 2, 3, 4}; b.resize(6,9); list中输出元素：1,2,3,4,9,9

6.clear()    7.front()和back()    8.pop_back()和pop_front()

9.assign()

有两种使用情况： (1) a.assign(n,val)将a所有的元素替换为n个val元素.

list<int>b{1,2,3,4,5}; b.assign(5,10);    //b中的元素变为10，10，10，10，10(2)a.assign(b.begin(),b.end()) list<int>a{6,7,8,9}; list<int>b{1,2,3,4,5}; b.assign(a.begin(),a.end()); 10.swap 交换两个链表：swap(a,b)     a.swap(b)

11.reserve()实现逆置     

12.merge()

c1.merge(c2)    合并两个有序的链使其有序放到c1之中 并释放c2

c1.merge(c2,comp)      合并2个有序的链表并使之按照自定义规则排序之后从新放到c1中,释放c2。

a.merge(b) 调用结束后b变为空，a中元素包含原来a和b的元素。

当源list均有序时，得到的list仍是有序的。

当源list无序时，得到的list不能保证有序，之所以这样说是因为，当list1的前两个元素即表现出无序时，合并后的结果将是直接把list2接到list1的后面。

13.splice()

list::splice实现list拼接的功能。将源list的内容部分或全部元素删除，拼插入到目的list

a.splice(a.begin(),b)    将b连接到a的begin位置，并释放c2

a.splice(a.begin(),b,b.begin() )    将b的begin位置的元素连接到a的begin位置的元素，并释放b的begin位置的元素

a.splice(a.begin(), b,b.begin(),b.end() ) 将b的[begin,end)位置的元素连接到a.begin()位置的元素，并释放b的[begin,end)位置的元素

14.insert()

在指定位置插入一个或多个元素

a.insert(a.begin(),100); //在a的开始位置（即头部）插入100 a.insert(a.begin(),2, 100); //在a的开始位置插入2个100 a.insert(a.begin(),b.begin(), b.end());//在a的开始位置插入b从开始到结束的所有位置的元素

15.erase()

删除一个或一个区域的元素 a.remove(a.begin(),a.end() )

16.remove()

删除所有指定值的元素 a.remove(x);

remove_if(comp)    删除满足条件的元素，参数为自定义的回调函数  

class single_digit{ public: bool operator()(const int& value){ return (value<10); } }; int main(){ list<int> a{6,7,4,9,7,10}; a.remove_if(single_digit()); list<int>::iterator it = a.begin(); while(it != a.end()){ cout<<*it<<" "; it++; } return 0; }                                //输出为0