C++常用标准模板库

vector,set,string,map,queue,priority_queue,stack,pair,bitset,algorithm
1. vector(动态数组)
vector 是向量类型，它可以容纳许多类型的数据，如若干个整数，所以称其为容器。vector 是C++ STL的一个重要成员，使用它时需要包含头文件：

#include<vector>;

一、vector 的初始化：可以有五种方式,举例说明如下：

    (1) vector<int> a(10); //定义了10个整型元素的向量（尖括号中为元素类型名，它可以是任何合法的数据类型），但没有给出初值，其值是不确定的。
   （2）vector<int> a(10,1); //定义了10个整型元素的向量,且给出每个元素的初值为1
   （3）vector<int> a(b); //用b向量来创建a向量，整体复制性赋值
   （4）vector<int> a(b.begin(),b.begin+3); //定义了a值为b中第0个到第2个（共3个）元素
   （5）int b[7]={1,2,3,4,5,9,8};
        vector<int> a(b,b+7); //从数组中获得初值

二、vector对象的几个重要操作，举例说明如下：

    （1）a.assign(b.begin(), b.begin()+3); //b为向量，将b的0~2个元素构成的向量赋给a
    （2）a.assign(4,2); //是a只含4个元素，且每个元素为2
    （3）a.back(); //返回a的最后一个元素
    （4）a.front(); //返回a的第一个元素
    （5）a[i]; //返回a的第i个元素，当且仅当a[i]存在2013-12-07
    （6）a.clear(); //清空a中的元素
    （7）a.empty(); //判断a是否为空，空则返回ture,不空则返回false
    （8）a.pop_back(); //删除a向量的最后一个元素
    （9）a.erase(a.begin()+1,a.begin()+3); //删除a中第1个（从第0个算起）到第2个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+         3（不包括它）
    （10）a.push_back(5); //在a的最后一个向量后插入一个元素，其值为5
    （11）a.insert(a.begin()+1,5); //在a的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4
    （12）a.insert(a.begin()+1,3,5); //在a的第1个元素（从第0个算起）的位置插入3个数，其值都为5
    （13）a.insert(a.begin()+1,b+3,b+6); //b为数组，在a的第1个元素（从第0个算起）的位置插入b的第3个元素到第5个元素（不包括b+6），如b为1,2,3,4,5,9,8         ，插入元素后为1,4,5,9,2,3,4,5,9,8
    （14）a.size(); //返回a中元素的个数；
    （15）a.capacity(); //返回a在内存中总共可以容纳的元素个数
    （16）a.resize(10); //将a的现有元素个数调至10个，多则删，少则补，其值随机
    （17）a.resize(10,2); //将a的现有元素个数调至10个，多则删，少则补，其值为2
    （18）a.reserve(100); //将a的容量（capacity）扩充至100，也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才         显得有意义，因为这将避免内存多次容量扩充操作（当a的容量不足时电脑会自动扩容，当然这必然降低性能） 
    （19）a.swap(b); //b为向量，将a中的元素和b中的元素进行整体性交换
    （20）a==b; //b为向量，向量的比较操作还有!=,>=,<=,>,<

三、顺序访问vector的几种方式，举例说明如下：
（1）向向量a中添加元素

  vector<int> a;
 for(int i=0;i<10;i++)
 a.push_back(i);

2、也可以从数组中选择元素向向量中添加

int a[6]={1,2,3,4,5,6};
vector<int> b；
for(int i=1;i<=4;i++)
b.push_back(a[i]);

3、也可以从现有向量中选择元素向向量中添加

int a[6]={1,2,3,4,5,6};
vector<int> b;
vector<int> c(a,a+4);
for(vector<int>::iterator it=c.begin();it<c.end();it++)
b.push_back(*it);

4、也可以从文件中读取元素向向量中添加

ifstream in("data.txt");
vector<int> a;
for(int i; in>>i)
    a.push_back(i);

5、【误区】

vector<int> a;
for(int i=0;i<10;i++)
    a[i]=i;
//这种做法以及类似的做法都是错误的。下标只能用于获取已存在的元素，而现在的a[i]还是空的对象

（2）从向量中读取元素
1、通过下标方式读取

int a[6]={1,2,3,4,5,6};
vector<int> b(a,a+4);
for(int i=0;i<=b.size()-1;i++)
    cout<<b[i]<<" ";

2、通过遍历器方式读取

int a[6]={1,2,3,4,5,6};
vector<int> b(a,a+4);
for(vector<int>::iterator it=b.begin();it!=b.end();it++)
    cout<<*it<<" ";

四、几种重要的算法，使用时需要包含头文件：

#include<algorithm>
（1）sort(a.begin(),a.end()); //对a中的从a.begin()（包括它）到a.end()（不包括它）的元素进行从小到大排列
（2）reverse(a.begin(),a.end()); //对a中的从a.begin()（包括它）到a.end()（不包括它）的元素倒置，但不排列，如a中元素为1,3,2,4,倒置后为4,2,3,1
（3）copy(a.begin(),a.end(),b.begin()+1); //把a中的从a.begin()（包括它）到a.end()（不包括它）的元素复制到b中，从b.begin()+1的位置（包括它）开        始复制，覆盖掉原有元素
（4）find(a.begin(),a.end(),10); //在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，若存在返回其在向量中的位置

1. set
   set翻译为集合，是一个内部自动有序且不含重复元素的容器。默认是升序。底层采用红黑树实现。
   set的定义：set<’typename’> s，降序的定义方式为set<typename,greater<typename>> s。typename可以是任意类型包括STL容器。Set数组的定义方式为，set<typename> s[size].s[0]…s[size-1]都是set类型。迭代器的定义方式set<typename>::iterator it
   set容器内元素的访问：set只能通过迭代器(iterator)访问。
   set常用函数
   （1） insert(x)可将x插入set容器中，并且自动递增排序和去重，时间复杂度O(logN),其中N是set中元素的数量。
   （2） find（x）返回set中对应值为x的迭代器，时间复杂度O(logN),N为set内元素的个数。
   （3） erase（），erase有两种用法：删除单个元素，删除一个区间内的所有元素。
   删除单个元素有两种方式，erase(it)删除该迭代器对应的元素，时间复杂度O(1),erase(x)删除该元素,时间复杂度O(logN)
   删除一个区间的元素，erase(st,ed),删除区间[st,ed)内的元素，时间复杂度O(ed-st)
   （4） size(),用来获得set内元素的个数，时间复杂度O(1)
   （5） clear(),用来清空set中所有元素，复杂度O(N),其中N为set内元素的个数。
   （6） count(x),返回set中x的数量

set<int> st ;
    st.insert(3) ;
    st.insert(3) ;
    st.insert(3) ;
    st.insert(1) ;
    st.insert(4) ;
    st.insert(4) ;
    st.insert(4) ;
    st.insert(4) ;
    st.insert(2) ;
    st.insert(2) ;
    cout << st.size() << endl ;
    cout << st.count(4) << endl ;//set去重了，返回只能是0或1
    cout << *st.find(1) << endl ;
    st.erase(1) ;
    st.erase(st.begin(),st.find(4)) ;
    for(auto ele : st) cout << ele << ' ' ;
    puts("") ;
    st.clear() ;
    cout << st.size() << endl ;

set的常见用途：
set最主要的作用是自动去重并且升序排序，因此碰到需要去重但不方便开数组的
时候，可以尝试用set解决。
注意：set中的元素是唯一的，如果需要处理不唯一的情况可以使用multiset。C++11中还增加了unordered_ set,以散列代替set内部的红黑树，unordered_set可以处理需要去重但是不需要排序的情况，速度比set快得多。Multiset和unordered_set的定义和常用函数和set类似。
3.string
C++STL中加入string类型，对字符串常用需求功能进行了封装，使得操作起来更方便，且不易出错。如果要使用string,需要添加string头文件，即#include<string>,注意string.h和string是不一样的头文件。除此之外要想使用string，还要在头文件下面加上一句“using namespace std”，这样就可以在代码中使用string了。
string的定义：
定义方式与基本数据类型相同，只需要在string后面跟上变量名称即可。
eg. string str;如果需要初始化，可以直接给string类型的变量赋值，string str = “hello”。
String中内容的访问：
(1) 通过下标访问，可以直接像字符数组那样去访问string

 string str = "hello" ;
    for(int i=0;i<str.size();i++){
        printf("%c",str[i]) ;
    } 
输出结果:hello

如果用string读入和输出字符串一般只能用cin和cout，使用printf输出也是可以的，但是要先将string装换为字符数组进行输出

string str ;
cin >> str ;
cout << str << endl ;
printf("%s\n",str.c_str()) ;
return 0 ;
输入：hello
输出：hello
hello

(2) 通过迭代器访问，string的访问一般采用第一种方式，但是string有很多函数要求以迭代器为参数。string迭代器的定义方式为string::iterator it，可以使用*it来访问string中的每一位。String迭代器的使用方法与其他容器的迭代器的使用方法类似，string和vector一样，支持直接对迭代器进行加减某个数字。
示例：

    string str = "hello" ;
    string::iterator it  ;
    for(it = str.begin();it!=str.end();it++){
        cout << *it ;
    }
    it = str.begin() ;
    cout << endl ;
        cout << *(it+1) << "<--->" << str[1] << endl ;
结果： hello
e<--->e

string常用函数：
string提供的函数有很多，这里紧介绍常用的string函数
（1） operator+=拼接
这是string的加法，可以将两个string直接拼接起来。

string str1 = "hello" ;
    string str2 = " world" ;
    cout << str1 + str2 << endl ;
结果：hello world

（2） compare operator比较
两个string类型可以直接使用==,!=,<,<=,>,>=比较大小，比较规则是字典序。

string str1 = "aa" ;
    string str2 = "ab" ;
    string str3 = "abc" ;
    if(str1 != str2){
        cout << "not same" << endl ;
    }else{
        cout << "same" << endl ;
    } 
    if(str3>str2){
        cout << "str3>str2" << endl ;
    }
结果：not same
str3>str2

（3） length()/size()取得大小
length()返回string的长度，即string存放的字符数，时间复杂度O(1)。size()和length()基本相同。

string str1 = "hello" ;
    cout << str1.size() << ' ' << str1.length() << endl ;
结果：5 5

（4） insert（）插入（原字符串不会被覆盖）
insert()函数有很多种写法，这里列出几个常用的写法，时间复杂度度O(N)。
insert(pos,string)，在pos号位置插入string。
insert(it,it1,it2)，it为原字符串欲插入的位置，it2和it3为待插字符串的首尾迭代器，用来表示串[it1,it2)将被插在it的位置上。

string str1 = "hello world" ;
    string str2 = "Maric" ;
    str1.insert(str1.begin()+5,str2.begin(),str2.end()) ;
    cout << str1 << endl ;
    str2.insert(5,"hello") ;
    cout << str2 << endl ;
结果：helloMaric world
Marichello

（5） erase()删除
erase()有两种用法，删除单个元素，上出一个区间内所有元素。时间复杂度O(N)。
a． erase(it)用于删除单个元素，it为需要删除的元素的迭代器。
b. 删除一个区间的元素有两种方法：
第一种是erase(st,ed),st，ed为string迭代器，表示删除区间[st,ed)之间的元素。
第二种是erase(pos,len)，其中pos为需要删除的起始位置，len为删除的字符个数。

string str1 = "hello world" ;
    str1.erase(str1.begin()) ;
    cout << str1 << endl ;
    str1.erase(str1.begin()+5,str1.end()) ;
    cout << str1 << endl ;
    str1.erase(1,2) ;
    cout << str1 << endl ;
结果：ello world
ello
eo

（6） clear()清空
clear()函数用来清空string中的数据，时间复杂度O(1)。

string str1 = "hello world" ;
    cout << str1.length() << endl ;
    str1.clear() ;
    cout << str1.size() << endl ;
结果：11
      0

（7） substr()截取子串
substr(pos,len)返回的是以pos位开始长度为len的子串，时间复杂度O(len)。

string str1 = "hello world" ;
        cout << str1.substr(6,5) << endl ;
结果：world

（8） string::npos
npos 是一个常数，用来表示不存在的位置，类型一般是std::container_type::size_type 许多容器都提供这个东西。取值由具体实现决定，一般是-1，但是由于是unsigned_int类型，也可以认为是unsigned_int类型的最大值，这样做，就不会存在移植的问题了。
不建议将find的返回值作为是否匹配的依据。最好使用示例的使用方式。npos主要是和find()函数搭配使用，用以作为find()函数失配时的返回值，举个例子具体解释一下：

if (a.find(b) != string::npos) {
    cout << "Yes!" << endl;
} else {
    cout << "No!" << endl;
}

（9） find()查找
str.find(str1),当str1是str的子串时，返回其在str中第一次出现的位置。如果str1不是str的子串，那么返回string::npos
str.find(str1,pos),从str的pos号位开始匹配str1,返回值与上面的相同，时间复杂度为O(nm),其中n和m分别为str和str1的长度。

string str1 = "hello world" ;
    string str2 = "world" ;
    if(str1.find(str2) != string::npos){
        cout << str1.find(str2) << endl ;
cout << str1.find(str2,3) << endl ;
    }else{
        cout << "match failure" << endl ;
    }
结果：6
         6

小结：find函数的返回值是整数，假如字符串存在包含关系，其返回值必定不等于npos，但如果字符串不存在包含关系，那么返回值就一定是npos。
（10） replace()
str.replace(pos,len,str1),把str从pos号位开始，长度为len的子串替换为str1。
str.replace(it1,it2,str1)把str的迭代器[it1,it2)替换为str1

string str1 = "hello world" ;
    string str2 = "kangkang" ;
    cout << str1.replace(6,5,str2) << endl ;
    cout << str1.replace(str1.begin()+6,str1.end(),str2) << endl ;
结果：hello kangkang
hello kangkang

1. map
   map翻译成映射，map可以将任何基本类型（包括STL容器）映射到任何基本类。（包括STL容器）。如要使用map，需要添加map头文件，并在头文件底下加上“using namespace std”,这样就可以在代码中使用map了。
   map的定义，map[HTML_REMOVED] mp;map和其他STL容器的定义上有点不同，因为map需要确定映射前类型（键key）和映射后类型（值value）,map存储的数据类型是一对K-V结构的数据。如果map是字符串到整型的映射，必须使用string而不能使用char数组。
   map的访问，map一般有两种访问方式，通过“下标”访问或者通过迭代器访问。
   （1） 通过“下标”访问，和普通数组的访问方式一样。比如，定义了一个map[HTML_REMOVED] mp;的map，可以使用mp[“hello”] = 8的方式向map中添加数据，用mp[“hello”]访问map中键为“hello”的值。map中的键是唯一的，可以观察下面代码的输出。

unordered_map<string,int> um ;
    um["hello"] = 8 ;
    um["hello"] = 100 ;
    cout << um["hello"] << endl ;
输出：100

（2） 通过迭代器访问，与其他STL迭代器有点不同，由于map的数据类型是K-V结构，因此迭代器包含了这两方面的数据。map迭代器的定义方式为map[HTML_REMOVED]::iterator it;可以通过it->first来访问键，it->second来访问值。观察下面的代码，

map<string,int> mp ;
    mp["hello"] = 8 ;
    mp["hello"] = 100 ;
    mp["aloha"] = 666 ;
    mp["good"] = 777 ;
    for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++){
        cout << it->first << ' ' << it->second << endl ;
    }
输出结果：aloha 666
good 777
hello 100

    观察输出结果，很有意思的是map按照键值从小到大排序了，如果是字符串，则按照字典序排序。map是采用红黑树来实现的。
    map的常用函数：

（1） find（key），返回键为key的映射的迭代器，时间复杂度为O(logN)，N为map中映射的个数。

map<string,int> mp ;
    mp["hello"] = 8 ;
    mp["hello"] = 100 ;
    mp["aloha"] = 666 ;
    mp["good"] = 777 ;
    auto it = mp.find("good") ;
    cout << it->first << ' ' << it->second << endl ;
输出结果：good 777

（2） erase(),erase()有两种用法：删除单个元素和删除一个区间内的元素。
a． 删除单个元素，删除单个元素也有两种方法
mp.erase(it)，it为需要删除的元素的迭代器，时间复杂度O(1)。

map<string,int> mp ;
    mp["hello"] = 8 ;
    mp["hello"] = 100 ;
    mp["aloha"] = 666 ;
    mp["good"] = 777 ;
    mp.erase(mp.find("good"));
    for(auto ele : mp){
        cout << ele.first << ' ' << ele.second << endl ;
    }
输出结果：aloha 666
hello 100

mp.erase(key)，key为欲删除的映射的键。时间复杂度O(logN)。N为map中元素的个数。

map<string,int> mp ;
    mp["hello"] = 8 ;
    mp["hello"] = 100 ;
    mp["aloha"] = 666 ;
    mp["good"] = 777 ;
    mp.erase("good");
    for(auto ele : mp){
        cout << ele.first << ' ' << ele.second << endl ;
    }

输出结果：aloha 666
hello 100

            b. 删除一个区间的元素，这里只能用迭代器删除，erase(st,ed),表示删除[st,ed)区间内的元素。

map<string,int> mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
mp.erase(mp.find("good"),mp.find("hello"));
for(auto ele : mp){
cout << ele.first << ' ' << ele.second << endl ;
}
输出结果：aloha 666
hello 100

        注意，st的迭代器位置必须在ed之前。

map<string,int> mp ;
    mp["hello"] = 8 ;
    mp["hello"] = 100 ;
    mp["aloha"] = 666 ;
    mp["good"] = 777 ;
    mp.erase(mp.find("good"),mp.find("good"));
    for(auto ele : mp){
        cout << ele.first << ' ' << ele.second << endl ;
    }

        输出结果：aloha 666
good 777
hello 100

其实是什么也没有删除。
（3） size(),用来获得map中映射的对数，时间复杂度O(1)。

map<string,int> mp ;
    mp["hello"] = 8 ;
    mp["hello"] = 100 ;
    mp["aloha"] = 666 ;
    mp["good"] = 777 ;
    cout << mp.size() << endl ;
输出结果：3

（4） clear()，用来清空map中所有元素，复杂度为O(N)，其中N为map中元素的个数。

map<string,int> mp ;
    mp["hello"] = 8 ;
    mp["hello"] = 100 ;
    mp["aloha"] = 666 ;
    mp["good"] = 777 ;
    mp.clear() ;
    cout << mp.size() << endl ; 
输出结果：0

    map的常见用途：

（1） 需要建立字符（或字符串）与整数之间映射的题目，使用map可以减少代码量。
（2） 判断大整数或者其他类型数据是否存在的题目，可以把map当成bool数组用。
（3） 字符串和字符串之间的映射。
补充：map和键和值都是唯一的，而如果一个键需要对应多个值，就只能使用multimap。另外，C++11标准中还增加了unordered_map,以散列代替map内部的红黑树实现，使其可以用来处理映射而不需要按key排序的需求，速度比map快很多。
5. queue
queue就是队列，在STL中是实现了一个先进先出的容器，要使用queue，需要在加上queue这个头文件。
queue的定义，queue<typename> q;其中typename可以为任何类型或容器。
queue的访问，由于队列是一种先进先出的限制性数据结构，因此在STL中只能通过front()来访问队首元素，或是通过back()来访问队尾元素。

        queue<`int`> q ;
    for(int i=1;i<5;i++){
        q.push(i) ;
    }
    cout << q.front() << endl ;
    cout << q.back() << endl ;
    输出结果：1

4
Queue常用函数
（1） push(),push(x)将x入队，时间复杂度O(1)
（2） front(),访问队首元素,back()访问队尾元素，时间复杂度O(1)。
（3） pop(),令队首元素出队，时间复杂度O(1)。

queue<int> q ;
    for(int i=1;i<5;i++){
        q.push(i) ;
    }
    q.pop() ;
    cout << q.front() << endl ;
    cout << q.back() << endl ;
输出结果：2

4
（4） empty(),判断队列是否为空，如果是空则返回true，否则返回false。
（5） size(),返回queue内元素的个数，时间复杂度为O(1)。

    queue<int> q ;
    for(int i=1;i<5;i++){
        q.push(i) ;
    }
    if(!q.empty()){
        cout << q.size() ;
    }
输出结果：4

Queue的常见用途：
    当需要实现广度优先搜索时，可以不用自己手工实现一个队列。在使用front()和pop()函数前，必须使用empty()判断队列是否为空，否则可能因为队空而出现错误。

1. priority_queue
   priority_queue又称优先队列，其底层是用堆来进行实现的。在优先队列中，队首的元素一定是当前队列中优先级最高的那一个。C++中的堆默认是大跟堆。
   priority_queue的定义，priority_queue<typename> q,typename可以为任意类型的元素。要使用优先队列，应先添加头文件#include[HTML_REMOVED]。
   Priority_queue只能通过top()函数来访问队首元素(堆顶元素)，也就是优先级最高的元素。

priority_queue<int> q ;
    q.push(3) ;
    q.push(1) ;
    q.push(5) ;
    cout << q.top() << endl ;
输出结果：5

Priority_queue常用函数
（1） push(x)，时间复杂度O(logN),N是堆中元素的个数。
（2） top(),top()可以获得队首元素，时间复杂度O(1)
（3） pop(),令堆顶元素出队，时间复杂度O(logN),其中N是堆中的元素个数。

priority_queue<int> q ;
    q.push(3) ;
    q.push(1) ;
    q.push(5) ;
    cout << q.top() << endl ;
    q.pop() ;
    cout << q.top() << endl ;
输出结果：5
3

（4） empty(),判断队列是否为空，为空返回true，否则返回false。
（5） size(),返回优先队列中元素的个数，时间复杂度O(1)

priority_queue<int> q ;
    q.push(3) ;
    q.push(1) ;
    q.push(5) ;
    if(!q.empty()){
        cout << q.size() << endl ;
    }
输出结果：3

Priority_queue内元素的优先级设置
    如何定义优先队列内元素的优先级是运用好优先队列的关键，下面分别介绍几本数据类型和结构体类型的优先级设置方法。

（1）基本数据类型的优先级设置
基本数据类型的优先级设置方法是类似的，这里用int举例。在C++中默认情况下是大根堆，所以下面两种优先队列的定义是等价的。
Priority_queue<int> q,priority_queue<int,vector<int>,less<int>> q;
可以发现第二种定义方式，后面多了两个参数，一个是vector<int>,另一个是less<int>。其中vector<int>填写的是来承载底层数据结构heap(堆)的容器；第三个参数less<int>则是对第一个参数的比较类，less[HTML_REMOVED]表示数字越大优先级越高，而greater<int>表示数字越小的优先级越大。因此，C++中定义小根堆的方式是,priority_queue<int,vector<int>,greater<int>> q。

priority_queue<int,vector<int>,greater<int>> q ;
    q.push(3) ;
    q.push(1) ;
    q.push(5) ;
    cout << q.top() << endl ;
输出结果：1

（2） 结构体的优先级设置
对结构体进行优先级设置有两种方式，第一种是在结构体内部重载小于号“<”，第二种方式是在结构体外部重载“()”,下面对这两种情况分别举个例子来说明
重载小于号“<”

struct fruit{
    string name ;
    int price ;
    friend bool operator < (fruit f1,fruit f2){
        return f1.price > f2.price ;
    }
};
priority_queue<fruit> q ;
    q.push({"apple",8}) ;
    q.push({"orange",7}) ;
    q.push({"banana",9}) ;
    auto ele = q.top() ;
    cout << ele.name << ' ' << ele.price << endl ;
输出结果：orange 7

这种情况下优先队列只能采用第一种定义方式。
重载小括号“()”

struct fruit{
    string name ;
    int price ;
};
struct cmp{
    bool operator () (fruit f1,fruit f2){
        return f1.price > f2.price ;
    }
};
int main(){

    priority_queue<fruit,vector<fruit>,cmp> q ;
    q.push({"apple",8}) ;
    q.push({"orange",7}) ;
    q.push({"banana",9}) ;
    auto ele = q.top() ;
    cout << ele.name << ' ' << ele.price << endl ;
    return 0 ;
}
输出结果：orange 7

这里的优先队列只能采用第二种定义方式。
小结，即使是基本数据类型或者STL容器，也可以通过同样的方式来定义优先级。
注意：如果结构体内的数据比较庞大，建议使用引用来提高效率，此时比较类的参数中需要加上“const”和“&”，如下所示：

friend bool operator < (const fruit& f1,cosnt fruit& f2){
        return f1.price > f2.price ;
    }
bool operator () (const fruit& f1,const fruit& f2){
        return f1.price > f2.price ;
    }

Priority_queue的常见用途
    Priority_queue可以解决一些贪心问题，也可以对dijkstra进行优化(因为优先队列的本质是堆)，在使用top()函数前，必须用empty()判断优先队列是否为空。

1. stack
   Stack翻译为栈，是STL中实现一个后进先出的容器。
   Stack的定义，stack<typename> name要使用stack需要加上头文件#include<stack>。
   Stack容器内元素的访问，由于栈本身就是一种后进先出的数据结构，在STL的stack中只能通过top()来访问栈顶元素。

stack<int> s ;
    s.push(3) ;
    s.push(1) ;
    s.push(2) ;
    s.push(5) ;
    s.push(4) ;
cout << s.top() << endl ;
输出结果：4

Stack常用函数

（1） push(x),将x压入栈中，时间复杂度O(1)
（2） top()，获得栈顶元素，时间复杂度O(1)
（3） pop(),将栈顶元素弹出，时间复杂度O(1)

stack<int> s ;
    s.push(3) ;
    s.push(1) ;
    s.push(2) ;
    s.push(5) ;
    s.push(4) ;
    cout << s.top() << endl ;
    s.pop() ;
cout << s.top() << endl ;
输出结果：4
5

（4） empty()判断栈是否为空，若为空，返回true，否则返回false，时间复杂度O(1)
（5） size()返回栈中元素的个数，时间复杂度O(1)

stack<int> s ;
    s.push(3) ;
    s.push(1) ;
    s.push(2) ;
    s.push(5) ;
    s.push(4) ;
    if(!s.empty()){
        cout << "栈的大小：" << s.size() << endl ;
}
输出结果：栈的大小：5

Stack的常见用途，stack用来模拟实现一些递归，防止程序对栈内存的限制而导致程序运行出错。

1. pair
   pair是个很实用的数据结构，当想要将两个元素绑在一起作为一个合成元素，又不想定义一个结构体的时候，可以使用pair。Pair的本质就是含有两个类型的结构体，这两个类型可以任意指定。
   pair的定义，pair<typename,typename> name,要使用pair，需要添加#incldue <utility>的头文件，map的头文件里也包含pair。Pair有两个参数，一个是first，一个是second分别对应pair中的2个元素的类型。
   如果想在定义pair的时候初始化pair，只需要跟上一个小括号，里面填写两个想要初始化的元素即可，pair<string,int> name(“hello”,888)。
   如果想要临时创建一个pair，可采用下面的两种方式，
   Pair<string,int>(“haha”,55),make_pair(“haha”,55)。
   Pair中元素的访问，pair中只有两个元素first和second，只需要按照结构体的方式去访问即可。

pair<string,int> p ;
    p.first = "haha" ;
    p.second = 55 ;
    cout << p.first << ' ' << p.second << endl ;
    p = make_pair("hehe",66) ;
    cout << p.first << ' ' << p.second << endl ;
    p = pair<string,int>("wuwu",77) ;
cout << p.first << ' ' << p.second << endl ;
输出结果：haha 55
hehe 66
wuwu 77

pair常用函数
比较操作数
两个pair类型的数据比较可以直接使用==,!=,<,<=,>,>=比较大小，比较的规则是先比较first，在比较second。

pair<string,int> q1,q2,q3 ;
    q1 = make_pair("a",88) ;
    q2 = make_pair("a",99) ;
    q3 = make_pair("b",77) ;
    if(q3 > q1) cout << "q3>q1" << endl ;
if(q2 > q1) cout << "q2>q1" << endl ;
输出结果：q3>q1
q2>q1

pair的常见用途

（1） 可以用来代替二元结构体及其构造函数，节省编码时间。
（2） 作为map的键值对来进行插入。

map<string,int> mp ;
    mp.insert({"haha",888}) ;
    mp.insert(make_pair("hehe",777)) ;
    mp.insert(pair<string,int>("wuwu",666)) ;
    for(map<string,int>::iterator it = mp.begin();it != mp.end();it++){
        cout << it->first << ' ' << it->second << endl ;
}
输出结果：haha 888
hehe 777
wuwu 666

1. bitset
   C++的 bitset 在 bitset 头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。
   下面是具体用法
   构造函数
   bitset常用构造函数有四种，如下

bitset<4> bitset1;　　//无参构造，长度为４，默认每一位为０
    bitset<8> bitset2(12);　　//长度为８，二进制保存，前面用０补充
    string s = "100101";
    bitset<10> bitset3(s);　　//长度为10，前面用０补充
    char s2[] = "10101";
    bitset<13> bitset4(s2);　　//长度为13，前面用０补充
    cout << bitset1 << endl;　　//0000
    cout << bitset2 << endl;　　//00001100
    cout << bitset3 << endl;　　//0000100101
    cout << bitset4 << endl;　　//0000000010101

注意：
用字符串构造时，字符串只能包含 ‘0’ 或 ‘1’ ，否则会抛出异常。
构造时，需在<>中表明bitset 的大小(即size)。
在进行有参构造时， 若参数的二进制表示长度比bitset的size小，则在前面用０补充(如上面的栗子)；若比bitsize大，参数为整数时取后面部分，参数为字符串时取前面部分(如下面栗子) ：

    bitset<2> bitset1(12);　　//12的二进制为1100（长度为４），但bitset1的size=2，只取后面部分，即00
    string s = "100101";　　
    bitset<4> bitset2(s);　　//s的size=6，而bitset的size=4，只取前面部分，即1001
    char s2[] = "11101";
    bitset<4> bitset3(s2);　　//与bitset2同理，只取前面部分，即1110
    cout << bitset1 << endl;　　//00
    cout << bitset2 << endl;　　//1001
    cout << bitset3 << endl;　　//1110

可用的操作符
bitset对于二进制有位操作符，具体如下

    bitset<4> foo (string("1001"));
    bitset<4> bar (string("0011"));
    cout << (foo^=bar) << endl;       // 1010 (foo对bar按位异或后赋值给foo)
    cout << (foo&=bar) << endl;       // 0010 (按位与后赋值给foo)
    cout << (foo|=bar) << endl;       // 0011 (按位或后赋值给foo)
    cout << (foo<<=2) << endl;        // 1100 (左移２位，低位补０，有自身赋值)
    cout << (foo>>=1) << endl;        // 0110 (右移１位，高位补０，有自身赋值)
    cout << (~bar) << endl;           // 1100 (按位取反)
    cout << (bar<<1) << endl;         // 0110 (左移，不赋值)
    cout << (bar>>1) << endl;         // 0001 (右移，不赋值)
    cout << (foo==bar) << endl;       // false (0110==0011为false)
    cout << (foo!=bar) << endl;       // true  (0110!=0011为true)
    cout << (foo&bar) << endl;        // 0010 (按位与，不赋值)
    cout << (foo|bar) << endl;        // 0111 (按位或，不赋值)
    cout << (foo^bar) << endl;        // 0101 (按位异或，不赋值)

此外，可以通过 [ ] 访问元素(类似数组)，注意最低位下标为 ０ ，如下：

    bitset<4> foo ("1011");

    cout << foo[0] << endl;　　//1
    cout << foo[1] << endl;　　//1
    cout << foo[2] << endl;　　//0

当然，通过这种方式对某一位元素赋值也是可以的，栗子就不放了。
可用函数
bitset还支持一些有意思的函数，比如：

    bitset<8> foo ("10011011");
    cout << foo.count() << endl;　　//5　　（count函数用来求bitset中1的位数，foo中共有５个１
    cout << foo.size() << endl;　　 //8　　（size函数用来求bitset的大小，一共有８位
    cout << foo.test(0) << endl;　　//true　　（test函数用来查下标处的元素是０还是１，并返回false或true，此处foo[0]为１，返回true
    cout << foo.test(2) << endl;　　//false　　（同理，foo[2]为０，返回false
    cout << foo.any() << endl;　　//true　　（any函数检查bitset中是否有１
    cout << foo.none() << endl;　　//false　　（none函数检查bitset中是否没有１
    cout << foo.all() << endl;　　//false　　（all函数检查bitset中是全部为１

补充说明一下：test函数会对下标越界作出检查，而通过 [ ] 访问元素却不会经过下标检查，所以，在两种方式通用的情况下，选择test函数更安全一些
另外，含有一些函数：

    bitset<8> foo ("10011011");
    cout << foo.flip(2) << endl;　　//10011111　　（flip函数传参数时，用于将参数位取反，本行代码将foo下标２处"反转"，即０变１，１变０
    cout << foo.flip() << endl;　　 //01100000　　（flip函数不指定参数时，将bitset每一位全部取反
    cout << foo.set() << endl;　　　　//11111111　　（set函数不指定参数时，将bitset的每一位全部置为１
    cout << foo.set(3,0) << endl;　　//11110111　　（set函数指定两位参数时，将第一参数位的元素置为第二参数的值，本行对foo的操作相当于foo[3]=0
    cout << foo.set(3) << endl;　　  //11111111　　（set函数只有一个参数时，将参数下标处置为１
    cout << foo.reset(4) << endl;　　//11101111　　（reset函数传一个参数时将参数下标处置为０
    cout << foo.reset() << endl;　　 //00000000　　（reset函数不传参数时将bitset的每一位全部置为０

同样，它们也都会检查下标是否越界，如果越界就会抛出异常
最后，还有一些类型转换的函数，如下：

    bitset<8> foo ("10011011");
    string s = foo.to_string();　　//将bitset转换成string类型
    unsigned long a = foo.to_ulong();　　//将bitset转换成unsigned long类型
    unsigned long long b = foo.to_ullong();　　//将bitset转换成unsigned long long类型
    cout << s << endl;　　//10011011
    cout << a << endl;　　//155
    cout << b << endl;　　//155

10.algorithm
使用algorithm头文件，需要在头文件下面加一行“using namespace std”，才能使用。
algorithm的常用函数
（1） max(),min(),abs()
max(x,y)和min(x,y)分别返回x和y的最大值和最小值，且参数必须是两个（可以是浮点数），如果要返回三个数x,y,z的最大值，可以使用max(max(x,y),z)的写法。abs(x)返回x的绝对值。注意，x必须是整数，浮点型的绝对值要用math头文件下的fabs。

int x = -1, y = 2 ;
    cout << max(x,y) << ' ' << min(x,y) << endl ;
cout << abs(x) << ' ' << abs(y) << endl ;
输出结果：2 -1
1 2

（2） swap()
swap(x,y)用来交换x和y的值

int x = 3, y = 5 ;
    swap(x,y) ;
cout << "x = " << x << ",y = " << y << endl ;
输出结果：x = 5,y = 3

（3） reverse()
reverse(it1，it2)可以将数组指针或者容器的迭代器在[it1,it2)范围内的元素进行反转。

int v1[] = {3,1,2,5,4} ;
    vector<int> v2(v1,v1+5) ;
    reverse(v1,v1+5) ;
    reverse(v2.begin(),v2.begin()+2) ;
    for(auto ele : v1) cout << ele << ' ' ;
    cout << endl ;
    for(auto ele : v2) cout << ele << ' ' ;
cout << endl ;
输出结果：4 5 2 1 3
1 3 2 5 4

（4） next_permutation()
next_permutation()给出一个序列全排列中的下一个序列。使用的方式和reverse类似。
例如，当n==3时的全排列为
123,132,213,231,312,321，这样231的下一个序列就是312。

int a[] = {1,2,3} ;
    do{
        cout << a[0] << a[1] << a[2] << endl ;
}while(next_permutation(a,a+3)) ;
输出结果：123
132
213
231
312
321

            注意，这里要用do..while否则输出的结果中会少123这种情况。

（5） fill()
fill()函数可以把数组或者容器中的某一段区域赋为某个相同的值。和memset不同的是，这里的赋值可以是和数组类型对应范围中的任意值。

int a[] = {3,1,2,5,4} ;
    fill(a,a+2,888) ;
    for(auto e : a) cout << e << ' ' ;
cout << endl ;
输出结果：888 888 2 5 4

（6） sort()
sort()是用来排序的。sort()的使用方式是，sort(首元素地址(必填)，尾元素地址的下一个地址(必填)，比较函数(非必填))。如果不写比较函数，则默认对给出的区间进行递增排序。

int a[] = {3,1,2,5,4} ;
    sort(a,a+2) ;
    for(auto e : a) cout << e << ' ' ;
    puts("") ;
    sort(a,a+5) ;
    for(auto e : a) cout << e << ' ' ;
cout << endl ;
输出结果：1 3 2 5 4
1 2 3 4 5

实现从大到小排序(char,doubel等基本类型与int类似)

bool cmp(int a,int b){
    return a>b ;
}
int main(){
    int a[] = {3,1,2,5,4} ;
    sort(a,a+2,cmp) ;
    for(auto e : a) cout << e << ' ' ;
    puts("") ;
    sort(a,a+5,cmp) ;
    for(auto e : a) cout << e << ' ' ;
    cout << endl ;
    return 0 ;
}
输出结果：3 1 2 5 4
5 4 3 2 1

结构体的排序，具体看cmp的编写方式。

const int N = 5 ;
struct point{
    int x,y ;
}a[N];

bool cmp(point a,point b){
    return a.x>b.x ;
}
int main(){
    a[0].x = 2 ;
    a[0].y = 3 ;
    a[1].x = 1 ;
    a[1].y = 4 ;
    a[2].x = 2 ;
    a[2].y = 5 ;
    sort(a,a+3,cmp) ;
    for(int i=0;i<3;i++){
        printf("%d %d\n",a[i].x,a[i].y) ;
    }
    return 0 ;
}
输出结果：2 3
2 5
1 4

如果要按照x从大到小排序，在x相等的时候按照y从小到大排序。

struct point{
    int x,y ;
}a[N];

bool cmp(point a,point b){
    if(a.x != b.x) return a.x > b.x ;
    else return a.y < b.y ;
}

int main(){
    a[0].x = 2 ;
    a[0].y = 3 ;
    a[1].x = 1 ;
    a[1].y = 4 ;
    a[2].x = 2 ;
    a[2].y = 5 ;
    sort(a,a+3,cmp) ;
    for(int i=0;i<3;i++){
        cout << a[i].x << " " << a[i].y << endl ;
    }
    return 0 ;
}
输出结果：2 3
2 5
1 4

最后举个很有意思的栗子，怎么样实现按照字符串的长度排序。

bool cmp(string str1,string str2){
    return str1.size() < str2.size() ;
}

int main(){
    string a[] = {"cccc","zz","bbb","aa"} ;
    sort(a,a+4,cmp) ;
    for(int i=0;i<4;i++){
        cout << a[i] << endl ;
    }
    return 0 ;
}
输出结果：zz
aa
bbb
cccc

实现了按照字符串的长度排序，但是如果当长度相同按字典序排，如何实现？

bool cmp(string str1,string str2){
    if(str1.size() != str2.size()) return str1.size() < str2.size() ;
    else return str1 < str2 ;
}

int main(){
    string a[] = {"cccc","zz","bbb","aa"} ;
    sort(a,a+4,cmp) ;
    for(int i=0;i<4;i++){
        cout << a[i] << endl ;
    }
    return 0 ;
}
输出结果：aa
zz
bbb
cccc

（7） lower_bound()和upper_bound()
lower_bound()和upper_bound()需要用在一个有序数组或者容器中。
Lower_bound(st,ed,val)用来寻找在数组或者容器中的[st,ed)范围内第一个值大于等于val的元素的位置，如果是数组，则返回该位置的指针，如果是容器则返回该位置的迭代器。
Upper_bound(st,ed,val)用来寻找在数组或者容器中的[st,ed)范围内的第一个大于val的元素的位置，如果是数组，则返回该位置的指针，如果是容器，则返回该位置的迭代器。

int a[10] = {1,2,2,3,3,3,5,5,5,5} ;
//search -1
int* lp = lower_bound(a,a+10,-1) ;
int* up = upper_bound(a,a+10,-1) ;
cout << lp - a << ' ' << up - a << endl ;
//search 1
lp = lower_bound(a,a+10,1) ;
up = upper_bound(a,a+10,1) ;
cout << lp - a << ' ' << up - a << endl ;
//search 3
lp = lower_bound(a,a+10,3) ;
up = upper_bound(a,a+10,3) ;
cout << lp - a << ' ' << up - a << endl ;
//search 4
lp = lower_bound(a,a+10,4) ;
up = upper_bound(a,a+10,4) ;
cout << lp - a << ' ' << up - a << endl ;
//search 6
lp = lower_bound(a,a+10,6) ;
up = upper_bound(a,a+10,6) ;
cout << lp - a << ' ' << up - a << endl ;

输出结果：0 0
0 1
3 6
6 6
10 10

如果想要获得数组中欲查元素的下标，可以直接令lower_bound()和upper_bound()的返回值减去数组的首地址即可。如果查找的对象是容器，则返回的是对应的迭代器。