STL中常用数据结构及用法

C++中的STL（Standard Template Library）,即标准模板库，中包含了很多编程时常用的数据结构，省去了自己临时写的麻烦，这里就来总结一下。如果有错误或写的不好的地方还请多指正。

首先稍微介绍下iterator(迭代器)，iterator不是数据结构，所有容器都提供获得迭代器的元素，声明时，其数据类型必须与容器的数据类型一致。其作用主要是用来遍历和删除元素。

操作	效果
begin()	返回一个迭代器，指向第一个元素
end()	返回一个迭代器，指向最后一个元素之后

左闭右开

vector

#include < vector > 向量，不定长数组。
与数组的区别在于声明时不需要指定长度，vector动态分配空间（线性连续地址）。插入和删除都比数组要方便很多。vector可以直接赋值，还可以作为函数的参数或者返回值，而无须像传递数组那样用另一个变量指定元素个数。

• 创建vector对象：

    //默认初始化，v1为空
    vector<int> v1;     
            
    //初始10个值为0的元素
    vector<int> v2(10);  
           
    //初始10个值为8.6的元素
    vector<double> v3(10,8.6)   
    

• 访问：

	//直接通过下标就能访问
	v2[2]=3;
    cout<<v2[2]<<endl;
    //通过迭代器访问
    cout<<*(v2.begin()+2)<<endl

• 遍历

    //①通过下标遍历
    for(int i=0;i<v3.size();i++)
        cout<<v3[i]<<' ';

	//②通过迭代器遍历（推荐）
    vector<int>::iterator it;
    for(it=v2.begin();it!=v2.end();it++)
    {
        cout<<*it<<' ';
    }

• 插入元素

   // ①元素尾部扩张
    v.push_back(9);
    
   // ②指定位置插入
    v.insert(v.begin()+2,1);
    v.insert(v.end(),3);

• 删除元素

	//删除单个元素
    v.erase(v.begin()+1);
    
    //删除区间内所有元素
    v.erase(v.begin()+2,v.begin()+5);
    
    //清空
    v.clear();

• 查找元素
  需要查操作的话一般不使用vector，而是set或multiset。
  方法：在vector中查找元素及其位置

• 排序

	//递增
	sort(v.begin(),v.end());

	//递减
	sort(v.begin(),v.end(),greater<int>());

	//自定义结构体排序
	struct Node
	{
	    int a;
	    int b;
	};
	bool cmp(Node x,Node y)
	{
	    return x.a<y.a;
	}
	vector<Node> v;
	sort(v.begin(),v.end(),cmp);

• 其他

    //元素反向排列
    reverse(v.begin(),v.end());

    //获取向量大小（元素个数）
    v.size()

	//向量是否为空
	v.empty()

• 例题：HDU 4841：圆桌问题（vector应用）

map

#include< map > 映射，键值对容器。

map就是从键（key）到值（value）的映射。因为重载了 [ ] 运算符，map更像是数组的“高级版”。例如可以用一个map< string,int>month_name来表示“月份名字到月份编号”的映射，然后用 month_name[“July”]=7 这样的方式来赋值。

类似于Python中的字典Dictionary与Java中的TreeMap。
所有元素会根据key值排序（默认升序，如果键值为字符串就是字典序），map中的所有元素都是pair，同时拥有实值和键值，pair的first为键值，second为实值，底层将它的first作为红黑树的排序key。
map不允许有两个相同键值的元素。map的迭代器不能修改键值，但可以修改实值。主要用于处理带有键值的记录性元素数据的快速插入、删除和检索。

• 创建map对象

	map<string,double> m;

• 插入和访问
  （访问时如果map中不存在该键值，实值为空，对于数字则为0，字符串则为空串。）

    m["Jack"]=98.5;
    cout<<m["Jack"]<<endl;

• 遍历

    map<string,double>::iterator it;
    for(it=m.begin();it!=m.end();it++)
        cout<<(*it).first<<":"<<(*it).second<<endl;

• 删除

    //通过键值删除
    m.erase("Jack");
    
    //清空
    m.clear();

还有一种方法是遍历删除，既可以通过键值，也可以通过实值，不过由于迭代器的属性，这种方法不注意的话很容易出错。这里贴两个大神的链接：
c++ 关于map的遍历 删除
c++如何遍历删除map/vector里面的元素

• 查找
  使用键值进行查找操作。大多数情况直接用键值访问就行了，很少用到下面的m.find()

Searches the container for an element with a key equivalent to k and returns an iterator to if found,otherwise it returns an iterator to map::end

1.用find函数来定位键值出现位置，它返回的一个迭代器，当键值出现时，它返回所在位置的迭代器，如果map中没有要查找的键值，它返回的迭代器等于end函数返回的迭代器

    map<string,double>::iterator it;
    it=m.find("Jack");
    cout<<(*it).first<<":"<<(*it).second<<endl;
    
    //等价于
    
    cout<<"Jack"<<":"<<m["Jack"]<<endl;
    

2.用count函数来判定键值是否出现，count函数的返回值只有两个，键值出现返回1，否则返回0

    if(m.count("Jack"))
        cout<<"FOUND"<<endl;
    else
        cout<<"NOT FOUND"<<endl;
	
	//等价于
	
    if(m["Jack"])
        cout<<"FOUND"<<endl;
    else
        cout<<"NOT FOUND"<<endl;

• 例题： POJ 1008：Maya Calendar (模拟)

set

#include< set > 集合

Sets are containers that store unique elements following a specific order.

类似于Java中的TreeSet，set就是数学上的集合——每个元素最多出现一次，其中的元素自动排序，自定义类型构造set时，必须定义"小于"运算符。一个集合通过一个链表来组织，在插入操作和删除操作上比向量(vector)快，但查找或添加末尾的元素时会有些慢。具体实现采用了红黑树的平衡二叉树的数据结构。

• 创建set对象

set<int> s1;    //默认升序
	
//-----------------//

struct comp
{
   bool operator() ( const int& lhs,  const int& rhs )
   {
       return lhs > rhs ;
   }
};
set<int, comp> s2;   //降序

//--------------//


struct Node
{
    int x;
    int y;
    friend bool operator < (Node a, Node b)//结构体排序(重载<操作符)：
    {
        return a.x<b.x; //按照x升序
    }
};

set<Node> s3;

• 插入和访问
  **set不支持随机访问！*因此(s.begin+1)这种操作都是非法的，只能通过迭代器移动来访问

    s1.insert(5);
    s2.insert(Node{8,5});

	cout<<*s1.begin()<<endl;//第一个元素
	cout<<*(--s1.end())<<endl;//最后一个元素

• 遍历

	//只能通过迭代器遍历
	set<int>::iterator it;
    for(it=s1.begin();it!=s1.end();it++)
        cout<<*it<<endl;

• 删除

    //删除值为5的元素，返回删除的元素个数
    s1.erase(5);   
         
    //删除首个元素，无返回值
	s1.erase(s1.begin());   

	//清空
	s1.clear();

• 查找

	if(s1.find(5)!=s1.end())
        cout<<"FOUND"<<endl;
    else
        cout<<"NOT FOUND"<<endl;

查找操作对应find函数，如果存在该元素，返回指向该元素的迭代器，否则返回end。
值得一提的是对自定义结构体的查找操作则比较复杂： C++ STL set::find的用法

stack

#include < stack >，堆栈

这个就是咱们数据结构中学的栈，栈的操作只有几种方法

• 声明

	stack<int> s;

• 入栈

	s.push(8);

• 出栈

	s.pop();

• 取栈顶元素（但不删除）

	s.top();

例题：HDU 1022：Train Problem I（堆栈的基本应用）

queue

priority_queue