c++ STL库

STL库

容器概述
容器：可以用于存放各种数据类型的数据的数据结构
分为三大类：

• 顺序容器：
  • vector:后部插入删除，直接访问
  • deque:前后部插入删除，直接访问
  • list:双向链表，任意位置插入删除
• 关联容器：
  • set:快速查找，无重复元素
  • multiset:快速查找，可以有重复元素
  • map:一对一映射，无重复元素，基于关键字查找
  • multimap:一对一映射，可有重复元素，基于关键字查找
• 容器适配器
  stack:LIFO
  queue:FIFO
  priority_queue:优先级高的元素先出
  对象被插入容器中时，被插入的是元素的一个复制品

顺序容器

1. vector:实际上是个动态数组，随机存取任何元素都能在常数时间完成，在尾端增删元素具有较佳的性能
2. deque:也是个动态数组，随机存取任何元素都能在常数时间完成，在两端增删元素具有较佳的性能
3. list:双向链表，不支持随机存取
   上述三种元素称为顺序元素，是因为元素的插入位置同元素的值无关，只与插入的时机有关。

成员函数

begin:返回容器中第一个元素的迭代器
end:返回容器中最后一个元素的后一个位置的迭代器
rbegin:返回容器中最后一个元素的迭代器
rend:返回容器中第一个元素前面一个位置的迭代器
erase:从容器中删除一个或几个元素
clear:从容器中删除所有元素

迭代器用法和指针类似
迭代器有const和非const两种
非const迭代器可以修改其指向的元素
容器类名::iterator 变量名
迭代器可以执行++操作

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    for(vector<int>::iterator i=v.begin();i!=v.end();i++)
    {
        cout<<*i<<endl;      //暂时可以把迭代器理解为指针 
    }
    return 0;
}

只有顺序容器可以用迭代器遍历

关联容器

关联式容器内的元素是排序的，插入任何元素，都按相应的排序准则来确定其位置，关联容器的特点是在查找时具有非常好的性能

1. set:集合
2. map:map中存放的是成对的key/value
   并根据key值对元素进行排序

容器适配器

1. stack:栈，后进先出
2. queue:队列，插入只在尾部进行，删除，检索和修改只允许在头部进行，先进先出
3. priority_queue:优先级队列，最高优先级元素总是第一个出列

容器的共有成员函数

1. 相当于按词典顺序比较两个容器大小的运算符：=, < , <= , > , >=, == , !=
2. empty:判断容器中是否有元素
3. max_size:容器中最多能装多少个元素
4. size:容器中元素个数
5. swap:交换两个容器的内容

//比较两个容器的例子
#include<vector>
#include<iostream>
using namespace std;
int main()
{
    vector<int> v1;
    vector<int> v2;

    //赋值
    v1.push_back(5);
    v1.push_back(3); 
    v2.push_back(5);
    v2.push_back(1);
    v2.push_back(4);

    cout<<(v1>v2)<<endl;
    return 0;
} 

STL算法

算法就是一个个函数模板
算法要通过迭代器来操纵函数中的元素
函数模板都在中定义
分类

1. 变化序列算法
   copy,remove,fill,replace,random_shuffle,swap
   会改变容器
2. 非变化序列算法
   adjacent-find,equal,mismatch,find,count,search,count_if,for_each,search_n
   

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    vector<int>::iterator p;
    p=find(v.begin(),v.end(),3);        //注意，返回的是迭代器，要用迭代器接收返回的值
    if(p!=v.end())
    cout<<"find it"<<*p<<endl;
    p=find(v.begin()+1,v.end(),1);
    if(p!=v.end())
    cout<<"find it"<<*p<<endl;
    else cout<<"not found"<<endl;
    return 0;
}

//数组也可以用find()
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int array[10]={10,20,30,40};
    int *p=find(array,array+4,20);
    cout<<*p<<endl;
    return 0;
}

顺序容器

front():返回容器中第一个元素的引用
back():返回容器中最后一个元素的引用
push_back()
pop_back()

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int a[5]={1,2,3,4,5};
    vector<int> v1(5);
    cout<<v1.end()-v1.begin()<<endl;
    //注意一下这个赋值方式 
    for(int i=0;i<v1.size();i++)
    {
        v1[i]=i;
    }
    v1.at(4)=100;      //把第四个数改成100 
    for(int i=0;i<v1.size();i++)
    {
        cout<<v1[i]<<" ";
    } 
    cout<<endl;
    vector<int> v2(a,a+5);  //把数组里的元素赋值到这个容器里 
    v2.insert(v2.begin()+2,12);      //在begin()+2的位置插入12
    for(int i=0;i<v2.size();i++)
    {
        cout<<v2[i]<<" ";
    }
    cout<<endl;
    return 0; 
}