STL是Standard Template Library的简称,中文名标准模板库。
从根本上说,STL是一些“容器”的集合,这些“容器”有list,vector,set,map等,STL也是算法和其他一些组件的集合。STL现在是C++的一部分,因此不用安装额外的库文件。
在C++标准中,STL被组织为下面的17个头文件:
<algorithm>、<deque>、<functional>、<iterator>、<array>、<vector>、<list>、<forward_list>、<map>、<unordered_map>、<memory>、<numeric>、<queue>、<set>、<unordered_set>、<stack>和<utility>。
一、vector
1. vector的自我介绍
- vector是向量的意思,可以理解为“可变长度的数组”。
- 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
- 相当于一个动态数组,在你不知道需要的数组有多大时可以使用它来节省很多空间。在ACM中常常会出现内存溢出(out of memory)的问题导致WA(wrong answer),而使用vector就能节省很多内存。
- 使用vector要在程序开头加上#include<vector>来包含需要的头文件,还有加上“using namespace std;”,这样就可以在代码中使用vector了。
2.vector的定义
- 定义一个vector:
vector<typename> vectorname;
- 这个定义相当于定义了一个一维的数组vectorname[SIZE],只不过这个SIZE的长度是可以改变的,随着你“加入”进去数的个数而改变。所谓“可变长度的数组”。
- 和一维的数组一样,这里的typename可以是任何的类型,如int,double,char,string,long long ,也可以是结构体,甚至是STL的容器如vector,set,queue,stack等。注意!如果typename也是一个容器的话,比如vector<vector<int> > vectorname,要在两个'<'符号之间加上一个空格,否则编译时会误以为是位移操作。
3.vector的创建
vector<double> vec1; // 创建一个空的double向量
vector<int> vec(66); // 创建一个初始大小为66的int向量
vector<double> vec2(vec1); // 创建一个double型的vec2,并用vec1去初始化vec2
vector<char> vec(10,'k'); // 创建一个含有10个char型数据的vector,并全部初始化为'k'
vector<int> vec(10,1);//创建一个初始大小为10的并且值都是1的vector
vector<int> vec2(vec1.begin(),vec1.begin()+3);//用向量vec1的第0个到第2个值初始化vec2
int arr[5] = {1, 2, 3, 4, 5};
vector<int> vec(arr, arr + 5); //将arr数组的元素用于初始化vec向量,末尾指针指向结束元素
//的下一个
vector<int> vec(&arr[1], &arr[4]); //将arr[1]~arr[4]范围内的元素作为vec的初始值,不包含arr[4],
//原因如上
4.特别的,元素为vector的vector数组
- (其实就是vector的二维数组)和vector数组! 如果typename是vector,那么就这么定义vector<vector<int> > vectorname; 注意在相邻的'>'之间要加空格。 这个就像二维数组的定义,其中一维是一个元素是vector的vector数组。可以把vector数组 当作两个维长度都可变的二维数组理解。vector数组的定义vector<typename> Arrayname[arraySize]; 比如,vector<int> vec[66]; 这样Arrayname[0]~Arrayname[arraySize-1]中每一个都是vector容器。 而vector<vector<int> > vectorname不同的地方时,前者的第一维长度已经固定为arraySize了, 后者却是两个维度都可变长的数组。哈哈哈,用你的大脑,发挥空间想象能力,出现了什么图形? 很神奇是不是!
5.vector容器内元素的访问形式
- vector一般有两种访问形式:通过下标访问或者是通过迭代器访问。
(1)通过下标访问
和访问普通数组是一样的,一个已经定义的vector<typename> vec的vector容器,直接访问vec[index]就可以了(比如 vec[0],vec[1])。需要注意的一点是,首先这个vec得有size!!!桥黑板!什么意思呢?就是如果一开始你定义了 比如vector<int> vec1;直接使用vec[0]是不对的!因为里面还没有长度啊!开始用的时候我就经常犯这个错误(尴尬) 。所以可以通过下标访问的范围是从0~vec.size()-1.
(2)通过迭代器访问
- 啥叫迭代器啊?好可怕~就理解为指针吧,不去考虑细节,两者是一样的(包括在java中最近遇见的引用,这简直是三胞胎!)。 定义如下: vector<typename>::iterator it;(it就是变量名,一般默认都写成it) 这样it就是一个vector<typename>::iterator 型的变量了(hhh,这个名字好长啊),其中,typename就是定义vector时 写的类型。比如: vector<double>::iterator it; vector<int> vec; vector<int>::iterator it2; it2=vec.begin();(或者合成一条:vector<int>::iterator it2=vec.begin(); ) 这样就得到了迭代器it(or it2),并且可以通过*it来访问vector里的元素。
vector<int> vec;
vector<int>::iterator it;
for (it = vec.begin(); it != vec.end(); it++)//vector的迭代器不支持it<vec.end()写法,因此循环中只能用it!=end()
cout << *it << endl;
//或者
vector<int>::iterator it=vec.begin();
for(int i=0;i<vec.size();i++){
printf("%d ",*(it+i));//桥黑板!!在STL容器中,只有vector和string这两个好基友,才允许使用vev.begin()+3这种迭代器加上整
//数的写法,只有这俩。
//从这里可以看出,vec[i]和*(vec.begin()+i)是等价的
}
//或者
for (size_t i = 0; i < vec.size(); i++) {
cout << vec.at(i) << endl;//见下文分解
}
好了,终于说完访问形式了,可以介绍基本操作啦!
6.vector的基本操作
(1)对容量的操作
- 得到向量的大小: vec.size();
- 得到向量最大可以是多大: vec.max_size();
- 重新设置容器size的大小: vec.resize(num);
- 重新设置容器capacity的大小: vec.reserve(num);
- 向量真实大小: vec.capacity();
- 判断向量是否为空: vec.empty();
注:关于resize()和reverse(),我觉得记住一点就行了,容器调用resize()函数后, 所有的空间都已经初始化了,所以可以直接访问。比如: vector<int> vet; vec.resize(100); vec[0]=1;//合法语句! 而reserve()函数预分配出的空间没有被初始化,所以不可访问。 推荐一个关于resize()和reserve()写的不错的博客vector中resize()和reserve()区别
(2)修改元素
- 多个元素赋值: vec.assign(); //类似于初始化时用数组进行赋值
- 末尾添加元素: vec.push_back(i)//在末尾添加元素i
- 末尾删除元素: vec.pop_back();
- 任意位置插入元素: vec.insert(it,x);
- 用来向vector的任意迭代器(见上文)it处插入一个元素x,时间复杂度O(N);
- 任意位置删除元素: vec.erase();
- erease(it)即删除迭代器为it处的元素;
- erase(first,last)即删除[first,last)内的所有元素;(老美的左闭右开,你懂的)
- 交换两个向量的元素: vec.swap();//不多讲,用的真的很少。同样,推荐博客vector利用swap()函数进行内存的释放
(3)惊现迭代器
开始指针:vec.begin();
末尾指针:vec.end(); //指向最后一个元素的下一个位置
指向常量的开始指针: vec.cbegin(); //意思就是不能通过这个指针来修改所指的内容,但还是可以通过其他方式修改的,而且指针也是可以移动的。(用的很少,不妨先忽略吧)
指向常量的末尾指针: vec.cend();(同上,不多说)
(4)元素的访问
下标访问: vec[1]; //桥黑板!!并不会检查是否越界
at方法访问: vec.at(1); //以上两者的区别就是at会检查是否越界,是则抛出out of range异常
访问第一个元素: vec.front();
访问最后一个元素: vec.back();
返回一个指针: int* p = vec.data(); //可行的原因在于vector在内存中就是一个连续存储的数组,所以可以返回一个指针指向这个数组。这是是C++11的特性。(可忽略)
(5)一些算法
- 遍历元素
Cvector<int>::iterator it;
for (it = vec.begin();it != vec.end(); it++)
cout << *it << endl;
//或者
for (size_t i = 0; i < vec.size(); i++) {
cout << vec.at(i) << endl;
}
- 元素翻转
C#include <algorithm>
reverse(vec.begin(), vec.end());
- 元素排序
C#include <algorithm>
sort(vec.begin(), vec.end()); //采用的是从小到大的排序
//如果想从大到小排序,可以采用上面反转函数,也可以采用下面方法:
bool Comp(const int& a, const int& b) {//固定套路,要加上const,意思是不能修改引用
return a > b;
}
sort(vec.begin(), vec.end(), Comp);
7.vector的用武之地
(1)储存数据
- vector本身可以作为数组使用,而且在一些元素个数不确定的场合可以很好的节省空间。
- 有些场合需要根据一些条件把部分数据输出在同一行,数据中间用空格隔开。由于输出的数据个数是不确定的,为了跟方便的处理最后一个满足条件的数据后面不输出额外的空格,可以先用vector记录所有需要输出的数据,然后一次性输出。
- 有强大的方法可以调用(妈呀,java学多了,请不要喷我,暂且就叫方法吧,介绍如上vector的基本操作(1)~(4))
( 2 )用邻接表存储图
- 使用vector实现邻接表可以有效避免指针,而且更容易把握。
哈哈哈,终于结束啦(喝口水)。
好了,说了这么多,当然废话也不少~~
来几道题目吧!
PAT A1039. Course List for Student (25)
PAT A1047. Student List for Course (25)
参考:C++ STL之vector用法总结
《算法笔记》(胡凡,曽磊)