前言
前面我们学习C++的string部分,其中的接口,函数都很多,vector相较与string的学习就会轻松很多,接下来我们将一起探索神奇的vector!!!
1.vector的介绍
向量(Vector)是一种在计算机科学中常用的数据结构,它是一种能够存储一系列数据的顺序容器。在 C++ 中,std::vector 是一种模板类,它可以存储任何类型的动态大小数组。
1. 动态数组:std::vector 是一个动态数组,这意味着它可以在运行时根据需要自动调整其大小。
2. 连续存储:std::vector`保证其元素在内存中是连续存储的,这使得通过索引访问元素非常快速。
3. 模板类:std::vector 是一个模板类,这意味着它可以用来创建任何类型元素的向量,例如 vector<int>, vector<double>, vector<string>, 等等。
4. 自动内存管理:std::vector会自动管理其元素的内存分配和释放,这减少了内存泄漏的风险。
5. 成员函数:std::vector`提供了多种成员函数来操作其元素,如 push_back() 用于在末尾添加元素,pop_back()用于移除末尾的元素,size() 返回向量中元素的数量,capacity() 返回当前向量在不重新分配内存的情况下可以存储的元素数量。
6. 迭代器:std::vector 提供了迭代器,可以用来遍历向量中的元素。
7. 性能特性:
- 随机访问:由于元素是连续存储的,因此 std::vector`支持快速的随机访问。
- 插入和删除:向量的末尾插入或删除元素通常是非常高效的,但在向量开始或中间插入或删除元素可能比较低效,因为这可能导致大量元素的移动。
8. 构造函数:std::vector提供了多种构造函数,允许从其他容器复制构造,或者指定初始大小和元素值。
2.vector的部分使用
2.1(constructor)构造函数声明
vector()(重点)无参构造
vector(size_type n, const value_type& val = value_type())构造并初始化n个val
vector (const vector& x); (重点)拷贝构造
vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造
#include <iostream> #include <vector> using namespace std; void test_vector1() { vector<int> v1; vector<int>v2(3, 1); vector<int>v3(v2.begin(), v2.end()); vector<int>v4(v2); } int main() { test_vector1(); return 0; }
2.2vector的遍历(与string是相似的)
循环遍历for+[],迭代器遍历,范围for
#include <iostream> #include <vector> using namespace std; void test_vector1(){ vector<int> v1{1,2,3,4,5}; vector<int>v2(5,1); vector<int>v3(++v2.begin(),--v2.end()); vector<int>v4(v2); for(int i=0;i<v3.size();i++){ cout << v3[i] << " "; } cout<<"\n"; vector<int>::iterator it=v1.begin(); while(it != v1.end()){ cout<<*it<<" "; it++; } cout<<"\n"; for(auto e:v3){ cout<<e<<" "; } } int main(){ test_vector1(); return 0; }
2.3 vector容量空间
size获取数据个数
capacity获取容量大小
empty判断是否为空
resize(重点)改变vector的size
reserve (重点)改变vector的capacity
void test_vector2() { vector<int> v(10, 1); v.reserve(20); cout << v.size() << endl; cout << v.capacity() << endl; v.reserve(15); cout << v.size() << endl; cout << v.capacity() << endl; for(size_t i=0;i<v.size();i++){ cout << v[i] << " "; } cout<<"\n"; v.reserve(5); cout << v.size() << endl; cout << v.capacity() << endl; for(size_t i=0;i<v.size();i++){ cout << v[i] << " "; } cout<<"\n"; } void test_vector3() { vector<int> v(10, 1); v.reserve(20); cout << v.size() << endl; cout << v.capacity() << endl; v.resize(15, 2); cout << v.size() << endl; cout << v.capacity() << endl; for(size_t i=0;i<v.size();i++){ cout << v[i] << " "; } cout<<"\n"; v.resize(25, 3); cout << v.size() << endl; cout << v.capacity() << endl; v.resize(5); cout << v.size() << endl; cout << v.capacity() << endl; for(size_t i=0;i<v.size();i++){ cout << v[i] << " "; } cout<<"\n"; }
capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2 倍增长的,vscode是按2倍增长。这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是 根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。 reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代 价缺陷问题。 resize在开空间的同时还会进行初始化,影响size。
下面我们简单测试下capacity的扩容机制(vscode)
void test_vector_expand(){ size_t sz; vector<int>v; sz=v.capacity(); cout << "making v grow:\n"; for(int i=0;i<100;i++){ v.push_back(1); if(sz!=v.capacity()){ sz = v.capacity(); cout << "capacity changed: " << sz << '\n'; } } }
当然如果已经确定vector中要存储元素大概个数,可以提前将空间设置足够 ,就可以避免边插入边扩容导致效率低下的问题了,上面代码我们可以提前v.reserve(100)
2.4vector的增删查改
这里find使用,导入#include <algorithm>
void test_vector4(){ vector<int>v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); auto it=v.begin(); while(it!=v.end()){ cout<<*it<<" "; it++; } cout<<'\n'; v.pop_back(); v.pop_back(); it=v.begin(); while(it!=v.end()){ cout<<*it<<" "; it++; } cout<<'\n'; } void test_vector5() { // 使用列表方式初始化,C++11新语法 vector<int> v{ 1, 2, 3, 4 }; // 在指定位置前插入值为val的元素,比如:3之前插入30,如果没有则不插入 // 1. 先使用find查找3所在位置 // 注意:vector没有提供find方法,如果要查找只能使用STL提供的全局find auto pos = find(v.begin(), v.end(), 3); if (pos != v.end()) { // 2. 在pos位置之前插入30 v.insert(pos, 30); } vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; pos = find(v.begin(), v.end(), 3); // 删除pos位置的数据 v.erase(pos); it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; }
3.vector的嵌套
在vector的介绍我们提到vector可以用来创建任何类型元素的向量,例如 vector<int>, vector<double>, vector<string>等
void test_vector6() { vector<string> v1; string s1("xxxx"); v1.push_back(s1); v1.push_back("yyyyy"); for (const auto& e : v1) { cout << e << " "; } cout << endl; }
那么是否可以vector中套用vector呢,当然是可以的
void test_vector7(){ vector<int>v(5,1); vector<vector<int>>vv(4,v); for(size_t i=0;i<vv.size();i++){ for(size_t j=0;j<v.size();j++){ cout<<vv[i][j]<<" "; } cout<<endl; } vv[2][1]=2;//修改 }
这个嵌套我们可以看成一个二维数组,遍历修改都是差不多的
下面我们将从底层剖析vector的嵌套,实际上存在一个模版类,来进行处理
template <class T> class Vector{ T&opetator[](int i) { assert(i<_size); return _a[i]; } private: T*_a; size_t _size; size_t _capacity; } //vector<int> class vector{ int& operator[](int i){ assert(i < _size); return _a[i]; } private: int* _a; size_t _size; size_t _capacity; }; // vector<vector<int>> class vector{ vector<int>& operator[](int i) { assert(i < _size); return _a[i]; } private: vector<int>* _a; size_t _size; size_t _capacity; };
下面通过一道题来加深印象
结束语
本节内容就到此结束了,下节我们将继续深入学习vector.
最后真心感谢各位友友的支持!!!