C++ std::vector 超详细指南：基础实践（手搓vector）

一.基本概念

二.类的常用接口说明

1.类对象的常见构造

2. vector类空间变化

1）.size()（获取数据个数）

2）.capacity()（获取容量大小）

3）.empty()（判断是否为空）

4）.resize()（改变vector的size）

5）.reserve()（改变vector的capacity）

6）.注意

3.vector iterator （迭代器）的使用

1）.begin()+end()（获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator）

2）.rbegin()+rend()（获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置）

4.vector 增删查改

1）.push_back()（尾插）

2）.pop_back()（尾删）

3）.insert()（在position之前插入val）

4）.erase()（删除position位置的数据）

5）.swap()（交换两个vector的数据空间）

6）.operator[ ]()（像数组一样访问）

三.vector 迭代器失效问题

1.导致迭代器失效的常见操作

1）.插入元素（push_back/insert/emplace_back）

2）.删除元素（erase/pop_back）

3）.容量调整（resize/reserve/shrink_to_fit）

2.典型错误场景

1）.循环中删除元素

2）.插入后使用旧迭代器

四.vector类的模拟实现

1.vector.h

2.vector.cpp（内容实现在.h里。我就不分离了，如需分离可自行实现）

一.基本概念

vector是STL提供的动态数组容器
使用vector要包含头文件：#include <vector>
特性：
- 支持随机访问（O(1)时间复杂度）
- 动态扩容（自动管理内存）
- 尾部插入/删除高效（O(1)时间复杂度）
- 连续内存空间存储元素

二.类的常用接口说明

1.类对象的常见构造

我们可以通过监视窗口查看构造完初始化的值

#include <vector>
#include <iostream>
using namespace std;

int main() {
    // 空vector
    vector<int> v1;
    cout << "v1 size: " << v1.size() << endl;  // 0

    // 包含5个默认初始化的int（0）
    vector<int> v2(5);
    cout << "v2: ";
    for(int n : v2) cout << n << " ";  // 0 0 0 0 0 

    // 包含3个值为10的元素
    vector<int> v3(3, 10);
    cout << "\nv3: ";
    for(int n : v3) cout << n << " ";  // 10 10 10

    // 拷贝构造
    vector<int> v4(v3);
    cout << "\nv4: ";
    for(int n : v4) cout << n << " ";  // 10 10 10

    // 用数组初始化
    int arr[] = {1,3,5,7};
    vector<int> v5(arr, arr + sizeof(arr)/sizeof(int));
    cout << "\nv5: ";
    for(int n : v5) cout << n << " ";  // 1 3 5 7

    // C++11初始化列表
    vector<int> v6{2,4,6,8};
    cout << "\nv6: ";
    for(int n : v6) cout << n << " ";  // 2 4 6 8
}

构造函数声明	接口说明
vector()	无参构造
vector（size_type n, const value_type& val =value_type()）	构造并初始化n个val
vector (const vector& x)	拷贝构造
vector (InputIterator first, InputIterator last);	使用迭代器进行初始化构

2. vector类空间变化

1）.size()（获取数据个数）
vector<int> v(10, 1);  
cout << v.size() << endl;     //10

2）.capacity()（获取容量大小）
	vector<int> v(10, 1);
	cout << v.capacity() << endl;      //10

3）.empty()（判断是否为空）
	vector<int> v;
	cout << v.empty()<<endl;      //1

4）.resize()（改变vector的size）

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v(10, 1);

	v.resize(15, 2);
	cout << v.size() << endl;    //15
	cout << v.capacity() << endl;     //15

	v.resize(25, 3);
	cout << v.size() << endl;     //25
	cout << v.capacity() << endl;     //25

	v.resize(5);
	cout << v.size() << endl;     //5
	cout << v.capacity() << endl;     //25

}

5）.reserve()（改变vector的capacity）

	vector<int> v(10, 1);
	v.reserve(20);
	cout << v.size() << endl;     //10 
	cout << v.capacity() << endl;     //20

6）.注意

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为

reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题

resize在开空间的同时还会进行初始化，影响size

// 如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{
	vector<int> v;
	size_t sz = v.capacity();
	v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容
	cout << "making bar grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

3.vector iterator （迭代器）的使用

1）.begin()+end()（获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator）
vector<int> v(10, 1);
v.resize(15, 2);
vector<int>::iterator beg =v.begin();
vector<int>::iterator end =v.end()-1;  //end是 \0 无法访问
cout << *beg<<" "<<*end;     //1   2

2）.rbegin()+rend()（获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置）
	vector<int> v(10, 1);
	v.resize(15, 2);
	vector<int>::reverse_iterator rbeg =v.rbegin();
	vector<int>::reverse_iterator rend =v.rend()-1;
	cout << *rbeg<<" "<<*rend;     //2   1

4.vector 增删查改

1）.push_back()（尾插）

	vector<string> v1;
	string s1("xxxx");
	v1.push_back(s1);
	v1.push_back("yyyyy");
	for (const auto& e : v1)
	{
		cout << e << " ";      //xxxx yyyyy
	}
	cout << endl;

2）.pop_back()（尾删）

	vector<string> v1;
	string s1("xxxx");
	v1.push_back(s1);
	v1.push_back("yyyyy");
	v1.pop_back();
	for (const auto& e : v1)
	{
		cout << e << " ";      //xxxx
	}
	cout << endl;

3）.insert()（在position之前插入val）

	vector<int> v(10, 1);
	v.insert(v.begin(), 0);
	v.insert(v.begin() + 3, 10);
	for (auto e : v)
	{
		cout << e << " ";     //0 1 1 10 1 1 1 1 1 1 1 1
	}
	cout << endl;

3）.erase()（删除position位置的数据）

	vector<int> v(10, 1);
	v.insert(v.begin(), 0);
	v.insert(v.begin() + 3, 10);
	for (auto e : v)
	{
		cout << e << " ";     //0 1 1 10 1 1 1 1 1 1 1 1
	}
	cout << endl;
	v.erase(v.begin());  //参数必须是迭代器
	v.erase(v.begin(), v.begin()+2);
	for (auto e : v)
	{
		cout << e << " ";     //10 1 1 1 1 1 1 1 1
	}

4）.swap()（交换两个vector的数据空间）

vector<int> v(10, 1);
vector<int> c(10, 2);
v.swap(c);

for (auto e : v)
{
	cout << e << " ";     //2 2 2 2 2 2 2 2 2 2
}
cout << endl;
for (auto e : c)
{
	cout << e << " ";    //1 1 1 1 1 1 1 1 1 1
}

5）.operator[ ]()（像数组一样访问）

	vector<int> v(10, 1);
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";    //1 1 1 1 1 1 1 1 1 1
	}

三.vector 迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃) 。