C++ - STL标准库_c++ stl标准库

1.C++ STL标准库简介

长久以来，软件界一直希望建立一种可重复利用的东西，以及一种得以制造出”可重复运用的东西”

的方法，从函数(functions)，类别(classes),函数库(function libraries),类别库(class libraries)、各种

组件，从模块化设计，到面向对象(object oriented )，为的就是复用性的提升。

复用性必须建立在某种标准之上。但是在许多环境下，就连软件开发最基本的数据结构(data

structures) 和算法(algorithm)都未能有一套标准。大量程序员被迫从事大量重复的工作，竟然是为

了完成前人已经完成而自己手上并未拥有的程序代码，这不仅是人力资源的浪费，也是挫折与痛苦

的来源。

为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹

性、交互操作性(相互合作性,interoperability),诞生了STL。

STL(Standard Template Library,标准模板库)，是惠普实验室开发的一系列软件的统称。现在主要

出现在 c++中，但是在引入 c++之前该技术已经存在很长时间了。

STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator)。

容器和算法之间通过迭代器进行无缝连接。STL 几乎所有的代码都采用了模板类或者模板函数，这

相比传统的由函数和类组成的库来说提供了更好的代码重用机会。

STL(Standard Template Library)标准模板库,在我们 c++标准程序库中隶属于 STL 的占到了 80%以

上。

2.STL容器使用时机

vector的使用场景：比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次的记

录，上上次的记录，但却不会去删除记录，因为记录是事实的描述。

deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，

尾端的快速添加。如果采用vector，则头端移除时，会移动大量的数据，速度慢。

vector与deque的比较：

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

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

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

list的使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置元素的移

除插入。

set的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分的顺序排列。

map的使用场景：比如按ID号存储十万个用户，想要快速要通过ID查找对应的用户。二叉树的查找

效率，这时就体现出来了。如果是vector容器，最坏的情况下可能要遍历完整个容器才能找到该用

户。
 

3.vector容器

vector的数据安排以及操作方式，与array非常相似，两者的唯一差别在于空间的运用的灵活性。

Array是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，可以，一切琐碎得由

自己来，首先配置一块新的空间，然后将旧空间的数据搬往新空间，再释放原来的空间。

Vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此vector的

运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就要

求一个大块头的array了。

Vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦vector旧空间

满了，如果客户每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓的扩

充空间(不论多大)，一如刚所说，是”配置新空间-数据移动-释放旧空间”的大工程,时间成本很高，

应该加入某种未雨绸缪的考虑，稍后我们便可以看到vector的空间配置策略。

基本使用：

#include "stdafx.h"
#include <iostream>
 
#include <vector>//动态数组
using namespace std;
 
int main()
{
   vector<int>  v1;//构造一个空的vector
   cout << "容量为："<<v1.capacity() << "     元素个数: " << v1.size() << endl;
 
   vector<int>  v2(5);//构造一个空间大小为5，并且元素为5个（有默认值）的vector
   cout << "容量为：" << v2.capacity() << "     元素个数: " << v2.size() <<"	   v2[0]:"<<v2[0]<< endl;
 
   vector<int>  v3(5,111);//构造一个空间大小为5，并且元素为5个（每个元素初始值为111）的vector
   cout << "容量为：" << v3.capacity() << "     元素个数: " << v3.size() << "	   v3[0]:" << v3[0] << endl;
 
   vector<int>  v4(v3);//拷贝构造vector
   cout << "容量为：" << v4.capacity() << "     元素个数: " << v4.size() << "	   v4[0]:" << v4[0] << endl;
 
   //像数组一样的访问vector
   v2[0] = 1;//vector重载了[]运算符
   v2[1] = 2;
   v2[2] = 3;
   v2.at(3) = 4;
   v2.at(4) = 5;
 
   for (size_t i = 0; i < v2.size(); i++)
   {
   	//cout << v2[i] << "	";
   	//cout << v2.at(i)<< "	";
        cout << &v2[i] << "	";//输出地址，说明存储空间是连续的
   }
   cout << endl;
 
   return 0;
}

迭代器使用：

#include<iostream>
#include<vector>//动态数组
using namespace std;
 
template<class T>
void   Print(T  begin, T  end)
{
   //此处编写代码
   for (T p = begin; p != end; ++p)
   {
   	cout << *p << "		";
   }
   cout << endl;
}
 
int main()
{
   vector<int>  v(5);//构造一个空间大小为5，并且元素为5个（有默认值）的vector
 
   //像数组一样的访问vector
   v[0] = 1;//vector重载了[]运算符
   v[1] = 2;
   v[2] = 3;
   v.at(3) = 4;
   v.at(4) = 5;
 
   for (size_t i = 0; i < v.size(); i++)
   {
   	cout << v[i] << "	";
   }
   cout << endl;
 
   {
   //验证vector的迭代器是随机访问迭代器（支持++  、-- 、 +n、  +=n 、-=n 、 -n 、 *、[]   ）
   //random_access_iterator
   cout << typeid(vector<int>::iterator::iterator_category).name() << endl;
 
   vector<int>::iterator  it = v.begin();//begin返回v的第一个元素的迭代器
   cout << "v开头的迭代器指向的元素值：" << *it << endl;
 
   ++it;//it的值改变
   cout << "v第二个的元素值：" << *it << endl;
 
   cout << "v第四个的元素值：" << *(it + 2) << endl;//此刻这里的it还是指向第二个，没变
 
   it -= 1;//it的值改变
   cout << "v第一个的元素值：" << *it << endl;
 
   cout << "v第五个的元素值：" << it[4] << endl;//这里的it没变
}
   //可以改变指向元素的值
   vector<int>::iterator  it = v.begin();
   *it = 111;
   //使用迭代器遍历元素
   for (vector<int>::iterator  it = v.begin() ;   it!=v.end(); it++)
   {
   	cout << *it << "	";
   }
   cout << endl;
 
   //常迭代器  指向的元素值不可改变,  类似  const int  *p; 
   vector<int>::const_iterator   it2 = v.cbegin();
   //*it2 = 111;
 
   //反向迭代器
   for (vector<int>::reverse_iterator  it3 = v.rbegin(); it3 != v.rend(); it3++)
   {
   	cout << *it3 << "	";
   }
   cout << endl;
 
   //测试我们自己实现的Print算法,迭代器架起了 算法与容器之间的桥梁
   Print<vector<int>::iterator>(v.begin(), v.end());
   Print(v.begin(), v.end());
   Print<vector<int>::reverse_iterator>(v.rbegin(), v.rend());
 
   return 0;
}

添加、删除、插入元素：

#include<iostream>
#include<vector>
using namespace  std;
 
int main()
{
   vector<int >   v;//定义一个空的动态数组
   cout << "容量:" << v.capacity() << "		元素个数:" << v.size() << endl;
 
   //往尾部插入元素   //    1
   v.push_back(1);
   cout << "容量:" << v.capacity() << "		元素个数:" << v.size() << endl;
    
   v.push_back(2);     //      1  2 
   cout << "容量:" << v.capacity() << "		元素个数:" << v.size() << endl;
 
   //向某一个迭代器指向的位置插入
   v.insert(v.begin(), 3);//    3  1   2
   cout << "容量:" << v.capacity() << "		元素个数:" << v.size() << endl;
 
   //向某一个迭代器指向的位置插入2个值为4的元素
   v.insert(v.end()-1 ,  2, 4);//    3  1      4  4  2
   cout << "容量:" << v.capacity() << "		元素个数:" << v.size() << endl;
 
   //使用迭代器遍历
   for (vector<int >::const_iterator   it =  v.cbegin();   it!=  v.cend(); it++)
   {
   	cout << *it << "		";
   }
   cout << endl;
 
   //访问第一个元素
   cout <<"front		" <<v.front() << endl;
   //访问最后一个元素
   cout << "back		" << v.back() << endl;
   //访问某一个下标的元素
   cout << "at			" << v.at(3) << endl;
 
   //删除最后一个元素
   v.pop_back();
   cout << "容量:" << v.capacity() << "		元素个数:" << v.size() << endl;
 
   //删除开头的元素
   v.erase(v.begin());
   cout << "容量:" << v.capacity() << "		元素个数:" << v.size() << endl;
 
   //删除结尾的元素, end()指向最后一个元素的下一个
   v.erase(v.end()-1);
   cout << "容量:" << v.capacity() << "		元素个数:" << v.size() << endl;
 
   //使用迭代器遍历
   for (vector<int >::const_iterator it = v.cbegin(); it != v.cend(); it++)
   {
   	cout << *it << "		";
   }
   cout << endl;
 
   //删除所有元素，不会清除容量
   v.clear();
   cout << "容量:" << v.capacity() << "		元素个数:" << v.size() << endl;
 
   /*
   当size和capacity相等时继续添加数据，否则vector会扩容，
   每次扩容都是增加当前空间的1/2(第一次除外);
   */
   {
   	vector<int>  v;
 
   	cout << "------------------------capacity容量随元素个数size增加的规律----------------------------" << endl;
   	for (int i = 0; i < 50; i++)
   	{
   		v.push_back(i);
   		cout << "v的容量：" << v.capacity() << "  元素个数:" << v.size() << endl;
   	}
   }
 
   return 0;
}

 vector常用赋值操作：

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
vector& operator=(const vector  &vec);//重载等号操作符
swap(vec);// 将vec与本身的元素互换。

vector大小操作:

size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。
capacity();//容器的容量
reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。

vector数据存取操作:

at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
operator[];//返回索引idx所指的数据，越界时，运行直接报错
front();//返回容器中第一个数据元素
back();//返回容器中最后一个数据元素

vector插入和删除操作:

insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
push_back(ele); //尾部插入元素ele
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
erase(const_iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素

vector排序：

sort(nums.begin(),nums.end());

定义二维vector：

vector<vector<int>> v;

创建m*n的二维vector：

vector<vector <int> >nums(m ,vector<int>(n)); //m*n的二维vector

初始化二维数组：

vector<vector<int>> nums(m ,vector<int>(n,0)); //m*n的二维vector，所有元素为0

二维数组遍历：

int m = nums.size(),n = nums[0].size();
for(int i = 0; i < m; i++){
    for(int j = 0; j < n; j++){
        cout<<nums[i][j]<<endl;
    }
}

4.deque容器

Vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。

所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector容器也可以

在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。

deque容器实现原理:

Deque容器是连续的空间，至少逻辑上看来如此，连续现行空间总是令我们联想到array和

vector,array无法成长，vector虽可成长，却只能向尾端成长，而且其成长其实是一个假象，事实上

(1) 申请更大空间 (2)原数据复制新空间 (3)释放原空间 三步骤，如果不是vector每次配置新的空间

时都留有余裕，其成长假象所带来的代价是非常昂贵的。

Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便

配置一段连续定量的空间，串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连

续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮

回，代价就是复杂的迭代器架构。

既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计

及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list都多得多。

Deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续

的内存空间，其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称

作缓冲区。缓冲区才是deque的存储空间的主体。

基本使用 :

#include<iostream>
 
#include<deque>
using namespace  std;
 
int main()
{
   //空的双端队列
   deque<int> d;
   cout << "元素个数" << d.size() << endl;
 
   deque<int> d2(5);//指定元素个数，默认值为类型默认值
   cout << "元素个数" << d2.size() <<"   "<<d2[0]<< endl;
 
   deque<int> d3(5,111);//指定元素个数，每一个指定元素值111
   cout << "元素个数" << d3.size() << "   " << d3[4] << endl;
 
   deque<int>  d4(d3);//拷贝构造
   cout << "元素个数" << d4.size() << "   " << d4[3] << endl;
 
   //像数组一样的访问元素（内存空间并不是连续的）
   d2[0] = 1;
   d2[1] = 2;
   d2[2] = 3;
   d2.at(3) = 4;
 
   for (size_t i = 0; i < d2.size(); i++)
   {
   	cout << d2[i] << "		";
   }
   cout << endl;
 
   //验证deque的内存空间不是连续的
   {
   	deque<int>  d;
 
   	for (size_t i = 0; i < 20; i++)
   	{
   		d.push_back(i);
   		cout << "元素" << d[i] << " " << &d[i] << '\t';
 
   		if ((i + 1) % 4 == 0)cout << endl;
   	} 
   	cout << endl; 
   }
 
   return 0;
}

 迭代器使用：

#include<iostream>
 
#include<deque>
using namespace  std;
 
template<class T>
void   Print(T  begin, T  end)
{
   for (T p = begin; p != end; ++p)
   {
   	cout << *p << "		";
   }
   cout << endl;
}
 
int main()
{
   deque<int> d2(5);//指定元素个数，默认值为类型默认值
   cout << "元素个数" << d2.size() << "   " << d2[0] << endl;
 
   //像数组一样的访问元素（内存空间并不是连续的）
   d2[0] = 1;
   d2[1] = 2;
   d2[2] = 3;
   d2.at(3) = 4;
   d2.at(4) = 5;
   for (size_t i = 0; i < d2.size(); i++)
   {
   	cout << d2[i] << "		";
   }
   cout << endl;
 
   //deque<int>::iterator是随机访问迭代器
   cout << typeid( deque<int>::iterator::iterator_category ).name() << endl;
 
   //支持++ 、--、+=n、 -=n、[]、* 、+n、-n
   
   deque<int>::iterator  it = d2.begin();//获取指向容器的第一个元素的迭代器
   cout << "begin返回的迭代器指向的元素："<<*it << endl;
 
   *it = 111;//deque<int>::iterator可以改变迭代器指向的元素值
   it++;//下一个元素，it自身改变
   cout <<"++后:"<< *it << endl;
 
   it += 2;//往后移2个位置，it自身改变，指向第4个元素
   cout << "+=2后:" << *it << endl;
 
   cout << "-3后:" << *(it-3) << endl; //  it-3代表it位置的前3个位置，it自身不变
 
   cout << "[1]后:" << it[1] << endl; //指向最后一个
 
   it = d2.begin();//置为开头
   cout << "[i]后:" << it[1] << endl; //指向第二个
 
   //const_iterator只读的迭代器
   deque<int>::const_iterator   it2 = d2.cbegin();
   //*it2 = 11111; //无法改变元素的值，只能读取，类似于 const int  *
 
   //使用迭代器正向遍历
   for (deque<int>::iterator it = d2.begin(); it !=  d2.end(); ++it)
   {
   	cout << *it << "		";
   }
   cout << endl;
 
   //使用反向迭代器反向向遍历
   for (deque<int>::reverse_iterator it = d2.rbegin(); it != d2.rend(); ++it)
   {
   	cout << *it << "		";
   }
   cout << endl;
 
   //测试自己写的算法(无需知道deque容器的内存结构，具有通用性)
   Print<deque<int>::iterator>(d2.begin(), d2.end());
   Print(d2.rbegin(), d2.rend());//自动推导 
 
   return 0;
}

添加、删除、插入元素：

#include<iostream>
 
#include<deque>
using namespace  std;
 
int main()
{
   deque<int>  d;
 
   d.push_back(1);//从尾部插入元素
   d.push_front(2);//从头部插入元素（vector没有此方法）
   d.insert(d.begin(), 3);//在迭代器位置插入
   d.insert(d.end(), 2, 4);//在迭代器位置插入2个元素值为4
 
   for ( int  i = 0; i < d.size(); i++)
   {
   	cout <<d[i]<< "		";
   }
   cout << endl;
 
   //访问元素
   //d.at(0) = 111;
   //d[4] = 555;
   cout << d.front() << endl;//返回第一个元素
   cout << d.back() << endl;//返回第一个元素
 
   //删除元素
   d.pop_back();//从尾部删除
   d.pop_front();//从头部删除（vector不提供）
 
   d.erase(d.begin());//删除某个迭代器指向的元素
 
   for (int i = 0; i < d.size(); i++)
   {
   	cout << d[i] << "		";
   }
   cout << endl;
 
   d.clear();//全部清空
 
   cout << "元素个数："<<d.size() << endl;
 
   return 0;
}

deque赋值操作：

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符 
swap(deq);// 将deq与本身的元素互换

deque大小操作：

deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果容器变短，则末尾超出容器长度的元素被删除。

deque双端插入和删除操作：

push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据

deque数据存取：

at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
front();//返回第一个数据。
back();//返回最后一个数据

deque插入操作：

insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。

deque删除操作：

clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。

5.list容器

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针

链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包

括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是

配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，

对于任何位置的元素插入或元素的移除，list永远是常数时间。

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

List容器是一个双向链表。

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

基本使用:

#include<iostream>
 
#include<list>
using namespace std;
 
int main()
{
   list<int> l;//空的双向链表
   cout << "元素个数:" << l.size() << endl;
 
   list<int> l2(5);//初始化5个元素，默认值为类型的默认值
   cout << "元素个数:" << l2.size() <<"  "<<  * (l2.begin() )<< endl;
 
   list<int> l3(5,111);//初始化5个元素，每个元素初始值为111
   cout << "元素个数:" << l3.size() << "  " << *(l3.begin()) << endl;
 
   list<int> l4( l3 );//拷贝构造
   cout << "元素个数:" << l4.size() << "  " << *(l4.begin()) << endl;
 
   //不支持[]运算符，因为效率低
   //cout << l4[0] << endl;
 
   //验证了list容器的内存空间是不连续的
   for (list<int>::iterator   it = l3.begin(); it !=l3.end(); it++)
   {
   	cout << &(*it) << "   ";
   }
   cout << endl;
 
   return 0;
}

迭代器使用:

#include<iostream>
 
#include<list>
using namespace std;
 
template<class T>
void   Print(T  begin, T  end)
{
   //此处编写代码
   for (T p = begin; p != end; ++p)
   {
   	cout << *p << "		";
   }
   cout << endl;
}
 
int main()
{ 
   list<int> l3(5, 111);//初始化5个元素，每个元素初始值为111
   cout << "元素个数:" << l3.size() << "  " << *(l3.begin()) << endl;
 
   //验证list容器的迭代器类型（5种之一）
   //双向迭代器bidirectional_iterator_tag
   cout << typeid(list<int>::iterator::iterator_category).name() << endl;
 
   //双向迭代器比随机访问迭代器弱一些，支持  ++  --   !=  ==  =  *   不支持[]  +n -n  +=n  -=n
   list<int>::iterator  it = l3.begin(); //指向容器l3的第一个元素
   cout << *it << endl;
 
   *(++it) =  222;
   *(++it) = 333;
   *(++it) = 444;
   *(++it) = 555;
   ++it;//指向最后一个元素的下一个
 
   cout <<"迭代器指向末尾的下一个"<< (it == l3.end() )<< endl;
 
   --it;//指向最后一个元素
   cout << *it << endl;
 
   //it += 3;//不支持
   //it + 3;//不支持
   //it[0];//不支持
 
   //const_iterator常迭代器，类似于 const  int  *
   list<int>::const_iterator  it2 = l3.cbegin();
   //*it2 = 1;//不能修改常迭代器指向的内容
 
   //正向遍历
   for (list<int>::iterator it = l3.begin(); it != l3.end(); it++)
   {
   	cout <<  *it << "   ";
   }
   cout << endl;
 
   //反向遍历
   for (list<int>::reverse_iterator it = l3.rbegin(); it != l3.rend(); it++)
   {
   	cout << *it << "   ";
   }
   cout << endl;
 
   //测试自己的算法(迭代器带来的好处，算法无需关系容器的具体内存结构，就可以遍历)
   Print<list<int>::iterator>(l3.begin(), l3.end());
   Print(l3.crbegin(), l3.crend());//自己推到迭代器类型
 
   return 0;
}

增加、删除、插入元素:

#include<iostream>
 
#include<list>
using namespace std;
 
int main()
{
   list<int>  l;
 
   //头部插入一个节点（list容器肯定知道头部的位置）
   l.push_front(111);
 
   //尾部插入一个节点（list容器肯定知道尾部的位置）
   l.push_back(444);
   l.push_back(555);
 
   //在某个迭代器的位置之前插入
   l.insert(l.begin(), 222);
 
   //在某个迭代器的位置之前插入n个相同值元素
   l.insert(l.begin(), 3,333);
 
   //访问链表第一个元素
   l.front() = 1;
   cout <<"第一个元素:"<< l.front() << endl; 
 
   //访问链表最后一个元素
   cout << "最后一个元素:" << l.back() << endl;
 
   for (list<int>::iterator it = l.begin();  it!= l.end(); it++)
   {
   	cout << *it << "	   ";
   }
   cout << endl;
 
   //删除链表头的元素
   l.pop_front();
 
   //删除链表尾的元素
   l.pop_back();
 
   //删除某个迭代器指向的元素
   l.erase(l.begin());
    
    //删除一段迭代器区间
   l.erase(l.begin(),l.end());
 
   //清空链表
   l.clear();
 
   for (list<int>::iterator it = l.begin(); it != l.end(); it++)
   {
   	cout << *it << "	   ";
   }
   cout << endl;
 
   return 0;
}

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值匹配的元素。

list大小操作

size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num，
若容器变长，则以默认值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num，
若容器变长，则以elem值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。

list赋值操作

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
list& operator=(const list &lst);//重载等号操作符
swap(lst);//将lst与本身的元素互换。

list数据的存取

front();//返回第一个元素。
back();//返回最后一个元素。

list反转排序

reverse();//反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。
sort(); //list排序

6.set/multiset容器

set（集合）是一种每个元素值都是唯一的有序的关联容器。

multiset（多重集合）是一种元素值 可复的、有序的 关联容器。

set/multiset容器内部结构采用红黑树（Red-Black tree）的平衡二叉树，它可以在O(logn)时间内

高效的做查找，插入和删除。

 基本使用:

#include<set>
#include<vector>
#include<iostream>
 
using namespace  std;
 
int main()
{
   //set 的特点， 值必须唯一， 有序
 
   set<int> s;//构造空的集合,默认less 升序
   cout << "元素个数" << s.size() << endl;
 
    set<int>  s2 = {3,2,5,1,4 ,3};//初始化列表
   //set<int, greater<int>>  s2 = {3,2,5,1,4 ,3};//初始化列表,降序
   cout << "元素个数" << s2.size() << endl;
 
   set<int>  s3(s2.begin(),s2.end()); //拷贝迭代器范围内的元素
   cout << "元素个数" << s3.size() << endl;
 
   //插入元素 ,成功后返回值的成员second为1，失败为0
   //cout << typeid(s2.insert(9)).name() << endl; 
   cout<< s2.insert(9).second <<endl;
 
   //重复插入元素
   cout << s2.insert(9).second << endl;
    
   vector<int> v = {6,7,8,9};
   s2.insert(v.begin(), v.end());//插入其它容器中元素的值
 
   for (set<int>::iterator   it = s2.begin(); it!=s2.end(); it++)
   {
   	cout << *it << "   ";
   }
   cout << endl;
 
   //删除值为6的元素
   s2.erase(6); 
 
   //删除迭代器指向的元素
   s2.erase(s2.begin());
 
   for (set<int>::iterator it = s2.begin(); it != s2.end(); it++)
   {
   	cout << *it << "   ";
   }
   cout << endl;
 
   //删除迭代器区间
   set<int>::iterator it = s2.begin();
   it++;	it++;	it++;
   s2.erase(s2.begin(), it);
 
   //s2.clear();//清空集合元素
 
   for (set<int>::iterator it = s2.begin(); it != s2.end(); it++)
   {
   	cout << *it << "   ";
   }
   cout << endl;
 
   //查找集合中的元素 ,找到返回指向该元素的迭代器，否则返回end()
   set<int>::iterator it2 = s2.find(99);
   if (it2 != s2.end())
   {
   	cout << "找到:" <<*it2<< endl;
   }
   else
   {
   	cout << "未找到！" << endl;
   }
 
   return 0;
}

迭代器使用

STL为set容器提供了相应的迭代器类set<T>::iterator，它是一个双向迭代器（Bidirectional

iterator），以供我们方便的访问容器内部的元素。

#include<set> 
 
#include<iostream>
using namespace  std;
 
template<class T>
void   Print(T  begin, T  end)
{
   for (T p = begin; p != end; ++p)
   {
   	cout << *p << "		";
   }
   cout << endl;
}
 
int main()
{
   //set 的特点， 值必须唯一， 有序 
   set<int>  s2 = { 3,2,5,1,4,3 };//初始化列表
    
   //输出set迭代器的类别: bidirectional_iterator_tag 双向迭代器
   cout << typeid(set<int>::iterator::iterator_category).name() << endl;
 
   //双向迭代器，支持++ --   *   !=  ==  =  不支持  []  +=n  -=n  +n  -n
   set<int>::iterator it = s2.begin();//获取第一个元素
   cout <<"第一个元素"<< *it << endl;
 
    // *it = 111;  //不可更改，说明set中元素值不可改变
   //符合逻辑，因为set中每个元素都已经根据值排列好了大小，此刻你若更改值，顺序无法保证
 
   ++it;
   cout << "第二个元素" << *it << endl;
 
   --it;
   cout <<"是否指向开头"<<  (it  ==  s2.begin())<< endl;
 
   //常迭代器，不可更改指向的元素的内容
   set<int>::const_iterator it2 = s2.cbegin();//获取第一个元素
    // *it2 = 111;  //不可更改set元素中的值
 
   //验证下， set<int>::iterator 与 set<int>::const_iterator 是一样的
   cout << typeid(set<int>::iterator ).name() << endl;
   cout << typeid(set<int>::const_iterator).name() << endl;
   
   //正向遍历
   for (set<int>::iterator it = s2.begin(); it != s2.end(); it++)
   {
   	cout << *it << "   ";
   }
   cout << endl;
 
   //反向遍历
   for (set<int>::reverse_iterator it = s2.rbegin(); it != s2.rend(); it++)
   {
   	cout << *it << "   ";
   }
   cout << endl;
 
   //测试自定义的Print算法(迭代器，算法无需关心容器的内存结构)
   Print<set<int>::iterator>(s2.begin(), s2.end());
   return 0;
}

set赋值操作

set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器

set大小操作

size();//返回容器中元素的数目
empty();//判断容器是否为空

set插入和删除操作

insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。

set查找操作

find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count(key);//查找键key的元素个数
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。

7.map/multimap容器

map（映射）是一种存储键值（key-value）对， key是唯一的、有序的 关联容器。

multimap（多重映射）是一种存储键值（key-vauekey是 允许重复的、有序的 关联容器。

map内部结构采用红黑树（Red-Black tree）平衡二叉树，它可以在O(log n)时间内高效的做查

找，插入和删除。

Map和list拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所

有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。

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

 基本使用 

#include<map>
 
#include<iostream>
using namespace  std;
 
int main()
{
   //map映射 ，  每个元素都是 key-value 键值对，  key不能重复，value可以，有序的
   map<int, string>  m;//构造空的map
   cout <<"元素个数："<< m.size() << endl;
 
   //初始化列表构造map
   map<int, string>  m2 = { {3,"CCC"} ,  {1,"AAA"} ,  {2,"BBB"} };
   cout << "元素个数：" << m2.size() << endl;
 
   //拷贝构造
   map<int, string>  m3(m2);
   cout << "元素个数：" << m3.size() << endl;
 
   //验证map容器中的元素类型   pair<int, string>
   cout << typeid(map<int, string>::value_type).name() << endl;
 
   //一对值  pair 类模板
   pair<int, float>  p1;
   p1.first = 1;
   p1.second = 2.34f;
 
   pair<int, float>  p2(2, 3.45f); //有参构造
   cout << "first: " << p2.first << "     second:" << p2.second<< endl;
 
   //使用make_pair函数构造pair
   pair<short, char>  p3 = make_pair<short, char>(3, 'A');
   //pair<short, char>  p3 = make_pair(3, 'A');//自动推导
   cout << "first: " << p3.first << "     second:" << p3.second << endl;
 
 
   map<int, string>  m4 = {   pair<int, string>( 3,"CCC" )   ,  make_pair( 2,"BBB"),  make_pair(1,"AAA"), };
   cout << "元素个数：" << m4.size() << endl;
 
   return 0;
}

插入、删除元素

#include<vector>
#include<map>
 
#include<iostream>
using namespace  std;
 
int main()
{
   //map映射 关联容器 ，  每个元素都是 key-value 键值对  pair， 
   //key不能重复，value可以， 有序的
   map<int, string>  m;//构造空的map 
 
   //插入pair
   pair<int, string>  p1(2, "BBB");
   m.insert(p1);
    
   m.insert(pair<int, string>(1, "AAA"));
 
   //可以通过insert返回值的 成员.second查看是否插入成功，true成功，false是失败
   m.insert( make_pair<int, string>(2, "bbb")); //插入重复的key, 插入失败
   m.insert(make_pair(3, "CCC")); 
 
   // 插入其它容器中迭代器范围中的元素
   vector<pair<int, string>>  v = { {3,"ccc"}, {5, "EEE"},{ 4,"DDD" },{6, "FFF"} };
   m.insert(v.begin(), v.end());
 
   //[key]= value 
   m[7] = "GGG"; //对于不存在的key， 插入，相当于 (7,"GGG") 
   m[8];  //对于不存在的key，插入，相当于 ( 8,"")
   m[2] = "bbb";// 已经存在的key，相当于是修改元素的value
 
   for (map<int, string>::iterator  it = m.begin(); it!= m.end(); ++it)
   {
   	cout << it->first << "->" << it->second.c_str() << "   ";
   }
   cout << endl;
 
   //查找key为3的元素，成功返回迭代器，失败返回end()
   {
   	map<int, string>::iterator  it = m.find(33);
   	if (it != m.end())
   	{
   		cout << "找到：" << it->first << "->" << it->second.c_str() << endl;
   	}
   	else
   	{
   		cout << "未找到!" << endl;
   	}
   }
 
   //[key] 如果key存在，直接返回value
   //陷阱 ,如果key不存在，他会自动插入key，value为默认值再返回
   cout << "[key] "<< m[33].c_str() << endl;
    
   for (map<int, string>::iterator it = m.begin(); it != m.end(); ++it)
   {
   	cout << it->first << "->" << it->second.c_str() << "   ";
   }
   cout << endl;
 
   //删除key为3的元素
   m.erase(3); 
 
   //删除某个迭代器指向的元素
   m.erase(m.begin());
 
   //删除迭代器区间[)的元素
   map<int, string>::iterator it = m.begin();
   ++it; ++it; ++it; //往后移动
   m.erase(m.begin(), it); 
 
   //删除所有元素
   m.clear();
 
   for (map<int, string>::iterator it = m.begin(); it != m.end(); ++it)
   {
   	cout << it->first << "->" << it->second.c_str() << "   ";
   }
   cout << endl;
 
   return 0;
}

迭代器使用

STL为map容器提供了相应的迭代器类map<T1,T2>::iterator，它是一个双向迭代器

（Bidirectional iterator）以供我们方便的访问容器内部的元素。

#include<map>
 
#include<iostream>
using namespace  std;
 
template<class T>
void   Print(T  begin, T  end)
{
   for (T p = begin; p != end; ++p)
   {
   	cout << *p << "		";
   }
   cout << endl;
}
 
//为   map<int, string>元素类型提供 <<运算符重载
ostream  &  operator<<(ostream  &  os, map<int, string>::value_type   &p)
{
   cout << p.first << "->" << p.second.c_str() ;
   return  os;
}
 
int main()
{
   //map映射 关联容器 ，  每个元素都是 key-value 键值对  pair， 
   //key不能重复，value可以， 有序的
   map<int, string>  m;//构造空的map  
   m.insert(make_pair(3, "CCC"));
   m.insert(make_pair(1, "AAA"));	m.insert(make_pair(2, "BBB")); 
    
   //map<int, string>::iterator是双向迭代器 bidirectional_iterator_tag
   cout << typeid(map<int, string>::iterator::iterator_category).name() << endl;
 
   //双向迭代器，支持  ++  --  *   =    !=   == ，  不支持   [] 、+=n， -=n  +n  -n
   map<int, string>::iterator  it = m.begin();
   // it->first = 111; //map的key值不允许修改, map是按照key排好序的，如果你更改key值，会打乱顺序
    it->second = "aaa"; //map的value允许修改
 
    ++it;
    cout << it->first << "->" << it->second.c_str() <<endl;
 
    --it;
    cout << "回到开头"<<(it == m.begin()) << endl;
      
    //const_iterator 指向的元素内容不可修改
    map<int, string>::const_iterator  it2 = m.begin();
   // it2->first = 111; //均不可修改
   // it2->second = "aaa";//均不可修改
 
    //查看两种iterator的真实类型
    cout << typeid(map<int, string>::iterator).name() << endl;
    cout << typeid(map<int, string>::const_iterator).name() << endl;
     
    //正向遍历
   for (map<int, string>::iterator it = m.begin(); it != m.end(); ++it)
   {
   	cout << it->first << "->" << it->second.c_str() << "   ";
   }
   cout << endl;
      
   //反向遍历
   for (map<int, string>::reverse_iterator it = m.rbegin(); it != m.rend(); ++it)
   {
   	cout << it->first << "->" << it->second.c_str() << "   ";
   }
   cout << endl;
 
   //使用Print ，无需知道map的内部结构，通过迭代器就可以遍历map的所有元素
 
   Print<map<int, string>::iterator>(m.begin(), m.end());
 
   return 0;
}

map赋值操作

map& operator=(const map &mp);//重载等号操作符
swap(mp);//交换两个集合容器

map大小操作

size();//返回容器中元素的数目
empty();//判断容器是否为空

map插入数据元素操作

map.insert(...); //往容器插入元素，返回pair<iterator,bool>
map<int, string> mapStu;
// 第一种 通过pair的方式插入对象
mapStu.insert(pair<int, string>(3, "小张"));
// 第二种 通过pair的方式插入对象
mapStu.inset(make_pair(-1, "校长"));
// 第三种 通过value_type的方式插入对象
mapStu.insert(map<int, string>::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";

map删除操作

clear();//删除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(keyElem);//删除容器中key为keyElem的对组。

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相等的上下限的两个迭代器。