vector介绍和基本使用

2023-05-16

文章目录

一.vector介绍
二.vector使用
- (1).constructor
- (2).iterator
- (3).capacity
- (4).Element access
- (5).Modifiers
三.vector迭代器失效问题

一.vector介绍

vector文档

vector是表示可变大小数组的序列容器。

就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。

二.vector使用

(1).constructor

(1).构造一个空容器，没有元素

vector<int> v1;

(2).构造n个值为val的容器

vector<int> v2(10,2); // size为10，capacity为10

(3).使用 [first,last) 区间内的元素构造容器

vector<int> v3(v2.begin(),v2.end());
string s = "hello world";
vector<char> v4(s.begin(),s.end());

(4).拷贝构造

vector<int> v5(v3);

(2).iterator

iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;

在这里插入图片描述

#include<iostream>
#include<vector>
using namespace std;
void print(const vector<int>& v)
{
	// const_iterator
	vector<int>::const_iterator vit = v.begin();
	while (vit != v.end())
	{
		cout << *vit << " ";
		++vit;
	}
	cout << endl;
}
int main()
{
	vector<int> v1(10, 2);
	const vector<int> v2(10,5);
	
	vector<int>::iterator vit = v1.begin();
	while (vit != v1.end())
	{
		cout << *vit << " ";
		++vit;
	}
	cout << endl;

	print(v2);
	// reverse_iterator
	vector<int>::reverse_iterator vrit = v1.rbegin();
	while (vrit != v1.rend())
	{
		cout << *vrit << " ";
		++vrit;
	}
	cout << endl;
	// const_reverse_iterator
	vector<int>::const_reverse_iterator vrit2 = v2.rbegin();
	while (vrit2 != v2.rend())
	{
		cout << *vrit2 << " ";
		++vrit2;
	}
	cout << endl;
}

(3).capacity

(1). size_t size()const;

返回容器中有效的元素个数

(2). size_t capacity()const;

返回当前容器的容量

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v(10,2);
	cout<<v.size()<<endl; // 返回有效数据的个数
	cout<<v.capacity()<<endl;// 返回容量的个数
	return 0;
}

(3).void resize (size_t n, T val = T());

1). 当 n 小于容器当前的size，size减少到 n
2). 当 n 大于容器当前的size，小于容器当前的 capacity，size扩充到n，值用val填充
3). 当 n 大于容器当前的capacity，先扩容，再将容器的size扩充n，值用val填充

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	// vs2019下的测试结果，不同编译器的结果可能不同
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5); // size = 5,capacity = 6

	v.resize(2);    // size = 2,capacity = 6
	v.resize(6, 2); // size = 6,capacity = 6
	v.resize(8,3);  // size = 8,capacity = 9
}

(4).void reserve(size_t n);

1). 当n大于容器当前的capacity时，将capacity扩大到n或更大。
2). 当n小于容器当前的capacity时，什么也不做。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5); // size = 5,capacity = 6
	v.reserve(10);  // size = 5,capacity = 10
	v.reserve(6);   // size = 5,capacity = 10
}

注意 :

1). capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。不要固化的认为，顺序表增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。

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

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

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	size_t sz;
	vector<int> foo;
	sz = foo.capacity();
	cout << "making foo grow:" << endl;
	for (int i = 0; i < 100; ++i) {
		foo.push_back(i);
		if (sz != foo.capacity()) {
			sz = foo.capacity();
			cout << "capacity changed: " << sz <<endl;
		}
	}
}
//vs：运行结果：
//making foo grow :
//capacity changed : 1
//capacity changed : 2
//capacity changed : 3
//capacity changed : 4
//capacity changed : 6
//capacity changed : 9
//capacity changed : 13
//capacity changed : 19
//capacity changed : 28
//capacity changed : 42
//capacity changed : 63
//capacity changed : 94
//capacity changed : 141
//g++运行结果：
//making foo grow :
//capacity changed : 1
//capacity changed : 2
//capacity changed : 4
//capacity changed : 8
//capacity changed : 16
//capacity changed : 32
//capacity changed : 64
//capacity changed : 128

(5).bool empty()const;

判断当前容器是否为空

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v(10, 2);
	cout << v.empty() << endl;
	return 0;
}

(4).Element access

(1).

reference operator[] (size_t n);
const_reference operator[] (size_t n) const;

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v(10, 1);
	//使用“下标+[]”的方式遍历容器
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
	return 0;
}

(2).

reference at (size_type n);
const_reference at (size_type n) const;

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v(10, 1);
	//使用“下标+[]”的方式遍历容器
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v.at(i) << " ";
	}
	cout << endl;
	return 0;
}

operator[] 和 at() 的区别

operator[] 和 at() 的区别
operator[] 和 at() 的区别

(5).Modifiers

(1).void push_back (const T& val);
(2).void pop_back();

通过push_back函数对容器进行尾插，pop_back函数对容器进行尾删。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v;
	v.push_back(1); //尾插元素1
	v.push_back(2); //尾插元素2
	v.push_back(3); //尾插元素3
	v.push_back(4); //尾插元素4

	v.pop_back(); //尾删元素
	v.pop_back(); //尾删元素
	v.pop_back(); //尾删元素
	v.pop_back(); //尾删元素
	return 0;
}

(3). insert 和 erase

iterator insert (iterator position, const value_type& val);
void insert (iterator position, size_type n, const value_type& val);
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);
[first,last)

iterator erase (iterator position);
iterator erase (iterator first, iterator last); 
[first,last)

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1;
	v1.insert(v1.begin(),1);
	v1.insert(v1.end(),5,2);
	print(v1);
	vector<int> v2;
	v2.insert(v2.begin(),v1.begin(),v1.end());
	print(v2);

	v2.erase(v2.begin());
	v2.erase(v2.begin(),v2.begin() + 2);
	print(v2);
}

(4). void swap (vector& x);

通过swap函数可以交换两个容器的数据空间，实现两个容器的交换

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(10,1);
	vector<int> v2(10,2);
	v1.swap(v2);
	print(v1);
	print(v2);
}

以上是按位置进行插入或删除元素的方式，若要按值进行插入或删除（在某一特定值位置进行插入或删除），则需要用到find函数。

find函数 :

template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val);

find函数共三个参数，前两个参数确定一个迭代器区间（左闭右开），第三个参数确定所要寻找的值。
find函数在所给迭代器区间寻找第一个匹配的元素，并返回它的迭代器，若未找到，则返回所给的第二个参数。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	
	vector<int>::iterator pos = find(v.begin(),v.end(),3);
	if (pos != v.end())
	{
		v.insert(pos,30);
	}
	pos = find(v.begin(), v.end(), 3);
	v.erase(pos);
}

(5). void clear();

使容器的 size 成为 0

三.vector迭代器失效问题

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

实例一 : 迭代器的意义改变
(vs2019下报错，g++下不报错，因为不同编译器处理不同，但程序都是不对的)
原意是想要删除3，但由于我们插入了30，pos指向了30，迭代器的意义改变。
解决方案 : 重新定位pos的位置

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);//  size = 5,capacity = 6
	
	vector<int>::iterator pos = find(v.begin(),v.end(),3);
	if (pos != v.end())
	{
		v.insert(pos,30);
	}
	print(v);
	// 解决方案
	//pos = find(v.begin(),v.end(),3);
	v.erase(pos);
	print(v);
}

实例二 : 迭代器成为野指针
(vs2019和g++都报错)

在插入之前容器已满，再插入元素会增容(新开一块空间，拷贝数据，释放原空间)，释放掉原空间后，pos成为了野指针

解决方案 : 重新定位pos的位置

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6); // size = 6,capacity = 6
	
	vector<int>::iterator pos = find(v.begin(),v.end(),3);
	if (pos != v.end())
	{
		 v.insert(pos,30);
	}
	print(v);
	// 解决方案
	// pos = find(v.begin(),v.end(),3);
	v.erase(pos);
}

实例三 : 删除偶数
(vs2019无论最后一个数是奇数还是偶数，程序都会崩溃，因为erase()以后vit迭代器已经失效，对失效的迭代器进行++操作导致程序崩溃，g++下最后一个数是偶数会崩溃，因为最后进行erase()时，进行了越界访问，g++下最后一个数是奇数不会崩溃，但如果出现连续的偶数时，程序运行结果依然是错误的)

解决方案 : 利用 erase() 的返回值，erase() 返回删除元素的下一个有效位置

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	// 删除偶数
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);
	v.push_back(7);

	vector<int>::iterator vit = v.begin();
	while (vit != v.end())
	{
		if (*vit % 2 == 0)
			v.erase(vit);
		++vit;
	}
	
	// 解决方案
	vector<int>::iterator vit = v.begin();
	while (vit != v.end())
	{
		if (*vit % 2 == 0)
			vit = v.erase(vit);
		else
			++vit;
	}
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

vector

介绍和基本使用