1.STL容器简介

1.1STL介绍

STL是什么？STL（Standard Template Library）标准模板库的简称，是由惠普开发的一系列软件的总称，STL 现在是 C++的一部分，已经被构建于编译系统之内，所以不需要再引入。STL以模板类和模版函数的形式为程序员提供了各种数据结构和算法的实现，程序员吐过能够充分的利用STL，可以在代码空间、执行时间和编码效率上获得极大的好处。

STL大致可以分为三大类：容器（container）、算法（algorithm）、迭代器（iterator）。

STL容器是一些模版类，提供了多种组织数据的常用方法，例如：vector（向量，类似于数组）、list（列表，类似于链表）、deque（双向队列）、set（集合）、map（映像）、stack（栈）、queue（队列）、priority_queue（优先队列）等，通过模版的参数我们可以指定容器中的元素类型。

STL算法是一些模版函数，提供了相当多的有用的算法和操作，从简单的for_each（遍历）到复杂的stable_sort（稳定排序）。

STL迭代器是对C中的指针的一般化，用来将算法和容器联系起来。几乎所有的STL算法都是通过迭代器来存取元素序列进行工作的，而STL中的每一个容器也都定义了其本身所专有的迭代器，用以存取容器中的元素。有趣的是，普通的指针也可以像迭代器一般的工作。

1.2容器分类

• 1、顺序容器：是一种各元素之间有顺序关系的线性表，是一种线性结构的可序群集。顺序性容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。顺序容器的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定。顺序容器包括：vector(向量)、list（列表）、deque（队列）。

• 2、关联容器：关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。但是关联式容器提供了另一种根据元素特点排序的功能，这样迭代器就能根据元素的特点“顺序地”获取元素。元素是有序的集合，默认在插入的时候按升序排列。关联容器包括：map（集合）、set（映射）、multimap（多重集合）、multiset（多重映射）。

• 3、容器适配器：本质上，适配器是使一种不同的行为类似于另一事物的行为的一种机制。容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作“它保存一个容器，这个容器再保存所有元素”。STL 中包含三种适配器：栈stack 、队列queue 和优先级队列priority_queue 。

容器类自动申请和释放内存，因此无需new和delete操作。

2.向量vector

2.1定义和初始化

如果没有指定元素的初始化式，那么标准库将自行提供一个元素初始值进行，具体值为何，取决于存储在vector 中元素的数据类型；如果为int型数据，那么标准库将用 0 值创建元素初始化式；如果 vector 保存的是含有构造函数的类类型（如 string）的元素，标准库将用该类型的默认构造函数创建元素初始化式；元素类型可能是没有定义任何构造函数的类类型。这种情况下，标准库仍产生一个带初始值的对象，这个对象的每个成员进行了值初始化。

#include <vector>
using std::vector;
 
vector<int> vec1;    //默认初始化，vec1为空
vector<int> vec2(vec1);  //使用vec1初始化vec2
vector<int> vec3(vec1.begin(),vec1.end());//使用vec1初始化vec2
vector<int> vec4(10);    //10个值为0的元素
vector<int> vec5(10,4);  //10个值为4的元素
vector<string> vec6(10,"null");    //10个值为null的元素
vector<string> vec7(10,"hello");  //10个值为hello的元素

2.2常用操作

Vector的下标操作符接受一个值，并返回vector中的该对应位置的元素。Vector元素的位置从0开始，使用vector::size_type作为下标的类型。
也就是说，必须是已存在的元素才能用下标操作符进行索引，通过下标操作符进行赋值时，不会添加任何元素。下标操作符[ ]仅能提取确实已存在的元素。
下标操作不能添加元素，只能获取已存在的元素，想在vector中插入元素，使用push_back()函数。

vec1.push_back(100);            //添加元素
int size = vec1.size();         //元素个数
bool isEmpty = vec1.empty();    //判断是否为空
cout<<vec1[0]<<endl;        //取得第一个元素
vec1.insert(vec1.end(),5,3);    //从vec1.back位置插入5个值为3的元素
vec1.pop_back();              //删除末尾元素
vec1.erase(vec1.begin(),vec1.end());//删除之间的元素，其他元素前移
cout<<(vec1==vec2)?true:false;  //判断是否相等==、！=、>=、<=...
vector<int>::iterator iter = vec1.begin();    //获取迭代器首地址
vector<int>::const_iterator c_iter = vec1.begin();   //获取const类型迭代器
vec1.clear();                 //清空元素

2.3遍历操作

//下标法(vector的特有访问方法，一般容器只能通过迭代器访问)
 int length = vec1.size();
 for(int i=0;i<length;i++)
 {
    cout<<vec1[i];
 }
 cout<<endl<<endl;
 //迭代器法
 vector<int>::const_iterator iterator = vec1.begin();
 for(;iterator != vec1.end();iterator++)
 {

    cout<<*iterator；

 }

3.列表list

3.1定义和初始化

list是stl实现的双向链表，与向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢。

#include <list>#使用时需要添加头文件
list<int> lst1;          //创建空list
list<int> lst2(3);       //创建含有三个元素的list
list<int> lst3(3,2); //创建含有三个元素的值为2的list
list<int> lst4(lst2);    //使用lst2初始化lst4
list<int> lst5(lst2.begin(),lst2.end());  //同lst4

3.2常用操作

lst1.assign(lst2.begin(),lst2.end());  //分配值
lst1.push_back(10);                    //添加值
lst1.pop_back();                   //删除末尾值
lst1.begin();                      //返回首值的迭代器
lst1.end();                            //返回尾值的迭代器
lst1.clear();                      //清空值
bool isEmpty1 = lst1.empty();          //判断为空
lst1.erase(lst1.begin(),lst1.end());                        //删除元素
lst1.front();                      //返回第一个元素的引用
lst1.back();                       //返回最后一个元素的引用
lst1.insert(lst1.begin(),3,2);         //从指定位置插入3个值为2的元素
lst1.rbegin();                         //返回第一个元素的前向指针
lst1.remove(2);                        //相同的元素全部删除
lst1.reverse();                        //反转
lst1.size();                       //含有元素个数
lst1.sort();                       //排序
lst1.unique();                         //删除相邻重复元素

3.3遍历操作

  for(list<int>::const_iteratoriter = lst1.begin();iter != lst1.end();iter++)
    {
      cout<<*iter;
    }
    cout<<endl;

3.4实例程序

#include <iostream>
#include <list>
#include <numeric>
#include <algorithm>
#include <windows.h>
using namespace std;
 
typedef list<int> LISTINT;
typedef list<int> LISTCHAR;
 
void main()
{
    //用LISTINT创建一个list对象
    LISTINT listOne;
    //声明i为迭代器
    LISTINT::iterator i;
 
    listOne.push_front(3);
    listOne.push_front(2);
    listOne.push_front(1);
 
    listOne.push_back(4);
    listOne.push_back(5);
    listOne.push_back(6);
 
    cout << "listOne.begin()--- listOne.end():" << endl;
    for (i = listOne.begin(); i != listOne.end(); ++i)
        cout << *i << " ";
    cout << endl;
 
    LISTINT::reverse_iterator ir;
    cout << "listOne.rbegin()---listOne.rend():" << endl;
    for (ir = listOne.rbegin(); ir != listOne.rend(); ir++) {
        cout << *ir << " ";
    }
    cout << endl;
 
    int result = accumulate(listOne.begin(), listOne.end(), 0);
    //accumulate: 以init为初值，对迭代器给出的值序列做累加，返回累加结果值，
    cout << "Sum=" << result << endl;
    cout << "------------------" << endl;
 
    //用LISTCHAR创建一个list对象
    LISTCHAR listTwo;
    //声明i为迭代器
    LISTCHAR::iterator j;
 
    listTwo.push_front('C');
    listTwo.push_front('B');
    listTwo.push_front('A');
 
    listTwo.push_back('D');
    listTwo.push_back('E');
    listTwo.push_back('F');
 
    cout << "listTwo.begin()---listTwo.end():" << endl;
    for (j = listTwo.begin(); j != listTwo.end(); ++j)
        cout << char(*j) << " ";
    cout << endl;
 
    j = max_element(listTwo.begin(), listTwo.end());
    cout << "The maximum element in listTwo is: " << char(*j) << endl;
    Sleep(10000);  //这是windows里的延时函数，这里作用是主函数运行完之后10s后程序才停止
}

4.双端队列deque

4.1定义和初始化

所谓的deque是”double ended queue”的缩写，双端队列不论在尾部或头部插入元素，都十分迅速。而在中间插入元素则会比较费时，因为必须移动中间其他的元素。双端队列是一种随机访问的数据类型，提供了在序列两端快速插入和删除操作的功能，它可以在需要的时候改变自身大小，完成了标准的C++数据结构中队列的所有功能。
虽然deque也提供Random Access Iterator，但它的迭代器并不是普通指针，其复杂度和vector不可同日而语，这当然涉及到各个运算层面。因此，除非必要，我们应尽可能选择使用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector身上，将vector排序后（利用STL的sort算法），再复制回deque。

#include<deque>  / 头文件
deque<type> deq;  / 声明一个元素类型为type的双端队列que
deque<type> deq(size);  / 声明一个类型为type、含有size个默认值初始化元素的的双端队列que
deque<type> deq(size, value);  / 声明一个元素类型为type、含有size个value元素的双端队列que
deque<type> deq(mydeque);  / deq是mydeque的一个副本
deque<type> deq(first, last);  / 使用迭代器first、last范围内的元素初始化deq

4.2常用操作

deque<int> deq;
deq[ ]：用来访问双向队列中单个的元素。
deq.front()：返回第一个元素的引用。
deq.back()：返回最后一个元素的引用。
deq.push_front(x)：把元素x插入到双向队列的头部。
deq.pop_front()：弹出双向队列的第一个元素。
deq.push_back(x)：把元素x插入到双向队列的尾部。
deq.pop_back()：弹出双向队列的最后一个元素。

注意:deque容器类与vector类似，支持随机访问和快速插入删除，它在容器中某一位置上的操作所花费的是线性时间。与vector不同的是，deque还支持从开始端插入数据：push_front()。其余类似vector操作方法的使用。

4.3实例操作

double covCal(const std::deque<sampale_data>& inputSet , int flag=0){

          std::vector<double> resultSet;

          int count = inputSet.size();


          if(flag==0){
             for (int i = 0; i < count;i++)
                  {
                      resultSet.push_back(inputSet.at(i).x) ;
                  }
          }

          else if(flag==1){
              for (int i = 0; i < count;i++)
                  {
                      resultSet.push_back(inputSet.at(i).y) ;
                  }

          }

          else if(flag==2){
              for (int i = 0; i < count;i++)
                  {
                      resultSet.push_back(inputSet.at(i).yaw) ;
                  }

          }
       
          double sum = std::accumulate(std::begin(resultSet), std::end(resultSet), 0.0);  
          double mean =  sum / resultSet.size();  
            
          double accum  = 0.0;  
          std::for_each (std::begin(resultSet), std::end(resultSet), [&](const double d) {  
              accum  += (d-mean)*(d-mean);  
          });  

	//for (int i = 0; i < count; i++)
	//        {
	//            double d1=resultSet1.at(i);
	//            double d2=resultSet2.at(i);
	 //           accum  += (d1-mean1)*(d2-mean2); 
	            
	 //       } 
          
          return accum;  
  }

5.集合set

set集合容器：实现了红黑树的平衡二叉检索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。构造set集合主要目的是为了快速检索，不可直接去修改键值。

5.1定义和初始化

vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
ivec.push_back(i);
ivec.push_back(i);
}

set<int> iset(ivec.begin(), ivec.end());
cout << ivec.size() << endl; //20个
cout << iset.size() << endl; // 10个

5.3常用操作

• 添加元素

 set<string> set1;

set1.insert("the"); //第一种方法：直接添加

set<int> iset2;

iset2.insert(ivec.begin(), ivec.end());//第二中方法：通过指针迭代器

• 访问元素

set<int> iset;

for(int i = 0; i<10; i++)iset.insert(i);

iset.find(1) // 返回指向元素内容为1的指针

iset.find(11) // 返回指针iset.end()

iset.count(1) // 存在，返回1

iset.count(11) // 不存在，返回0

set 容器不提供下标操作符。为了通过键从 set 中获取元素，可使用 find运算。
如果只需简单地判断某个元素是否存在，同样可以使用 count 运算，返回 set 中该键对应的元素个数。
当然，对于 set 容器，count 的返回值只能是1（该元素存在）或 0（该元素不存在）。

• 删除元素

    set<int> s;
    s.erase(2);        //删除键值为2的元素
    s.clear();

• 查找元素
  元素检索：find()，若找到，返回该键值迭代器的位置，否则，返回最后一个元素后面一个位置。

set<int>::iterator it;
it=s.find(5);    //查找键值为5的元素
if(it!=s.end())    //找到
    cout<<*it<<endl;
else            //未找到
    cout<<"未找到";

5.4遍历操作

• 常规遍历

   for(set<int>::iterator it=numSet.begin() ;it!=numSet.end();it++)
	    {
	        cout<<*it<<" occurs "<<endl;
	    }
 

• 反向遍历

    set<int> s;
    ......
    set<int>::reverse_iterator rit;
    for(rit=s.rbegin();rit!=s.rend();rit++)

5.5实例操作

下面程序统计出现的数字有哪些,介绍set的增删查遍历实现

	#include <iostream>
	#include<set>
	using namespace std;
	int main()
	{
	    int numList[6]={1,2,2,3,3,3};
	    //1.set add
	    set<int> numSet;
	    for(int i=0;i<6;i++)
	    {
	        //2.1insert into set
	        numSet.insert(numList[i]);
	    }
	    //2.travese set
	    for(set<int>::iterator it=numSet.begin() ;it!=numSet.end();it++)
	    {
	        cout<<*it<<" occurs "<<endl;
	    }
	    //3.set find useage
	
	    int findNum=1;
	    if(numSet.find(findNum)!=numSet.end())
	    {
	        cout<<"find num "<<findNum<<" in set"<<endl;
	    }else{
	        cout<<"do not find num in set"<<findNum<<endl;
	    }
	    //set delete useage
	    int eraseReturn=numSet.erase(1);
	    if(1==eraseReturn)
	    {
	          cout<<"erase num 1 success"<<endl;
	    }else{
	        cout<<"erase failed,erase num not in set"<<endl;
	    }
	    return 0;
	}

6.映射map

map 是键－值对的集合。map 类型通常可理解为关联数组：可使用键作为下标来获取一个值，正如内置数组类型一样。而关联的本质在于元素的值与某个特定的键相关联，而并非通过元素在数组中的位置来获取。内部结构如下:

6.1定义和初始化

#include<map>
  map<int,int> numCountMap;

6.2常用操作

• 添加元素

numCountMap.insert({numName,thisAddTime});
numCountMap.insert(make_pair(numName,thisAddTime));
numCountMap.insert(pair<int,int>(numName,thisAddTime));
numCountMap.insert(map<int,int>::value_type(numName,thisAddTime));

插入规则:
注意，map包含不重复的关键字，此例子中关键字是numName,
因此插入一个已经存在的元素对容器没有影响．
如对于关键字１插入两次，即调用以下代码

numCountMap.insert({１,１});
numCountMap.insert({１,２});

• insert返回值
  此例insert返回值是

  pair<map<int,int>::iterator,bool> 

• 插入注意
  map 中使用一个不存在的关键字作为下标时会插入一个给定关键字的元素
  因此如下也可以插入元素
  numCountMap[numName]＝thisAddTime；
• 寻找元素find
  由于map 中使用一个不存在的关键字作为下标时会插入一个给定关键字的元素，因此查找是否有某个元素一定要使用find方法，否则使用下标操作会插入一个新元素
  map<int,int>::iterator it=numCountMap.find(alterNum);
• 删除
  erase的返回值总是０和１，若返回０，表示删除的元素不在map中
  int eraseReturn=numCountMap.erase(1);
• 修改和访问
  由于map 中使用一个不存在的关键字作为下标时会插入一个给定关键字的元素
  因此修改元素的时候不直接用下标操作
  通过先查找得到指向元素的迭代器， 然后直接赋值
  find返回指向元素的迭代器， 如果元素不存在， 则返回end 迭代器。

    int alterNum=3;
    map<int,int>::iterator alterit=numCountMap.find(alterNum);
    if(alterit!=numCountMap.end())
    {
        alterit->second=6;
        cout<<"alter num 3 occurs 6 time"<<endl;
    }

• 遍历
  遍历使用迭代器遍历，有两种形式，c++11使用auto 作为迭代器，如下

 　　//2.1 way one
    for(map<int,int>::iterator it=numCountMap.begin() ;it!=numCountMap.end();it++)
    {
        cout<<it->first<<" occurs "<<it->second<<" times"<<endl;
    }
    //2.1 way two ,c＋＋11 useage
    for(const auto &it : numCountMap)
    {
        cout<<it.first<<" occurs "<<it.second<<" times"<<endl;
    }

6.4实例操作

本文实现数字计数并介绍map的增删查改遍历实现

#include <iostream>
#include<map>
#include<set>
using namespace std;
int main()
{
    int numList[6]={1,2,2,3,3,3};
    map<int,int> numCountMap;
    //1.map add useage,insert into map four way
    for(int i=0;i<6;i++)
    {
        int numName=numList[i];
        int thisAddTime=1;
//        //1.1
//        numCountMap.insert({numName,thisAddTime});
//        //1.2
//        numCountMap.insert(make_pair(numName,thisAddTime));
        //1.3
         pair<map<int,int>::iterator,bool> ret=numCountMap.insert(pair<int,int>(numName,thisAddTime));
         if(!ret.second)
         {
             ++ret.first->second;
         }
//        //1.4
//        numCountMap.insert(map<int,int>::value_type(numName,thisAddTime));

    }

    //2.map traverse useage ,two way
    //2.1 way one
    for(map<int,int>::iterator it=numCountMap.begin() ;it!=numCountMap.end();it++)
    {
        cout<<it->first<<" occurs "<<it->second<<" times"<<endl;
    }
//    //2.1 way two ,c11 useage
//    for(const auto &it : numCountMap)
//    {
//        cout<<it.first<<" occurs "<<it.second<<" times"<<endl;
//    }

    //3.1 find useage
    int findNum=1;
    if(numCountMap.find(findNum)!=numCountMap.end())
    {
        cout<<"find num "<<findNum<<endl;
    }else{
        cout<<"do not find num "<<findNum<<endl;
    }

    //4.1 delete useage
    int eraseReturn=numCountMap.erase(1);
    if(1==eraseReturn)
    {
          cout<<"erase num 1 success"<<endl;
    }else{
        cout<<"erase failed,erase num not in map"<<endl;
    }

    for(map<int,int>::iterator it=numCountMap.begin() ;it!=numCountMap.end();it++)
    {
        cout<<it->first<<" occurs "<<it->second<<" times"<<endl;
    }

    //5.1 alter value useage
    int alterNum=3;
    map<int,int>::iterator alterit=numCountMap.find(alterNum);
    if(alterit!=numCountMap.end())
    {
        alterit->second=6;
        cout<<"alter num 3 occurs 6 time"<<endl;
    }
    for(map<int,int>::iterator it=numCountMap.begin() ;it!=numCountMap.end();it++)
    {
        cout<<it->first<<" occurs "<<it->second<<" times"<<endl;
    }
    return 0;
}

参考文献

c++ primer 第５版
c++标准程序库