一、容器

（1）容器分类

<1>顺序容器（序列容器）

<2>关联容器

<3>容器适配器

（2）vector容器

<1>概念

vector是一个连续的空间。vector<T> 容器是包含 T 类型元素的序列容器，和 array<T，N> 容器相似，不同的是 vector<T> 容器的大小可以自动增长，从而可以包含任意数量的元素；因此类型参数 T 不再需要模板参数 N。只要元素个数超出 vector 当前容量，就会自动分配更多的空间。只能在容器尾部高效地删除或添加元素。

<2>vector的构造和赋值

• 构造

1.空的
    vector<int> empty;
2.10个初始值为0的
    vector<int> fault(10);
3.10个初始值为2的
    vector<int> fault2(10,2);
4.c++11
    vector<int> vec={1,2,3,4,5,6,7,8,9};
5.拷贝构造
    vector<int> vec1=vec;或者：
    vector<int> vec1(vec);
6.调用构造函数来部分构造
      vector<int> vec2(vec.begin(),vec.begin()+6);
或者： vector<int> vec2(vec.begin(),next(vec.begin(),6));

• 赋值

1.变量之间直接赋值
    vec2=vec1;
2.赋常值
    vec2={10,11,12,13,14};
3.使用assign方法赋值
    vec2.assign(vec.begin()+6,vec.end());
或者：
    vec2.assign(next(vec.begin(),6),vec.end());//next对于vector和list一样

<3>vector的遍历

一、遍历vector

• （1）c语言风格的遍历方法

vector<int> vec={1,2,3,4,5,6};
for(int i=0;i!=vec.size();++i){//c++一般用不等于表示，不用<了
        cout << vec[i] << " ";
}
cout << endl;

• （2）迭代器（把迭代器当作指针来看）

vector有4中迭代器：
(1)顺序可修改的迭代器：iterator，操作：begin()、end()
(2)逆序可修改的迭代器：reverse_iterator，操作：rbegin()、rend()
(3)顺序不可修改的迭代器：const_iterator，操作：cbegin()、cend()
(4)逆序不可修改的迭代器：const_reverse_iterator，操作：crbegin()、crend()

A. 使用迭代器顺序遍历

void Travesal(vector<int>& vec){//不能使用const
    vector<int>::iterator it=vec.begin();
    while(it!=vec.end()){
            cout << *it << " ";
            ++it;//不要忘了循环
    }
}

B. 使用迭代器逆序遍历

void TravesalReverse(vector<int>& vec){//不能使用const
    vector<int>::reverse_iterator rit=vec.rbegin();
    while(rit!=vec.rend()){
            cout << *rit << " ";
            ++rit;
    }
}

C. 不可修改的顺序遍历

void TravealConst(const vector<int>& vec){
    vector<int>::const_iterator cit=vec.cbegin();
    while(cit!=vec.cend()){
        cout << *cit << " ";
        ++cit;
    }
}

D.不可修改的逆序遍历

void TraveaReverselConst(const vector<int>& vec){
    vector<int>::const_reverse_iterator crit=vec.crbegin();
    while(crit!=vec.crend()){
        cout << *crit << " ";
        ++crit;
    }
 }

• （3）基于范围的迭代C++11

void Traversal(const vector<int>& vec){
     for(auto n:vec){
           cout << n << " ";
     }
}

string 和vector的遍历方法一样。

二、修改vector中的值

（1）迭代的方式

vector<int>& Multiply(vector<int>& vec,int n){
    vector<int>::iterator it=vec.begin();
    while(it!=vec.end()){
        *it *=n;
        ++it;
    }
    return vec;//返回引用可以直接修改vec的值，使用void也行，因为参数传的是引用
}

（2）范围的迭代

vector<int>& Multipy2(vector<int>& vec,int m){
    for(auto& n:vec){//直接使用auto不会改变vecor的值，要想改变必须使用auto&
        n *=m;
    }
    return vec;
}

（3）可以使用迭代（类似指针的方式修改）

对于数组中元素访问有两种方式：
（1）下标:arr[i] (2)指针: * (arr+i)
对于vector中的元素也有两种访问方式：
(1)下标:vec[i] (2)迭代器:*(it+i)

vector<int> vec={1,2,3,4,5,6,7};
vector<int>::iterator it=vec.begin();
类似于指针的修改方式： 
*(it+3) *=10;

---

vector的访问：

image.png
元素访问方式：
（1）[ ]
（2）.at(迭代器)
（3）.front()
（4）.back()

---

<4> 插入和删除

（1）插入

• 插入一个元素
  尾插入：push_back(val)
  任意位置插入：insert(迭代器的位置，val)

vec.push_back(100);//在vec的尾部插入元素100
vec.insert(vec.begin()+2,100);//在索引为2的地方插入100；

• 一次插入多个元素
  插入多个重复的元素：insert(插入的迭代器位置，元素个数，val)；
  插入数组：insert(插入的迭代器位置，数组的开始，数组的结束)；
  插入vector：insert(插入的迭代器位置，vector的begin()，vector的end())；

1.插入数组：
int arr[]={1,2,3};
vec.insert(vec.begin(),arr,arr+3);//c++98
vec.insert(vec.begin(),begin(arr),end(arr));//C++11
2.插入vector
vector<int> v={0,-1,-2,-3};
vec.insert(vec.end(),v.begin(),v.end());
3.一次性插入多个元素：
vec.insert(vec.end(),5,100);//在结束位置插5个100

（2）删除

• 删除一个元素
  尾删除：pop_back();
  任意位置删除：erase(迭代器的位置);

vec.erase(vec.begin()+2);//删除索引为2的元素

删除一个元素后，vector 的大小减 1；但容量不变。会返回一个迭代器，它指向被删除元素后的一个元素。

    it=vec.begin();
    it +=1;
    vec.erase(it);
    cout << *it << endl;

• 删除多个元素
  删除多个元素：erase(删除的迭代器起点，删除的迭代器终点);（不包括终点，左闭右开），作为删除不包括传进去的最后一个迭代器。

vec.erase(vec.begin()+1,vec.end()-1);//留第一个和最后一个元素
vec.erase(vec.begin()+1,vec.begin()+1);//不会删除改元素，该区间为空集
//[1,1)可以表示空集，不会做任何删除。

<5>成员函数

• vector的整体赋值

（1）vector的构造函数

vector<int> v2(vec.begin(),vec.end());

（2）使用assign整体赋值

(1)assign赋n个相同的值：
vec.assign(5,100);//5个100
(2)使用vector给另一个vector赋值： 
    vector<int> v3;
    v3.assign(vec.begin(),vec.end());
(3)使用数组给vector赋值
int arr[]={2,3,4,5};
vec.assign(arr,arr+3);

（3）swap

vector<int> vec1={1,2,3,4};
vector<int> vec2={5,6,7,8,9,10};
vec1.swap(vec2);
则现在vec1现在的值就是vec2，而vec2的值为vec1.

（4）clear
在vector中移除所有元素，这个vector将被销毁，其size的大小为0；

  std::vector<int> myvector;
  myvector.push_back (100);
  myvector.push_back (200)
 myvector.clear();
  myvector.push_back (1101);
则现在myvector里面只剩下最后添加的元素1101.

（5）empty
判断vec是否是空的。

vec.empty();

<6>vector的容量和大小

• size表示vector中元素的个数，capacity表示vector可容纳的元素大小，超过这个会引发vector的重分配。capacity申请机制：C++每次申请内存一般都会成倍的增长1，2，4，8，16...

vec.size();//返回vec的size大小
vec.capacity();//返回capacity的大小
vec.max_size();//返回vec的最大size

• resize()：可以改变size大小，如果改小会丢掉后面的元素，如果改大会对新增加的元素进行值初始化。

vector<int> vec={1,2,3,4,5,6};
vec.resize(5);//1,2,3,4,5
vec.resize(7,10);//1,2,3,4,5,10,10
vec.resize(10);//1,2,3,4,5,10,10,0,0,0

• reserve()：可以改变capacity的大小，容器内的对象并没有真实的内存空间(空间是"野"的)，直接访问会出现越界，访问的值是随机值。注意capacity大于size的地方都是不能使用reserve。

vec.reserve(100);//给vec预留100个空间

• STL容器中拥有capacity属性的只有string和vector

vector的疑惑点：
因为vector是连续内存，插入数据时，申请了一块新的内存，以前的it就失效了。如果内存不变就不会失效。所以要想在不改变迭代器时删除增加的元素，可以在位置1指定capacity的大小，这样就不会由于重新申请内存而导致it失效。

    vector<int> vec={1,2,3,4,5,6,7};
    vector<int>::iterator it=vec.begin();
         【位置1】
    it=vec.begin();
    it +=2;
    cout << "capacity:" << vec.capacity() << endl;//7   
    vec.insert(it,200);
    cout << "capacity:" << vec.capacity() << endl;//14(重新申请了一块内存,所以迭代器就失效了)
    vec.erase(it);//所以删除操作不能删除200这个元素
或者在删除前再重新指定迭代器。
     it=vec.begin();
     it +=2;
     vec.erase(it);

注意：vector在插入元素之前reserve()的话，it的位置不会向后移动，否则就会向后移动。因此vector在删除时需要重新指定it。

<7>迭代器的位置

next(vec.begin(),5);//vec.begin()+5
begin(vec);//ve.begin()
end(vec);//vec.end()

<8>二维vector

    vector<vector<int>> vec={{1,2,3,4},{5,6,7,8}};
    cout << vec.size() <<endl;//2
    cout << vec[0].size() <<endl;//4
    for(auto r:vec){//遍历所有行
        for(auto n:r){//遍历每行中的元素
            cout << n << " ";//1 2 3 4 换行 5 6 7 8
        }
        cout << endl;
    }

（3）list容器

<1>list概念

list一般不使用随机访问，要想使用随机访问可以使用vector。
list<T> 容器模板定义在list 头文件中，是 T 类型对象的双向链表。list 容器具有一些 vector 和 deque 容器所不具备的优势，它可以在常规时间内，在序列已知的任何位置插入或删除元素。list 的缺点是无法通过位置来直接访问序列中的元素，也就是说，不能使用索引访问元素。为了访问 list 内部的一个元素，必须一个一个地遍历元素，通常从第一个元素或最后一个元素开始遍历。

<2>list的构造和赋值

对于vector和list有相同的构造和赋值，注意list没有算术运算，可以使用next来代替索引。
例如：it=li.begin()+4------>it=next(li.begin(),4);

<3>list的遍历

list不能通过下标访问元素，可以使用迭代器和c++11的auto。
和vector一样。除过使用索引访问外，其他的方式都一样。

<4>随机访问

list不能像vector一样进行下标的随机访问，要想访问，必须从begin开始进行遍历，并且迭代器不能进行加减运算，但是可以自增自减。也可以使用c++11的next函数来实现迭代器的增长。

    it = l.begin();
    for(int i=0;i<4;++i){
        ++it;
    }
等价于：
    it = next(l.begin(),4);

<5>list的插入和删除

（1）插入

• 插入一个元素
  尾添加：push_back(val);
  首添加：push_front(val);（vector没有）
  指定位置插入：insert(迭代器,val);（要从首或者尾一直自增或自减）
  注意：再插入前要确保迭代器的存在，如果迭代器指向列表中不存在的元素，则需要重新指定迭代器。

1.尾添加：
        l.push_back(7);
2.首添加：
        l.push_front(-2);
3.插入:
        it=l.begin();
        ++it;
        //it=it+1;//list迭代器不能做算数运算，但是可以做自增自减
        l.insert(it,100);//迭代器it指向插入的后一个元素
        cout << *it << endl;//2

• 批量插入
  插入多个相同的元素：insert(迭代器,num,val);
  插入数组：insert(迭代器,数组起始位置,数组终止结束);
  插入列表：insert(迭代器,vec.begin().vec.end());

1. 插入多个相同的元素:
        l.insert(it,5,100);
2.插入数组
    int arr[]={11,12,13,14};
    l.insert(it,arr,arr+4);
3.插入向量：
    vector<int> vec1={21,22,23,24};
    l.insert(l.end(),vec1.begin(),vec1.end());

（2）删除

• 删除一个元素
  尾删除：pop_back();
  首删除：pop_front();
  指定位置删除：erase(迭代器);

        list<int> l={1,2,3,4,5,6};
        list<int>::iterator it=l.begin();
1. 尾删除：
        l.pop_back();
2. 首删除：
        l.pop_front();
3. 指定位置删除：
        --it;//在增加一个元素后,list的it会指向插入的后一个元素,要想删除插入的元素,需将it前移一个
        l.erase(it);

• 批量删除

    list<int>::iterator first=l.begin();
    ++first;
    l.erase(first,it);//用两个迭代器表示删除的起始和终止位置，不包括终止位置。

• 使用remove进行删除
  删除指定的元素：l.remove(val);(多个相同的都会删除)
  删除某个条件的元素：l.remove_if(函数指针/仿函数/lambda表达式);

1.形式一：函数形式
bool condition(int n){
    return n/10==0;//删除十位数是1的数
}
     l.remove_if(condition);
2.形式二：仿函数（重载（）运算符）
class Condition{
public:
    bool operator()(int n){
        return n/10==0;
    }
};
    Condition cond;
    l.remove_if(cond);
或者使用匿名对象：
    l.remove_if(Condition());
3.形式三：lamd表达式（c++11）
    l.remove_if([](int n){return n/10==0;});

<6>list的其他成员函数

（1）逆序：l.reverse();

li.reverse();

（2）排序：l.sort();
可以加函数指针，仿函数，lamd表达式来修改排序规则

l.sort();//默认为升序
l.sort([](int a,int b){return a>b;});//降序

（3）合并：l.merge(list<T>)
两个有序list的合并。 merge() 以另一个具有相同类型元素的 list 容器作为参数。两个容器中的元素都必须有相同的排序规则。参数 list 容器中的元素会被合并到当前的 list 容器中.

    list<int> l2={3,6,9,20,50};
    l.merge(l2);//merge()默认时升序排序，要想使用降序，可以在merge的第二个参数上编写排序规则。
示例：
     list<int> li2={100,50,25,20,18,6};
     li.merge(li2,[](int a,int b){return a>b;});

（4）list整体赋值方法

• 使用list的构造函数

    list<int> l2(l.begin(),l.end());

• 使用函数assign来赋值

    list<int> l3;
    l3.assign(l.begin(),l.end());

（5）判空
判断li是否是空的。

li.empty()

（6）元素访问

li.front();//获取list 的第一个元素
li.back()；//获取list的最后一个元素

（7）swap交换

li.swap(li1);

（8）clear清空

li.clear();

<7>emplace_back和push_back的区别：

vector和list都有emplace_back和push_back,emplace对应于insert,对于常规类型来说，emplace_back和push_back是没有区别的，但是对于类类型，这两个有区别。

vector<Simple> vec1;
vector<Simple> vec2;
vec1.push_back(Simple(1));//调用构造函数和拷贝构造函数
vec1.push_back(Simple(2));//调用构造函数和拷贝构造函数，并且会拷贝构造Simple 1（由于capacity的原因）

如果是vec2.emplace_back(Simple(1))的话，和push_back是一样的，但是
emplace_back参数可以直接使用构造函数的参数，在函数内部执行对象的构造,减少了拷贝构造。
vec2.emplace_back(1)；//只调用构造
vec2.emplace_back(2)；//只调用构造，但是由于capacity的原因会拷贝构造Simple1.

（4）set

<1>概念

set 是关联容器的一种，是排序好的集合（元素已经进行了排序），不能有重复的元素，即有序性，数据的唯一性。不能直接修改 set 容器中元素的值。因为元素被修改后，容器并不会自动重新调整顺序，于是容器的有序性就会被破坏，再在其上进行查找等操作就会得到错误的结果。因此，如果要修改 set 容器中某个元素的值，正确的做法是先删除该元素，再插入新元素。

<2>应用

如果题目中要求找到重复数字、第几大的数优先考虑set。

<3>特点

（1）有序性
（2）唯一性
（3）不能随机访问[]（随机访问的只有vector和deque）
（4）没有算数运算,但是可以自增自减（所以用next和prev函数代替）

it =s.begin()+3---------->it=next(s.begin(),3);
it=s.end()-3-------------->it=prev(s.end(),3);

（5）和vector、list一样有4中迭代器

<4>set的构造

和vector、list的一样。

• 默认构造(可带参数)
• 复制构造
• 范围赋值构造

<5>插入

只有insert可以插入，而且插入的时候不需要指定位置，因为set是有序的，插进去以后set会自动排序的。

• 函数原型：

pair<iterator, bool> insert(const T & val);

set的insert的返回值是pair模板类对象x:
(1)如果 x.second 为 true，则说明插入成功，此时 x.first 就是指向被插入元素的迭代器；
(2)如果 x.second 为 false，则说明要插入的元素已在容器中，此时 x.first 就是指向原有那个元素的迭代器。

    typedef set<int>::iterator IT;
    int a[5] = { 3,4,6,1,2 };
    set<int> st(a,a+5);    // st里是 1 2 3 4 6
    pair< IT,bool> result;
    result = st.insert(5); // st变成  1 2 3 4 5 6
    if(result.second)    //插入成功则输出被插入元素
        cout << * result.first  << " inserted" << endl; //输出: 5 inserted
    if(st.insert(5).second)
        cout << * result.first  << endl;
    else
        cout << * result.first << " already exists" << endl;
     //输出 5 already exists  

<6>删除

只有erase可以删除元素，和插入一样，删除时只需指定要删除的元素或者迭代器即可。

• 删除单个元素

s.erase(100);//指定删除的元素
s.erase(it);//指定删除的迭代器，it指向谁，就删除哪个元素

• 删除多个元素

s.erase(it,s.end());//删除从it到是s.end()之间的元素，不包括最后的元素

<7>set的成员函数

• count()函数
  查找数据是否存在，存在返回1，不存在返回0

s.count(2);//查找在s中是否存在元素2

• find()函数
  返回的是迭代器，如果查找的元素不存在，则返回的迭代器会指向end()的位置。

auto it3=s.find(29);
cout <<(it3==s.end()) << endl;//如果不存在则会返回迭代器到end()的位置
auto it4=s.find(4); 
cout << *it4 << endl;

• equal_range()函数

pair<iterator, iterator> equal_range(const T & val);

其返回值是一个pair对象。返回值对象中的 first 就是 lower_bound 的值，second 就是 upper_bound 的值。

    set<int> st={3,8,4,7,5,6};
    typedef set<int>::iterator IT;
    pair<IT,IT> bounds = st.equal_range(4);
    cout << * bounds.first << "," << * bounds.second ;  //输出：4,5

• 判空（empty）
• 交换（swap）
• 清空（clear）
• 大小（size）

<8>关于set的排序

set存放的对象必须可以比较大小，所以类中必须重载<、==运算符。

• （1）有关set的说明
  如果set中存放的是类类型的话，需要在类里面重载<运算符或仿函数类，因为set里面必须是排好序的。

class Simple{
public:
    /* bool operator==(const Simple&)const{//必须要加const
        return true;
    } */
    bool operator<(const Simple&)const{//<是必要的，
        return true;
    }   
};
set存放的对象必须可以比较大小，所以类必须重载<、==运算符
    set<Simple> ss;
    ss.insert(Simple());

• （2）基本类型的降序
  默认按照val升序排列。自定义排序时，只能使用仿函数类来重写排序规则，不能使用仿函数、函数指针或者lambda表达式。

class Greator{
public:
    bool operator()(int a,int b){
        return a>b;
    }
};
int main(){
//只能添加仿函数类名，不能是函数指针或lamd表达式
//只要有了类名，就可以在里面定义对象，达到仿函数的目的。
    set<int,Greator> s={10,2,3,4,63,3,1,78,19};//输出：降序排列
}

}

注意：由于改变了set的定义形式（加了仿函数类），因此打印时需要重新编写打印函数，最好写成模板格式。

void Printfunc(const set<int,Greator> s){
    for(auto n:s){
        cout << n << " ";
    }

可以写成下面的函数模板的形式：

• （3）类类型的排序

template<typename T,typename S>
void Print(const set<T,S>& s){
    for(auto n:s){
        cout << n << " ";
    }
    cout << endl;
}
class Student{
    string name;
    int age;
    float scores;
public:
    Student(const string& name,int age,float scores):name(name),age(age),scores(scores){}
    int GetAge()const{return age;}
    float GetScores()const{return scores;}
    friend ostream& operator<<(ostream& os,const Student& s){//由于输出的是对象
        return os<<s.name<<','<<s.age<<','<<s.scores;//所以必须重载输出运算符
    }
};
class AgeComp{
public:
    bool operator()(const Student& a,const Student& b){//访问类里面的成员方式：
        return a.GetAge()>b.GetAge();//(1)变公有(2)友元类(3)提供接口（常用）
    }
};
class ScoreComp{
public:
    bool operator()(const Student& a,const Student& b){
        return a.GetScores() < b.GetScores();
    }
};
int main(){
    set<Student,AgeComp> stu={      
        Student("张三",21,89),
        Student("李四",19,78),
        Student("王五",20,69)};
    Print(stu);//按年龄的降序来排
    set<Student,ScoreComp> stu2(stu.begin(),stu.end());
    Print(stu2);//按成绩的升序来排
}

（5）map

<1>定义

map 是关联容器的一种，map 的每个元素都分为键和值两部分，容器中的元素是按键排序的，并且不允许有多个元素的键相同。
注意，不能直接修改 map 容器中的键。因为 map 中的元素是按照键排序的，当键被修改后，容器并不会自动重新调整顺序，于是容器的有序性就会被破坏，再在其上进行查找等操作就会得到错误的结果。

<2>特点

（1）map是键值对<key,value>构据集合。key必须唯一。
（2）主要用来查找key对应value,要求key必须是可排序的，必须支持<比较运算符。map默认是以key升序存放键值对<key,value>数据，比较适合二分查找。
（3）map内部结构：
map使用pair<key,value>类模板保存key与value，pair<key,value>有两个public成员变量first和second,first存放key,second存放value。在map里面可以使用map<>::value_type表示pair<key,value>。

template<typename T,typename U>
struct pair{
      T first;
      U second;
};
typedef pair<key,value> value_type;

<3>应用

map主要用于资料一对一映射(one-to-one)的情況。比如对于需要统计或者需要下标和值的话，可以优先考虑map。

<4>构造

初始化时必须给map<>类模板同时设置key与value的类型模板实参。
比如：map<int, string> mapStudent;

1:map<char,int> first;
  first['a']=10;
  first['b']=30;
  first['c']=50;
  first['d']=70;
2:map<char,int> second (first.begin(),first.end());
3:map<char,int> third (second);
4:map<int,int> dict={{1,2},{3,4},{5,6}};

• 更改排序规则

5:map<char,int,classname(类名)> fourth; 
示例：
class Greator{
public:
    bool operator()(int p1,int p2){
        return p1 > p2;
    }
};
map<int,int,Greator> dict1={{2,3},{8,5},{6,7}};

<5>访问

• 可以使用方括号来访问值，通过传键来访问。

    map<string,string> dict={
        {"Apple","苹果"},
        {"Orange","橘子"},
        {"banana","香蕉"}
    };
    cout << dict["Apple"] << endl;
    dict["Orange"]="橙子";//可以通过键修改值

注意：方括号里面只能放键，来查找，[]如果能查到，返回查到的值；如果没有查到则添加新的，新的键为查找的内容，值为空。因此一般和count()函数配套使用。

if(dict.count["hello"]==1){
       cout << dic["hello"] << endl;
}

• 或者也可以通过.at()来访问，里面存放键。

cout << dict.at("Apple") <<endl;

<6>遍历

• c++11

for(auto p:dict){//p可以理解为一个pair对象,所以用.访问
    cout << p.first << "," << p.second << endl;
}

• 迭代器

map<int,int>::iterator it=m.begin();
while(it!=m.end()){//it理解为迭代器，用箭头访问
    cout <<it->first << "," << it->second << endl;
}

• for_each

for_each(m.begin(),m.end(),仿函数/函数指针/lamd)

示例：

void Show(pair<string,string> p){
    cout << p.first << " "<<p.second << endl;
}
class Print{
public:
    void operator()(pair<string,string> p){
        cout << p.first << " "<<p.second << endl;
    }
};
    for_each(dict.begin(),dict.end(),[](pair<string,string> p){cout <<p.first << ":"<<p.second<<endl;;});
    for_each(dict.begin(),dict.end(),Show);
    for_each(dict.begin(),dict.end(),Print());

<7>添加

• insert插入pair

dict.insert(pair<string,string>("cherry","樱桃"));

• insert插入make_pair

dict.insert(make_pair("cherries","车厘子"));//自动推断

• 用数组的方式添加数据

dict["haha"]="好好";

• 用insert函数插入value_type数据

dict.insert(map<string,string>::value_type("hehe","呵呵"));

• 指定位置插入

 map<char,int>::iterator it = mymap.begin();
 mymap.insert (it, pair<char,int>('b',300));  

• insert返回一个pair<it,bool>来判断是否插入成功

    typedef map<string,string>::iterator IT;
    pair<IT,bool> result;
    result=dict.insert(pair<string,string>("cherrys","樱桃2"));
    if(!result.second){
        cout << "error" << endl;
    }else{
        cout << result.first->second << endl;//result.first是迭代器，->second是val。
    }

<8>删除

• 直接用键来删除

dict.erase("cherrys");

• 通过迭代器删除

  it=mymap.find('b');
  mymap.erase (it);

• 范围删除

  it=mymap.find ('e');
  mymap.erase ( it, mymap.end() );

<9>查找

• find()
find通过键来查找元素的位置，找到返回指向该值的迭代器，否则返回end()。

map<string,string>::iterator it=dict.find("banana");
//auto it=dict.find("banana");也可以
    if(it!=dict.end()){
        cout << it->first << " " << it->second << endl;//it当作指针
    } 

• count()
  通过键来查找是否存在键，存在返回1，否则返回0.

if(dict.count("Apple")){...}

• equal_range

    typedef map<string,string>::iterator IT;
    pair<IT,IT> res;
    res=dict.equal_range("banana");
    cout << res.first->first << "=" <<res.first->second << endl;//上界
    cout << res.second->first << "=" <<res.second->second << endl;//下界

<10>其他的成员函数

• empty；
• size;
• swap;（a.swap(b)；a和b的元素进行交换）
• clear;

（6）stack

容器适配器有 stack、queue、priority_queue 三种。它们都是在顺序容器的基础上实现的，屏蔽了顺序容器的一部分功能，突出或增加了另外一些功能。要使用 stack，必须包含头文件 <stack>。

<1>定义

stack就是“栈”。栈是一种后进先出的元素序列，访问和删除都只能对栈顶的元素（即最后一个被加入栈的元素）进行，并且元素也只能被添加到栈顶。栈内的元素不能访问。如果一定要访问栈内的元素，只能将其上方的元素全部从栈中删除，使之变成栈顶元素才可以。

<2>stack的注意：

（1）不能随机访问[]；
（2）没有迭代器；stack<int>::iterator it=s.begin();
（3）不能使用for(auot n:s){}；
（4）只能访问栈顶元素。

<3>stack的成员函数

• 入栈：s.push(val);
• 出栈：s.pop();
• 获取栈顶元素：s.top();
• 大小：s.size();
• 判空：s.empty();

stack<int> s;
    for(int i=0;i<10;++i){
        s.push(i);
    }
    cout << "s.size: " << s.size() << endl;
    while(!s.empty()){
        cout << s.top() << " ";
        s.pop();
    }
    cout << "s.size: " << s.size() << endl;  

<4>使用vector、list来构造stack

• 把vector转换成stack

//形式1：
stack<int,vector<int>> s;
s.empty();//0
//形式2：
vector<int> vec={1,2,3,4,5};
stack<int,vector<int>> s1(vec);
while(!s1.empty()){
     cout << s1.top() << " ";//5，4，3，2，1
     s1.pop();
}

<5>反转链表

ListNode* reverseList(ListNode* head) {
//直接法
    ListNode* p=NULL;
    while(NULL!=head){
        ListNode* tmp=head;
        head=head->next;
        tmp->next=p;
        p=tmp;
    }
//使用栈
        if(NULL==head) return head;
        stack<ListNode*> s;
        while(NULL!=head){
            s.push(head);
            head=head->next;
        }
        ListNode* root=s.top();
        ListNode* tail=root;
        s.pop();
        while(!s.empty()){
            tail->next=s.top();
            tail=tail->next;
            s.pop();
        }
        tail->next=NULL;
        return root;
}

（7）queue

<1>定义

queue就是“队列”。队列是先进先出的，和排队类似。队列的访问和删除操作只能在队头进行，添加操作只能在队尾进行。不能访问队列中间的元素。头文件为<list>。

<2>注意

（1）不能随机访问[]；
（2）没有迭代器；stack<int>::iterator it=s.begin();
（3）不能使用for(auot n:s){}；

<3>成员函数

• 队尾添加元素：q.push(val);
• 队首删除元素：q.pop();
• 获取队首元素：q.front();
• 获取队尾元素：q.back();
• 大小：q.size();
• 判空：q.empty();

    queue<int> q;
    for(int i=0;i<10;++i){
        q.push(i);
    }
    cout << "size:" << q.size() << endl;
    while(!q.empty()){
        cout << q.front() << "," << q.back() << endl;
        q.pop();
    }
    cout << "size:" << q.size() << endl;

<4>list、deque转化为queue

可以把list、deque放进去，但是不能放vector,因为list有前删和后删，而vector只有后删.

    list<int> li={1,2,3,4};
    queue<int,list<int>> q1(li);

<5>队列和栈的相互实现

• 用栈实现队列（各司其职）

class MyQueue {
    stack<int> s1;//进
    stack<int> s2;//出
public:
    MyQueue() {
    }
    void push(int x) {
        s1.push(x);
    }
    int pop() {
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.top());
                s1.pop();
            }
        }
        int n=s2.top();
        s2.pop();
        return n;
    }
    int peek() {
        int res=this->pop();
        s2.push(res);
        return res;
    }
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

• 用队列实现栈（互相转换）

class MyStack {
    queue<int> q1;
    queue<int> q2;
public:
    void push(int x) {
        if(!q1.empty()){
            q1.push(x);
        }else{
            q2.push(x);
        }
    }
    int pop() {
        int res;
        if(!q1.empty()){
            while(!q1.empty()){
                res = q1.front();
                q1.pop();
                if(!q1.empty()) q2.push(res);
            }
        }else{
            while(!q2.empty()){
                res = q2.front();
                q2.pop();
                if(!q2.empty()) q1.push(res);
            }
        }
        return res;
    }
    int top() {
        if(!q1.empty()) return q1.back();
        else return q2.back();
    }
    bool empty() {
        return q1.empty() && q2.empty();
    }
};