C++ 泛型编程:vector 容器

vector 基本概念

vector 容器
  • vector 数据结构和数组类似
  • 数组是静态空间,vector 可以动态拓展
  • 动态拓展并不是在原空间之后续接新空间,而是找更大的内存空间,拷贝原数据,并释放原空间
  • vector 容器的迭代器是支持随机访问的迭代器
  • push_backpop_back 效率很高,但是 inserterase 则效率很低

vector 构造函数

  • vector<T> v;
  • vector<T> v2( v1.begin(), v1.end() ); // [ begin, end ),左闭右开
  • vector<T> v3( n, elem );
  • vector<T> v4( const vector& vec );
void print_vector(vector<int>& v)
{
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void vector_constructor()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	print_vector(v1);

	vector<int> v2(v1.begin(), v1.end());
	print_vector(v2);

	vector<int> v3(10, 100);
	print_vector(v3);

	vector<int> v4(v3);
	print_vector(v4);
}

vector 赋值操作

  • vector& operator=( const vector& vec );
  • void assign( v.begin(), v.end() ); // [ begin, end ),左闭右开
  • void assign( n, elem);
void vector_assign()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	print_vector(v1);

	vector<int> v2;
	v2 = v1;
	print_vector(v2);

	vector<int> v3;
	v3.assign(v1.begin(), v1.end());
	print_vector(v3);

	vector<int> v4;
	v4.assign(10, 100);
	print_vector(v4);
}

vector 大小和容量

  • bool empty();
  • int capacity();
  • int size();
  • void resize( int num )
  • void resize ( int num, elem );
void vector_sizeAndCapacity()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	print_vector(v1);

	if (v1.empty())
	{
		cout << "v1 为空" << endl;
	}
	else
	{
		cout << "v1 不为空" << endl;
		cout << "v1 的容量为:" << v1.capacity() << endl;
		cout << "v1 的大小为:" << v1.size() << endl;
	}

	v1.resize(15);
	print_vector(v1);  // 比原来长的部分,默认用 0 填充

	v1.resize(20, 100);  // 指定默认填充值
	print_vector(v1);

	v1.resize(5);  // 超出的部分会被删除
	print_vector(v1);
}

vector 插入和删除

  • void push_back( elem );
  • void pop_back();
  • iterator insert( const_iterator pos, elem );
  • iterator insert( const_iterator pos, int count, elem );
  • iterator insert( const_iterator pos, v.begin(), v.end() );
  • iterator erase( const_iterator pos);
  • iterator erase( v.begin(), v.end() );
  • void clear();
void vector_insertAndErase()
{
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);
	print_vector(v1);

	v1.pop_back();
	print_vector(v1);

	// insert 效率低,不推荐
	v1.insert(v1.begin(), 100);
	print_vector(v1);

	v1.insert(v1.begin(), 2, 1000);
	print_vector(v1);

	// erase 效率低,不推荐
	v1.erase(v1.begin());
	print_vector(v1);

	v1.erase(++v1.begin(), --v1.end());
	print_vector(v1);

	v1.clear();
	print_vector(v1);
}

vector 数据存取

  • T& at( int index );
  • T& operator[]( int index );
  • T& front();
  • T& back();
void vector_at()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	
	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";
	}
	cout << endl;

	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1.at(i) << " ";
	}
	cout << endl;

	cout << "第一个元素为:" << v1.front() << endl;

	cout << "最后一个元素为:" << v1.back() << endl;
}

vector 互换容器

  • void swap( vector& vec );
  • 巧用 swap 可以收缩内存空间(例如在 resize 之后)
void vector_swap()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}

	vector<int> v2;
	for (int i = 10; i > 0 ; i--)
	{
		v2.push_back(i);
	}

	cout << "交换前:" << endl;
	print_vector(v1);
	print_vector(v2);


	cout << "交换后:" << endl;
	v1.swap(v2);
	print_vector(v1);
	print_vector(v2);
}

巧用 swap 收缩内存空间案例:

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

	cout << "resize 前:" << endl;
	cout << "v1 的容量为:" << v1.capacity() << endl;
	cout << "v1 的大小为:" << v1.size() << endl;

	v1.resize(3);
	cout << "resize 后:" << endl;
	cout << "v1 的容量为:" << v1.capacity() << endl;
	cout << "v1 的大小为:" << v1.size() << endl;

	// 巧用 swap 收缩内存
	vector<int>(v1).swap(v1);

	cout << "swap 后:" << endl;
	cout << "v1 的容量为:" << v1.capacity() << endl;
	cout << "v1 的大小为:" << v1.size() << endl;
}

vector 预留空间

  • void reserve( int len );
  • 减少 vector 在动态拓展时的拓展次数
void vector_reserve()
{
	vector<int> v1;
	// 统计内存开辟次数
	int count = 0;
	int* p = nullptr;
	for (int i = 0; i < 100000; i++)
	{
		v1.push_back(i);
		if ( p != &v1[0])
		{
			p = &v1[0];
			count++;
		}
	}
	cout << "未使用 reserve 时,内存开辟次数为:" << count << endl;

	// 利用 reserve 预留控件
	vector<int> v2;
	v2.reserve(100000);
	count = 0;
	p = nullptr;
	for (int i = 0; i < 100000; i++)
	{
		v2.push_back(i);
		if (p != &v2[0])
		{
			p = &v2[0];
			count++;
		}
	}
	cout << "使用 reserve 后,内存开辟次数为:" << count << endl;
}