C++STL容器学习笔记

今天系统学习C++ STL。这个东西使用起来十分方便,但是之前一直是使用手动写的,所以耗费的时间很多。

区别

看了一篇jb51的文章,也不知道是不是转载的:

  1. vector (连续的空间存储,可以使用[]操作符)快速的访问随机的元素,快速的在末尾插入元素,但是在序列中间岁间的插入,删除元素要慢,而且如果一开始分配的空间不够的话,有一个重新分配更大空间,然后拷贝的性能开销.
  1. deque (小片的连续,小片间用链表相连,实际上内部有一个map的指针,因为知道类型,所以还是可以使用[],只是速度没有vector快)快速的访问随机的元素,快速的在开始和末尾插入元素,随机的插入,删除元素要慢,空间的重新分配要比vector快,重新分配空间后,原有的元素不需要拷贝。对deque的排序操作,可将deque先复制到vector,排序后在复制回deque。
  1. list (每个元素间用链表相连)访问随机元素不如vector快,随机的插入元素比vector快,对每个元素分配空间,所以不存在空间不够,重新分配的情况
  1. set 内部元素唯一,用一棵平衡树结构来存储,因此遍历的时候就排序了,查找也比较快的哦。
  1. map 一对一的映射的结合,key不能重复。
  1. stack 适配器,必须结合其他的容器使用,stl中默认的内部容器是deque。先进后出,只有一个出口,不允许遍历。
  1. queue 是受限制的deque,内部容器一般使用list较简单。先进先出,不允许遍历。

惊奇的发现,把这个网页复制过来之后,竟然有6个div标签包着p……

Vector

传说中的动态数组。

#include <vector>//vector需要该头文件 
using namespace std;
int main(){
    vector<type>name;//声明vector类型
    name.push_back(element);//向队尾添加一个元素。
    //终于知道为什么大神们在预定义宏里面加上#define pb push_back了
    cout<<name[i]<<endl;//调用元素。还真的十分像数组。
    //vector是为数不多的几个可以使用下标遍历的STL 
    sort(name.begin(),name.end());//排序。
    reverse(name.begin(),name.end());//翻转 
    //所以#define all(x) x.begin(),x.end()就在这时候派上用场了。
    for(int i=0;i<name.size();i++){
        //如此获得vector大小。 
    }
    /*
    除了这种迭代方式以外,还有一种iterator的方法,
    但是不太喜欢。
    */
    name.resize();//强制改变数组长度
    name.insert(name.begin()+n,element);//往第n+1位后面加入元素 
}

Set

集合强大之处在于可以去重,可以排序。

#include <set>//set的头文件 
using namespace std;
int main(){
    set<type>name;
    //如果type不是int,那么“<”一定要重载
    name.insert(element);//插入元素
    name.size();//获取大小
    for(set<int>::iterator it=name.begin();it!=name.end();it++){//使用迭代器进行遍历
        cout<<(*it)<<endl;//取值
        //所有迭代器的取值方法都是这样取的 
    }
}

Map

映射容器。key->value

#include <map>//map的头文件 
using namespace std;
int main(){
    map<key,value>name;//map的构建
    map[key]=value;//访问、修改方法
    //insert find count move
    name.insert(pair<type,type>(key,value));
    //可以看出 map的内部是使用Pair来存储的
    name.find(value);//返回一个pair*,first为Key,second为value
    name.count(key);//我本来以为是返回pair的个数的,结果是满足键==key的元素个数……
    //用于判断key是否存在于map中 
}

Stack

#include <stack>//栈
int main(){
    stack<type>name;//构造
    //只能用迭代器访问全部元素,无[]
    name.push(element);//添加元素
    name.pop();//弹出最上面的元素 
    name.top();//返回最上面的元素 
} 

Queue

#include <queue>//队列 
int main(){
    queue<type>name;//构造
    //只能用迭代器访问全部元素,无[]
    name.push(element);//添加元素
    name.front();//返回前面的元素
    name.back();//返回最后面的元素 
    name.pop();//弹出最前面的元素 
}

Priority_queue

这是一个比较特殊的结构了。

#include <queue>//优先队列 
int main(){
    priority_queue<type>name;
    //若type==int,默认大根堆
    //否则需要重载小于号
    name.push(element);//添加元素
    name.pop();//弹出最前的元素
    name.top();//返回最前元素
    //有点类似stack 
}

重载运算符

重载运算符不仅使得编程比较方便,而且在STL中有广泛的应用。STL中常常需要比较大小。algorithm中的sort需要自定义比较的时候只需要自定义比较函数,但是其他的呢?其他的就只能重载运算符了。让原有的运算符让自己的变量类型按照自定义的方式进行运算。

重载有两种方式,可以在结构体外,也可以在结构体内。结构体内部的二元运算符只需要一个传入变量,但是结构体外部需要两个。可以理解。

type operator *** (type args[])

一般args[]是需要添加引用&符号的,因为如果非引用传递参数是需要在内存中复制一份出来的。加上引用符号可以减少空间和时间消耗。

avatar
Kerry Su