STL vector 动态数组

vector 容器叫做动态数组，其大小可以随着元素的增长而变化，创建得时候不需要指定大小。vector 容器和 array 容器一样使用一块连续的内存空间来存储。

动态增长原理：
1. 当添加元素的时候，如果空间不足，此时，vector 容器会重新申请一块更大的内存空间
2. 将原来空间的数据拷贝到新空间中，然后，释放原来的空间。
3. vector 有容量的概念，主要是为了提高空间配置的效率。每次扩容，重新申请内存时，一般申请的空间大小会比实际需求大。

vector 容器的优缺点:
一般容器的优缺点都是和其内存结构相关。正是由于 vector 容器使用一块连续的内存空间，所以其优点如下：

根据下标（位置）查找某个元素效率极高，在尾部插入和删除元素效率比较高。
如果在头部、指定某个位置插入元素的话，效率比较低。
如果频繁需要在大 vector 中插入和删除数据，都会导致数组元素移动，效率非常低。如果说数据量小，无所谓。
vector 一般用于存储少量数据，vector 容器也是使用频率非常高的容器。

// 1. 容器的创建
void test01()
{
	// vector 不需要指定大小，和 array 相反。
	vector<int> v1;
	vector<int> v2 = { 10, 20, 30, 40 };
	vector<int> v3(v2.begin(), v2.end());

	int arr[] = { 10, 20, 30, 40 };
	vector<int> v4(&arr[0], &arr[4]);

	// vector 支持拷贝
	vector<int> v5 = v4;
}

// 2. 容器的遍历（正向遍历、反向遍历）
void test02()
{
	vector<int> v = { 10, 20, 30, 40 };


	// 容器的提供了哪些迭代器
	// vector<int>::iterator 正向可修改元素的迭代器类型
	// vector<int>::const_iterator  正向不可修改元素的迭代器类型
	// vector<int>::reverse_iterator  反向可修改的迭代器类型
	// vector<int>::const_reverse_iterator 反向不可修改的迭代器类型

	// 正向迭代器
	for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) *it += 100;
	for (vector<int>::const_iterator it = v.cbegin(); it != v.cend(); ++it) 
	{
		// 禁止修改元素的值  cbegin 返回开始位置的 const 迭代器，cend 返回结束位置的 const 迭代器
		// *it += 100;
	}


	// 反向迭代 : rbegin 指向容器最后一个元素   rend 指向的是第一个元素的前面的元素
	for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)
	{
		*it += 100;
	}

	for (vector<int>::const_reverse_iterator it = v.crbegin(); it != v.crend(); ++it)
	{
		// *it += 100;
		cout << *it << endl;
	}


	// for_each(v.begin(), v.end(), [](const int& v) { cout << v << endl; });
}

// 3. 容器元素的操作（插入、删除、赋值）
void test03()
{
	vector<int> v;
	// 尾部添加元素
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	// insert 函数的位置使用迭代器标识的，并不是数字下标
	v.insert(v.end(), 100);
	v.insert(v.begin(), 200);
	v.insert(v.begin() + 2, 300);
	for_each(v.begin(), v.end(), [](const int& v) { cout << v << endl; });

	cout << "-----------" << endl;

	// 删除元素使用 erase 函数，该函数可以一次删除某一个元素，也可以删除一个区间的元素
	// v.erase(v.begin());  // 删除数组中的第一个元素
	v.erase(v.begin(), v.begin() + 2);  // 左闭右开 [开始，结束)
	for_each(v.begin(), v.end(), [](const int& v) { cout << v << endl; });

	cout << "---------" << endl;
	v.assign({ 10, 20, 30 });  // 将原来的元素全部删除并重新赋值
	// v.assign(3, 100);
	for_each(v.begin(), v.end(), [](const int& v) { cout << v << endl; });
}


// 4. 容器元素的访问
void test04()
{
	vector<int> v = { 10, 20, 30, 40 };
	cout << v[0] << endl;
	cout << v.at(0) << endl;
	cout << v.front() << endl;
	cout << v.back() << endl;
}

// 5. 容器大小操作
void test05()
{
	vector<int> v = { 10, 20, 30, 40 };
	cout << "容器的大小:" << v.size() << endl;
	v.push_back(50);
	cout << "容器的大小:" << v.size() << endl;
	cout << "容器的容量:" << v.capacity() << endl;
	cout << "容器是否为空" << v.empty() << endl;
}

void test06()
{
	vector<int> v = { 10, 20, 30, 40 };
	// 重新改变容器的大小
	// 指定的大小小于之前的大小，右侧对于的元素会被销毁
	v.resize(2);
	// 指定的大小大于之前的大小，多余的元素填充0
	v.resize(4, 10);
	for_each(v.begin(), v.end(), [](const int& v) { cout << v << endl; });


	// reserve 函数预留空间
	vector<int> v2;
	v2.reserve(10);
	cout << "容量:" << v.capacity() << " 大小:" << v.size() << endl;
	cout << "容量:" << v2.capacity() << " 大小:" << v2.size() << endl;
}

// reserve 的使用案例
void test07()
{
	vector<int> v;
	// 假设：我们大概知道容器中需要存储的元素的个数 1000000
	// 此时，可以使用 reserve 预先分配容量，减少扩容次数
	v.reserve(1000000);

	int* p = nullptr;
	int cnt = 0;
	for (int i = 0; i < 1000000; ++i)
	{
		v.push_back(i);
		if (&v[0] != p)
		{
			p = &v[0];
			++cnt;
		}
	}

	cout << "容器扩容:" << cnt << "次" << endl;
}


// 6. 容器的交换
void test08()
{
	vector<int> v1 = {10, 20, 30};
	vector<int> v2 = {100, 200, 300};
	// 其内部仅仅是交换两个容器中指向存储数据的动态内存的指针，并不是拷贝所有的对象。
	v1.swap(v2);

	vector<int> v3;
	for (int i = 0; i < 100000; ++i)
	{
		v3.push_back(i);
	}

	// 虽然通过 resize 删除多余的元素， 但是 vector 的容量大小并没有收缩，仍然占据了大量的内存
	// 此时，如果希望收缩内存的话，可以使用 swap 函数
	v3.resize(10);
	cout << "容量:" << v3.capacity() << " 大小:" << v3.size() << endl;

	// vector<int>(v3) 先用 v3 初始化一个临时 vector 对象，该临时对象的容量就是 v3 的 size
	// 临时对象和 v3 进行交换，此时 v3 大的容量的空间就被交换给临时对象
	// 当前行结束之后，临时对象被销毁，其所关联的大容量内存也就被释放。
	vector<int>(v3).swap(v3);
	cout << "容量:" << v3.capacity() << " 大小:" << v3.size() << endl;
}

// 7. vector 容器迭代器失效问题
void test09()
{
	vector<int> v = { 10, 20, 30, 40 };
	vector<int>::iterator it = v.begin();

	// 当 vector 容器扩容之后，之前拿到的迭代器很有可能失效
	// 此时，需要重新获取迭代器。
	cout << v.capacity() << &v[0] << endl;
	v.push_back(50);
	cout << v.capacity() << &v[0] << endl;

	// *it = 200;
}

STL vector 动态数组

取消回复