vector类

海盗船长

发布于 2020-08-27 17:30:48

7160

发布于 2020-08-27 17:30:48

文章被收录于专栏：基础知识文章基础知识文章

1.vector的介绍和使用

1.vector的介绍

vector是表示可变大小数组的序列容器。
就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。

2 vector的使用

vector的定义

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

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> a;
	vector<int> b(6, 10);
	vector<int> c(b);
	vector<int> d(c.begin(), c.end());

	for (int i = 0; i < a.size(); i++)
		cout << a[i] << " ";
	cout << endl;
	for (int i = 0; i < b.size(); i++)
		cout << b[i] << " ";
	cout << endl;
	for (int i = 0; i < c.size(); i++)
		cout << c[i] << " ";
	cout << endl;
	for (int i = 0; i < d.size(); i++)
		cout << d[i] << " ";
	cout << endl;
	int e[] = { 3, 43, 2, 3435, 2, 65, 7, 8, 2, 7, 54 };
	vector<int> f(e, e + sizeof(e) / sizeof(e[0]));
	for (int i = 0; i < f.size(); i++)
		cout << f[i] << " ";
	cout << endl;
	system("pause");
	return 0;
}

vector的迭代器iterator的定义

iterator的使用	接口说明
begin()	获取第一个数据位置的iterator
end()	获取最后一个数据的下一个位置的iterator
rbegin()	获取最后一个数据位置的reverse_iterator
rend()	获取第一个数据前一个位置的reverse_iterator
cbegin()	获取第一个数据位置的const_iterator
cend()	获取最后一个数据的下一个位置的const_iterator

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> ans;
	ans.push_back(1);
	ans.push_back(2);
	ans.push_back(3);
	ans.push_back(4);
	ans.push_back(5);

	//使用迭代器进行遍历
	vector<int>::iterator it = ans.begin();
	while (it != ans.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	//使用迭代器进行修改
	it = ans.begin();
	while (it != ans.end())
	{
		*it=*it * 2;
		it++;
	}
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << " ";
	cout << endl;

	//使用逆向迭代器进行迭代
	vector<int>::reverse_iterator rit = ans.rbegin();
	while (rit != ans.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
	system("pause");
	return 0;
}

vector空间增长的问题

容量空间	接口说明
size()	获取数据个数
capacity()	获取容量大小
empty()	判断是否为空
void resize (size_type n, value_type val = value_type());	改变vector的size
void reserve (size_type n);	改变vector放入capacity

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。不要固化的认为，顺序表增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
resize在开空间的同时还会进行初始化，影响size。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> ans;
	int sz = ans.capacity();
	for (int i = 0; i < 100; i++)
	{
		ans.push_back(i);
		if (sz != ans.capacity()) {
			sz = ans.capacity();
			std::cout << "capacity changed: " << sz << '\n';
		}
	}
	system("pause");
	return 0;
}

vector的增删查改

vector增删查改	接口说明
void push_back (const value_type& val);	尾插
void pop_back();	尾删
InputIterator ﬁnd (InputIterator ﬁrst, InputIterator last, const T& val);	查找。（注意这个是算法模块实现，不是vector的成员接口）
iterator insert (iterator position, const value_type& val);	在position之前插入val
iterator erase (iterator position);	删除position位置的数据
void swap (vector& x);	交换两个vector的数据空间
reference operator[] (size_type n);	像数组一样访问

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	vector<int> ans;
	ans.push_back(1);
	ans.push_back(2);
	ans.push_back(3);
	ans.push_back(4);
	ans.push_back(5);
	//删除尾部
	ans.pop_back();
	//使用迭代器查找
	vector<int>::iterator it = find(ans.begin(), ans.end(), 3);
	//插入
	ans.insert(it, 50);
	//使用迭代器遍历
	it = ans.begin();
	while (it != ans.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
	system("pause");
	return 0;
}

vector 迭代器失效问题

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main()
{
    int a[] = { 1, 2, 3, 4 };
    vector<int> v(a, a + sizeof(a) / sizeof(int));
 
    // 使用find查找3所在位置的iterator
    vector<int>::iterator pos = find(v.begin(), v.end(), 3);
 
    // 删除pos位置的数据，导致pos迭代器失效。
    v.erase(pos);
    cout << *pos << endl; // 此处会导致非法访问
 
    // 在pos位置插入数据，导致pos迭代器失效。
    // insert会导致迭代器失效，是因为insert可
    // 能会导致增容，增容后pos还指向原来的空间，而原来的空间已经释放了。
    pos = find(v.begin(), v.end(), 3);
    v.insert(pos, 30);
    cout << *pos << endl; // 此处会导致非法访问
 
    return 0;
}

2.vector深度剖析及模拟实现

vector深度剖析

vector的模拟实现

#include<iostream>
#include<string>
#include<assert.h>
using namespace std;
namespace fxl
{
	template<class T>
	class vector
	{
	public:
		typedef T* Iterator;
		typedef const T* ConstIterator;
		Iterator Begin(){ return _start; }
		Iterator End(){ return _finish; }

		ConstIterator CBegin(){ return _start; }
		ConstIterator CEnd(){ return _finish; }

		size_t Size(){ return _finish - _start; }
		size_t Capacity(){ return _endOfStorage - _start; }

		vector()
		:_start=nullptr
		,_finish=nullptr
		,_endOfStorage=nullptr
		{}

		vector(int n, const T& value = T())
		:_start=nullptr
		,_finish=nullptr
		,_endOfStorage=nullptr
		{
			Reserve(n);
			while (n--)
			{
				Push_Back(value);
			}
		}

		template<class InputIterator>
		Vector(InputIterator first, InputIterator last)
		{
			Reserve(last - first);
			while (first!=last)
			{
				Push_Back(*first);
				first++:
			}
		}

		vector(const vector<T>& v)
			:_start=nullptr
			,_finish=nullptr
			,_endOfStorage=nullptr
		{
			Reserve(v.Capacity());
			Iterator it = Begin();
			const vit = v.CBegin();
			while (vit != v.CEnd())
			{
				*it++ = *vit++;
			}
			_finish = _start + v.Size();
			_endOfStorage = _start + v.Capacity();
		}

		vector<T>& operator= (vector<T> v)
		{
			swap(v);
			return *this;
		}

		~vector()
		{
			delete[] _start;
			_start = _finish = _endOfStorage = nullptr;
		}

		void Reserve(size_t n)
		{
			if (n > Capacity())
			{
				size_t size = Size();
				T tmp = new T[n];
				if (_start)
				{
					for (size_t i = 0; i < size; ++i)
						tmp[i] = _start[i];
				}
				_start = tmp;
				_finish = _start + size;
				_endOfStorage = _start + n;
			}
		}

		void Resize(size_t n, const T& value = T())
		{
			if (n < Capacity())
			{
				_finish = _start + n;
				return;
			}
			else
			{
				Reserve(n);
			}
			Iterator it = _finish;
			Iterator _finish = _start + n;
			while (it != _finish)
			{
				*it++ = value;
			}
		}

		void Swap(Vector<T>& v)
		{
			swap(_start, v._start);
			swap(_finish, v._finish);
			swap(_endOfStorage, v._endOfStorage);
		}

		void PushBack(const T& x)
		{
			Insert(End(), x);
		}

		void PopBack()
		{
			Erase(--End());
		}

		Iterator Insert(Iterator pos, const T& x)
		{
			assert(pos <= _finish);
			//如果空间不足就增容
			if (_finish == _endOfStorage)
			{
				size_t size = Size();
				size_t newCapacity = Capacity == 0 ? 1 : Capacity() * 2;
				Reserve(newCapacity);
				//如果发生增容，需要重置pos
				pos = _start + size;
			}
			Iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;
			return pos;
		}

		Iterator Erase(Iterator pos)
		{
			// 挪动数据进行删除
			Iterator begin = pos + 1;
			while (begin != _finish) {
				*(begin - 1) = *begin;
				++begin;
			}
			--_finish;
			return pos;
		}

		T& operator[](size_t pos)
		{
			return _start[pos];
		}
	private:
		Iterator _start;        // 指向数据块的开始
		Iterator _finish;       // 指向有效数据的尾
		Iterator _endOfStorage;
	};
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-03-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法