C++之STL（二）

ゞ浴缸里的玫瑰 2022-01-05 23:25 251阅读 0赞

**目录**

3.4 stack容器

3.5 queue容器

3.6 list容器

3.7 set/multiset容器

3.8 map/multimap容器

--------------------

### 3.4 stack容器 ###

stack是一种**先进后出(First In Last Out,FILO)**的数据结构，它只有一个出口，形式如图所示。stack容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。

有元素推入栈的操作称为：push，将元素推出stack的操作称为：pop。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70][]

**注意：Stack所有元素的进出都必须符合”先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。Stack不提供遍历功能，也不提供迭代器。**

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<stack>
    using namespace std;
    
    /*
    3.4.3.1 stack构造函数
    stack<T> stkT;//stack采用模板类实现， stack对象的默认构造形式：
    stack(const stack &stk);//拷贝构造函数
    3.4.3.2 stack赋值操作
    stack& operator=(const stack &stk);//重载等号操作符
    3.4.3.3 stack数据存取操作
    push(elem);//向栈顶添加元素
    pop();//从栈顶移除第一个元素
    top();//返回栈顶元素
    3.4.3.4 stack大小操作
    empty();//判断堆栈是否为空
    size();//返回堆栈的大小
    */
    
    void test01()
    {
    	stack<int>s;
    	//放数据
    	s.push(10);
    	s.push(30);
    	s.push(20);
    	s.push(40);
    
    	while (s.size() != 0)
    	{
    		cout << "栈顶为：" << s.top() << endl; //40为栈顶 20 30 10
    		//弹出元素
    		s.pop();
    	}
    	cout << "size = " << s.size() << endl;  //0 
    }
    
    int main()
    {
    	test01();
    	system("pause");
    	return 0;
    }

### 3.5 queue容器 ###

Queue是一种**先进先出(First In First Out,FIFO)**的数据结构，它有两个出口，queue容器允许从一端新增元素，从另一端移除元素。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1][]

**注意：Queue所有元素的进出都必须符合”先进先出”的条件，只有queue的顶端元素，才有机会被外界取用。Queue不提供遍历功能，也不提供迭代器。**

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<queue>
    using namespace std;
    
    //先进先出，后进后出
    
    /*
    3.5.3.1 queue构造函数
    queue<T> queT;//queue采用模板类实现，queue对象的默认构造形式：
    queue(const queue &que);//拷贝构造函数
    3.5.3.2 queue存取、插入和删除操作
    push(elem);//往队尾添加元素
    pop();//从队头移除第一个元素
    back();//返回最后一个元素
    front();//返回第一个元素
    
    3.5.3.3 queue赋值操作
    queue& operator=(const queue &que);//重载等号操作符
    3.5.3.4 queue大小操作
    empty();//判断队列是否为空
    size();//返回队列的大小
    */
    
    void test01()
    {
    	queue<int>q;
    	//向队尾添加元素
    	q.push(10);
    	q.push(20);
    	q.push(30);
    	q.push(40);
    
    	while (!q.empty())
    	{
    		//10 40; 20 40 ; 30 40 ; 40 40
    		cout << "队头=" << q.front() << endl;
    		cout << "队尾=" << q.back() << endl;
    
    		//弹出元素
    		q.pop();
    	}
    
    	cout << "size=" << q.size() << endl;
    }
    
    int main()
    {
    	test01();
    	system("pause");
    	return 0;
    }

### 3.6 list容器 ###

链表是一种物理[存储单元][Link 1]上非连续、非顺序的[存储结构][Link 2]，[数据元素][Link 3]的逻辑顺序是通过链表中的[指针][Link 4]链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储[数据元素][Link 3]的数据域，另一个是存储下一个结点地址的[指针][Link 4]域。

相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。

**List和vector是两个最常被使用的容器。**

**List容器是一个循环的双向链表。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2][]

*  采用动态存储分配，不会造成内存浪费和溢出
 *  链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
 *  链表灵活，但是空间和时间额外耗费较大

List迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增，递减、取值、成员取用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。

由于list是一个双向链表，迭代器必须能够具备前移、后移的能力，所以list容器提供的是**Bidirectional Iterators**。

List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效，甚至List元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<list>
    #include<string>
    #include<algorithm>
    using namespace std;
    
    //list是双向循环链表
    void test01()
    {
    	list<int> myList;
    	for (int i = 0; i < 10; i++){
    		myList.push_back(i);
    	}
    
    	list<int>::_Nodeptr node = myList._Myhead->_Next;
    
    	for (int i = 0; i < myList._Mysize * 2; i++){
    		cout << "Node:" << node->_Myval << endl;
    		node = node->_Next;
    		if (node == myList._Myhead){
    			node = node->_Next;
    		}
    	}
    }
    
    //list常用API
    /*
    3.6.4.1 list构造函数
    list<T> lstT;//list采用采用模板类实现,对象的默认构造形式：
    list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
    list(n,elem);//构造函数将n个elem拷贝给本身。
    list(const list &lst);//拷贝构造函数。
    3.6.4.2 list数据元素插入和删除操作
    push_back(elem);//在容器尾部加入一个元素
    pop_back();//删除容器中最后一个元素
    push_front(elem);//在容器开头插入一个元素
    pop_front();//从容器开头移除第一个元素
    insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
    insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
    insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
    clear();//移除容器的所有数据
    erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
    erase(pos);//删除pos位置的数据，返回下一个数据的位置。
    remove(elem);//删除容器中所有与elem值匹配的元素。
    
    
    
    */
    
    void printList(list<int>&L)
    {
    	for (list<int>::iterator it = L.begin(); it != L.end(); it++)
    	{
    		cout << *it << " ";
    	}
    	cout << endl;
    }
    
    void test02()
    {
    	list<int>L(10, 10);
    	list<int>L2(L.begin(), L.end());
    	printList(L);
    	printList(L2);
    
    	L2.push_back(100);
    	//逆向打印
    	for (list<int>::reverse_iterator it = L2.rbegin(); it != L2.rend(); it++)
    	{
    		cout << *it << " ";
    	}
    	cout << endl;
    
    	//list迭代器不支持随机访问
    	list<int>::iterator itBegin = L2.begin();
    	//itBegin = itBegin + 1;  不支持随机访问
    
    	//插入数据
    	list<int>L3;
    	L3.push_back(10);
    	L3.push_back(30);
    	L3.push_back(20);
    	L3.push_front(100);
    	L3.push_front(300);
    	L3.push_front(200);
    
    	printList(L3);  // 200 300 100 10 30 20 
    
    	//删除两端数据
    	L3.pop_back();  //头删
    	L3.pop_front();  //尾删
    
    	printList(L3);  //300 100 10 30
    
    	L3.insert(L3.begin(), 1000);
    	printList(L3);  //1000 300 100 10 30
    
    	//remove(elem);//删除容器中所有与elem值匹配的元素。
    	L3.push_back(10);  
    	printList(L3);  //1000 300 100 10 30 10
    	L3.remove(10);
    	printList(L3);  //1000 300 100 30
    }
    
    /*
    3.6.4.3 list大小操作
    size();//返回容器中元素的个数
    empty();//判断容器是否为空
    resize(num);//重新指定容器的长度为num，
    若容器变长，则以默认值填充新位置。
    如果容器变短，则末尾超出容器长度的元素被删除。
    resize(num, elem);//重新指定容器的长度为num，
    若容器变长，则以elem值填充新位置。
    如果容器变短，则末尾超出容器长度的元素被删除。
    
    3.6.4.4 list赋值操作
    assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
    assign(n, elem);//将n个elem拷贝赋值给本身。
    list& operator=(const list &lst);//重载等号操作符
    swap(lst);//将lst与本身的元素互换。
    3.6.4.5 list数据的存取
    front();//返回第一个元素。
    back();//返回最后一个元素。
    */
    
    void test03()
    {
    	list<int>L3;
    	L3.push_back(10);
    	L3.push_back(30);
    	L3.push_back(20);
    	L3.push_front(100);
    	L3.push_front(300);
    	L3.push_front(200);
    
    	cout << "大小：" << L3.size() << endl;
    
    	if (L3.empty())
    	{
    		cout << "L3为空" << endl;
    	}
    	else
    	{
    		cout << "L3不空" << endl;
    	}
    
    	L3.resize(10);
    	printList(L3);
    
    	L3.resize(3);
    	printList(L3);
    
    	list<int>L4;
    	L4.assign(L3.begin(), L3.end());
    
    	cout << "front" << L4.front() << endl;
    	cout << "back: " << L4.back() << endl;
    }
    
    /*
    3.6.4.6 list反转排序
    reverse();//反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。
    sort(); //list排序
    */
    
    bool myCompare(int v1, int v2)
    {
    	return v1 > v2;
    }
    
    void test04()
    {
    	list<int>L;
    
    	L.push_back(10);
    	L.push_back(20);
    	L.push_back(40);
    	L.push_back(30);
    
    	L.reverse();
    	printList(L);  //30 40 20 10
    
    	//所有不支持岁访问的迭代器 不可以用系统提供的算法
    	//如果不支持用系统提供算法，那么这个类内部会提供
    	//sort(L.begin(), L.end());  
    	L.sort();
    	printList(L);  //从小到大
    
    	//从大到小
    	L.sort(myCompare);
    	printList(L);
    }
    
    //自定义数据类型
    class Person
    {
    public:
    	Person(string name, int age, int height)
    	{
    		this->m_Name = name;
    		this->m_Age = age;
    		this->m_Height = height;
    	}
    
    	//重载 == 让remove可以删除自定义的Person
    	bool operator== (const Person &p)
    	{
    		if (this->m_Name == p.m_Name && this->m_Age == p.m_Age && this->m_Height == p.m_Height)
    		{
    			return true;
    		}
    		return false;
    	}
    
    
    	string m_Name;
    	int m_Age;
    	int m_Height; //身高
    };
    
    //myComparePerson  排序规则  如果年龄相同 按照身高升序排序
    bool myComparePerson(Person &p1, Person &p2)
    {
    	/*if (p1.m_Age > p2.m_Age)
    	{
    		return true;
    	}
    	return false;*/
    
    	if (p1.m_Age == p2.m_Age)      //身高从小到大排序，年龄按照从大到小排序
    	{
    		return p1.m_Height < p2.m_Height;
    	}
    	else
    	{
    		return p1.m_Age>p2.m_Age;
    	}
    }
    
    void test05()
    {
    	list<Person>L;
    	Person p1("A", 10, 165);
    	Person p2("B", 11, 170);
    	Person p3("C", 12, 120);
    	Person p4("D", 13, 200);
    	Person p5("E", 14, 203);
    	Person p6("F", 15, 203);
    	Person p7("G", 14, 150);
    
    	L.push_back(p1);
    	L.push_back(p2);
    	L.push_back(p3);
    	L.push_back(p4);
    	L.push_back(p5);
    	L.push_back(p6);
    	L.push_back(p7);
    
    	//需求  打印数据  按照年龄降序输出
    	//对于自定义数据类型，必须要指定排序规则
    	L.sort(myComparePerson);
    
    	for (list<Person>::iterator it = L.begin(); it != L.end(); it++)
    	{
    		cout << "姓名：" << it->m_Name << " 年龄：" << it->m_Age << "身高：" << it->m_Height << endl;
    	}
    
    	cout << "************************************" << endl;
    
    	//删除F
    	L.remove(p6);
    	for (list<Person>::iterator it = L.begin(); it != L.end(); it++)
    	{
    		cout << "姓名：" << it->m_Name << "年龄：" << it->m_Age << "身高：" << it->m_Height << endl;
    	}
    }
    
    int main()
    {
    	//test01();
    	//test02();
    	//test03();
    	//test04();
    	test05();
    	system("pause");
    	return 0;
    }

### 3.7 set/multiset容器 ###

Set的特性是：所有元素都会根据元素的键值自动被排序。Set的元素不像map那样可以同时拥有实值和键值，set的元素即是键值又是实值。Set不允许两个元素有相同的键值。

**我们不可以通过set的迭代器改变set元素的值**，因为set元素值就是其键值，关系到set元素的排序规则。如果任意改变set元素值，会严重破坏set组织。换句话说，set的iterator是一种const\_iterator.

set拥有和list某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。

multiset特性及用法和set完全相同，唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树，红黑树为平衡二叉树的一种。

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<string>
    using namespace std;
    //set multiset头文件
    #include<set>
    
    /*
    3.7.2.1 set构造函数
    set<T> st;//set默认构造函数：
    mulitset<T> mst; //multiset默认构造函数:
    set(const set &st);//拷贝构造函数
    3.7.2.2 set赋值操作
    set& operator=(const set &st);//重载等号操作符
    swap(st);//交换两个集合容器
    3.7.2.3 set大小操作
    size();//返回容器中元素的数目
    empty();//判断容器是否为空
    
    3.7.2.4 set插入和删除操作
    insert(elem);//在容器中插入元素。
    clear();//清除所有元素
    erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
    erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
    erase(elem);//删除容器中值为elem的元素。
    */
    
    void printSet(set<int>&s)
    {
    	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    	{
    		cout << *it << " ";
    	}
    	cout << endl;
    }
    void test01()
    {
    	set<int>s1;
    	//关联式容器  自动从小到大排序
    	s1.insert(5);
    	s1.insert(1);
    	s1.insert(9);
    	s1.insert(3);
    	s1.insert(7);
    
    	printSet(s1);
    
    	if (s1.empty())
    	{
    		cout << "空" << endl;
    	}
    	else
    	{
    		cout << "大小为："<< s1.size() << endl;
    	}
    
    	s1.erase(s1.begin());
    
    	s1.erase(3);
    
    	printSet(s1);
    }
    
    /*
    3.7.2.5 set查找操作
    find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
    count(key);//查找键key的元素个数
    lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
    upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
    equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
    */
    void test02()
    {
    	set<int>s1;
    	s1.insert(5);
    	s1.insert(1);
    	s1.insert(9);
    	s1.insert(3);
    	s1.insert(7);
    	//对于set没有value  key就是value
    
    	set<int>::iterator pos = s1.find(2);
    	//判断是否找到
    	if (pos != s1.end())
    	{
    		cout << "找到了，值为：" << *pos << endl;
    	}
    	else
    	{
    		cout << "没找到" << endl;
    	}
    
    	//count(key);//查找键key的元素个数 结果为0或为1
    	int num = s1.count(2);
    	cout << "1的个数为：" << num << endl;
    	
    	//lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
    	set<int>::iterator it = s1.lower_bound(3); //10就是没找到
    	if (it != s1.end())
    	{
    		cout << "找到了lower_bound(3)的值为：" << *it << endl;
    	}
    	else
    	{
    		cout << "未找到" << endl;
    	}
    
    	//upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
    	set<int>::iterator it2 = s1.upper_bound(3);
    	if (it != s1.end())
    	{
    		cout << "找到了upper_bound(3)的值为：" << *it2 << endl;
    	}
    	else
    	{
    		cout << "未找到" << endl;
    	}
    
    	//equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
    	//上下限就是 lower_bound upper_bound
    	pair<set<int>::iterator, set<int>::iterator> ret = s1.equal_range(3);
    	//获取第一个值
    	if (ret.first != s1.end())
    	{
    		cout << "找到equal_range中lower_bound的值：" << *(ret.first) << endl;
    	}
    	else
    	{
    		cout << "没找到" << endl;
    	}
    
    	//获取第二个值
    	if (ret.second != s1.end())
    	{
    		cout << "找到equal_range中upper_bound的值：" << *(ret.second) << endl;
    	}
    	else
    	{
    		cout << "没找到" << endl;
    	}
    }
    
    //set容器不允许插入重复的键值
    void test03()
    {
    	set<int>s1;
    	pair<set<int>::iterator, bool> ret = s1.insert(10);
    	if (ret.second)
    	{
    		cout << "插入成功" << endl;
    	}
    	else
    	{
    		cout << "插入失败" << endl;
    	}
    	ret = s1.insert(10);
    	if (ret.second)
    	{
    		cout << "第二次插入成功" << endl;
    	}
    	else
    	{
    		cout << "第二次插入失败" << endl;
    	}
    	printSet(s1);
    	
    	//multiset允许插入重复值
    	multiset<int> mul;
    	mul.insert(10);
    	mul.insert(10);  //插入均成功，因为multiset不返回bool值
    }
    
    //指定set排序规则从大到小
    //仿函数
    class myCompare
    {
    public:
    	//重载
    	bool operator()(int v1, int v2)
    	{
    		return v1 > v2;
    	}
    };
    
    
    //set容器排序
    void test04()
    {
    	set<int, myCompare>s1;
    	s1.insert(5);
    	s1.insert(1);
    	s1.insert(9);
    	s1.insert(3);
    	s1.insert(7);
    
    	//printSet(s1);  此时类型不是int  需重新写打印函数
    	//从大到小排序
    	//在插入之前就指定规则
    
    	for (set<int, myCompare>::iterator it = s1.begin(); it != s1.end(); it++)
    	{
    		cout << *it << " ";
    	}
    	cout << endl;
    }
    
    //自定义数据类型
    class Person
    {
    public:
    	Person(string name, int age)
    	{
    		this->m_Name = name;
    		this->m_Age = age;
    	}
    	string m_Name;
    	int m_Age;
    };
    
    class myComparePerson
    {
    public:
    	bool operator()(const Person &p1, const Person &p2)
    	{
    		if (p1.m_Age > p2.m_Age)
    		{
    			return true;
    		}
    		else
    		{
    			return false;
    		}
    	}
    };
    
    void test05()
    {
    	set<Person,myComparePerson>s1;
    	Person p1("A", 1);
    	Person p2("B", 2);
    	Person p3("C", 3);
    	Person p4("D", 4);
    
    	s1.insert(p1);
    	s1.insert(p2);
    	s1.insert(p3);
    	s1.insert(p4);
    
    	//插入自定义数据类型  上来就制定好排序规则
    
    	//显示
    	for (set<Person, myComparePerson>::iterator it = s1.begin(); it != s1.end(); it++)
    	{
    		cout << "姓名：" << (*it).m_Name << "年龄：" << (*it).m_Age << endl;
    	}
    }
    
    int main()
    {
    	//test01();
    	//test02();
    	//test03();
    	//test04();
    	test05();
    	system("pause");
    	return 0;
    }

### 3.8 map/multimap容器 ###

Map的特性是，所有元素都会根据元素的键值自动排序。Map所有的元素都是pair,同时拥有实值和键值，pair的第一元素被视为键值，第二元素被视为实值，map不允许两个元素有相同的键值。

我们不可以通过map的迭代器改变map的键值，因为map的键值关系到map元素的排列规则，任意改变map键值将会严重破坏map组织。修改元素的实值是可以的。

Map和list拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。

Multimap和map的操作类似，唯一区别multimap键值可重复。

Map和multimap都是以红黑树为底层实现机制。

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<map>
    using namespace std;
    
    /*
    3.8.2.1 map构造函数
    map<T1, T2> mapTT;//map默认构造函数:
    map(const map &mp);//拷贝构造函数
    
    
    3.8.2.2 map赋值操作
    map& operator=(const map &mp);//重载等号操作符
    swap(mp);//交换两个集合容器
    
    3.8.2.3 map大小操作
    size();//返回容器中元素的数目
    empty();//判断容器是否为空
    3.8.2.4 map插入数据元素操作
    map.insert(...); //往容器插入元素，返回pair<iterator,bool>
    map<int, string> mapStu;
    // 第一种 通过pair的方式插入对象
    mapStu.insert(pair<int, string>(3, "小张"));
    // 第二种 通过make_pair的方式插入对象
    mapStu.inset(make_pair(-1, "校长"));
    // 第三种 通过value_type的方式插入对象
    mapStu.insert(map<int, string>::value_type(1, "小李"));
    // 第四种 通过数组的方式插入值
    mapStu[3] = "小刘";
    mapStu[5] = "小王";
    */
    
    void test01()
    {
    	map<int, int> m;
    
    	//插入值
    	//4种方式
    	m.insert(pair<int, int>(1, 10));
    
    	//第二种 推荐
    	m.insert(make_pair(2, 20));
    
    	//第三种  不推荐
    	m.insert(map<int, int>::value_type(3, 30));
    
    	//第四种  如果保证key存在，那么可以通过[]去访问
    	m[4] = 40;
    
    	m[5];  //默认为0
    
    	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
    	{
    		cout << "key=" << it->first << "  value=" << it->second << endl;
    	}
    
    	if (m.empty())
    	{
    		cout << "空" << endl;
    	}
    	else
    	{
    		cout << "size=" << m.size() << endl;
    	}
    }
    
    /*
    3.8.2.5 map删除操作
    clear();//删除所有元素
    erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
    erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
    erase(keyElem);//删除容器中key为keyElem的对组。
    3.8.2.6 map查找操作
    find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；/若不存在，返回map.end();
    count(keyElem);//返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
    lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
    upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
    equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
    */
    
    void test02()
    {
    	map<int, int> m;
    	m.insert(pair<int, int>(1, 10));
    	m.insert(make_pair(2, 20));
    	m.insert(map<int, int>::value_type(3, 30));
    	m[4] = 40;
    
    	m.erase(1);
    	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
    	{
    		cout << "key=" << it->first << "  value=" << it->second << endl;
    	}
    
    	map<int, int>::iterator pos = m.find(2);
    	if (pos != m.end())
    	{
    		cout << "找到了 key=" << pos->first << "  value=" << pos->second << endl;
    	}
    	else
    	{
    		cout << "未找到" << endl;
    	}
    
    	int num = m.count(3); //map的count要么 0  1
    	cout << "num=" << num << endl;
    
    	//lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
    	map<int, int>::iterator ret = m.lower_bound(3);
    	if (ret != m.end())
    	{
    		cout << "lower_bound中的key" << ret->first << " value: " << ret->second << endl;
    	}
    	else
    	{
    		cout << "没找到" << endl;
    	}
    
    	//upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
    	
    	ret = m.upper_bound(3);
    	if (ret != m.end())
    	{
    		cout << "upper_bound中的key" << ret->first << " value: " << ret->second << endl;
    	}
    	else
    	{
    		cout << "没找到" << endl;
    	}
    
    
    	//equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
    	pair<map<int, int>::iterator, map<int, int>::iterator> ret2 = m.equal_range(3);
    	if (ret2.first != m.end())
    	{
    		cout << "找到了equal_range中的lower_bound的key" << ret2.first->first << " value=" << ret2.first->second << endl;
    	}
    	else
    	{
    		cout << "未找到" << endl;
    	}
    	if (ret2.second != m.end())
    	{
    		cout << "找到了equal_range中的upper_bound的key" << ret2.second->first << " value=" << ret2.second->second << endl;
    	}
    	else
    	{
    		cout << "未找到" << endl;
    	}
    }
    
    //指定排序规则
    class myCompare
    {
    public:
    	bool operator()(int v1, int v2)
    	{
    		return v1 > v2;
    	}
    };
    void test03()
    {
    	//从大到小排序
    	map<int, int> m;
    	m.insert(pair<int, int>(1, 10));
    	m.insert(make_pair(2, 20));
    	m.insert(map<int, int>::value_type(3, 30));
    	m[4] = 40;
    
    	for (map<int, int, myCompare>::iterator it = m.begin(); it != m.end(); it++)
    	{
    		cout << "key: " << it->first << " value: " << it->second << endl;
    	}
    }
    
    int main()
    {
    	//test01();
    	//test02();
    	test03();
    	system("pause");
    	return 0;
    }

**pair对组**

对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有属性first和second访问。

类模板：template <class T1, class T2> struct pair.

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<string>
    using namespace std;
    
    //创建对组
    void test01()
    {
    	//第一种
    	pair<string, int> p(string("Tom"), 100);
    
    	//取值
    	cout << "姓名：" << p.first << endl;
    	cout << "年龄：" << p.second << endl;
    
    	//第二种创建
    	pair<string, int>p2 = make_pair("Jerry", 200);
    
    	//取值
    	cout << "姓名：" << p2.first << endl;
    	cout << "年龄：" << p2.second << endl;
    
    }
    
    int main()
    {
    	test01();
    	system("pause");
    	return 0;
    }

STL容器使用时机

1.  vector的使用场景：比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次的记录，上上次的记录，但却不会去删除记录，因为记录是事实的描述。
2.  deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，尾端的快速添加。如果采用vector，则头端移除时，会移动大量的数据，速度慢。

vector与deque的比较：

1）vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置 却是不固定的。

2）如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。

3）deque支持头部的快速插入与快速移除，这是deque的优点。

*  list的使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置元素的移除插入。
 *  set的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分的顺序排列。
 *  map的使用场景：比如按ID号存储十万个用户，想要快速要通过ID查找对应的用户。二叉树的查找效率，这时就体现出来了。如果是vector容器，最坏的情况下可能要遍历完整个容器才能找到该用户。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70]: /images/20211228/e85c6cda5a56496a9cf0fa6d7eed5e19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1]: /images/20211228/11dd5dc6170a459fbe46ac1fef3237dd.png
[Link 1]: http://baike.baidu.com/view/1223079.htm
[Link 2]: http://baike.baidu.com/view/2820182.htm
[Link 3]: http://baike.baidu.com/view/38785.htm
[Link 4]: http://baike.baidu.com/view/159417.htm
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2]: /images/20211228/4386cc3eec3e4faa8bee6894bcbc78f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3]: /images/20211228/03dbab114d614103b1e0cf01ea520654.png