常用的STL数据结构及用法

标准模板库(英文:Standard Template Library,缩写:STL),是一个C++软件库,大量影响了C++标准程序库但并非是其的一部分。其中包含4个组件,分别为算法、容器、函数、迭代器。


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 <int>::iterator iElement = find(vecIntegerArray.begin(),vecIntegerArray.end(),3);
if( iElement != vecIntegerArray.end() ){
    int nPosition = distance(vecIntegerArray.begin(),iElement);
    cout << "Value  "<< *iElement;
    cout <<"  find in the vector at position: " <<nPosition + 1 <<endl;
    }
  • 排序
    //递增
    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()

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()
  1. 用find函数来定位键值出现位置,它返回的一个迭代器,当键值出现时,它返回所在位置的迭代器,如果map中没有要查找的键值,它返回的迭代器等于end函数返回的迭代器
    map<string,double>::iterator it;
    it=m.find("Jack");
    cout<<(*it).first<<":"<<(*it).second<<endl;

    //等价于

    cout<<"Jack"<<":"<<m["Jack"]<<endl;
  1. 用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;

set

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

  • 创建set对象
set s1; //默认升序
//-----------------//
struct comp
{
bool operator() ( const int& lhs, const int& rhs )
{
return lhs > rhs ;
}
};
set s2; //降序
//--------------//
struct Node
{
int x;
int y;
friend bool operator < (Node a, Node b)//结构体排序(重载<操作符):
{
return a.x 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.pop();
添加新评论