C++ vector容器_vector>

一、vector的介绍

1. vector是表示可变大小数组的序列容器。
2. 它和数组一样，也是采用连续存储空间存储元素，所以同样也可以采用下标对vector的元素进行访问，但是它的大小是动态改变的，也就是说它如果不够用，它会自动增容。

3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小，重新分配一个新的数组，然后将全部元素移到这个数组。

4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。

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

6. 与其它动态序列容器相比， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。

二、vector的使用

1、vector的定义

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v(10); //一个参数
	cout << v.size() << endl;
 
	vector<int> v1(10, 6); //n个val值
 
	for (auto &i : v1)
	{
		cout << i;
	}
	cout << endl;
 
	vector<int> v2 = v1;//拷贝
	for (auto &i : v2)
	{
		cout << i;
	}
	cout << endl;
	vector<int>v3(v1.begin() + 3, v1.end() - 2);//迭代器方法
	for (auto &i : v3)
	{
		cout << i;
	}
	cout << endl;
	system("pause");
	return 0;
}

2、vector iterator的使用

 

int main()
{
	vector<int> v4;
	for (int i = 1; i <= 10; i++)
	{
		v4.push_back(i);
	}
	vector<int>::iterator fi;
	vector<int>::reverse_iterator ri;
	for (fi = v4.begin(); fi != v4.end(); fi++)
	{
		cout << *fi << ' ';
	}
	cout << endl;
	for (ri = v4.rbegin(); ri != v4.rend(); ri++)
	{
		cout << *ri << ' ';
	}
 
	system("pause");
	return 0;
}

3、vector空间增长问题

注：

vs下capacity是按1.5倍增加的，在g++下是按2倍增加的

reserve只负责开辟空间

resize在进行开空间的同时还会进行初始化 

首先，我们先看一下 capacity的变化

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;
	size_t Capacity = v.capacity();
	for (int i = 0; i < 50; i++)
	{
		v.push_back(i);
		if (Capacity != v.capacity())
		{
			Capacity = v.capacity();
			cout << i << " capacity :" << Capacity << endl;
		}
	}
	system("pause");
	return 0;
}

这个是在vs下进行的，可以清楚的看到是以1.5倍增加的 

resize的用法

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector <int> s;
	cout << s.size() << endl;
	for (int i = 0; i < 50; i++)
	{
		s.push_back(i);
	}
	cout << s.size() << endl;
	s.resize(5); //将size置为5
	cout << s.size() << endl;
	s.resize(8, 10);//将size置位8，多余位置用10来填充
	cout << s.size() << endl;
	s.resize(12);//将si'ze置为12，多余位置用0来填充
	cout << s.size() << endl;
	for (int i = 0; i < s.size(); i++)
	{
		cout << s[i] << ' ';
	}
	system("pause");
	return 0;
}

 

从上边的代码以及结果来看 resize()的作用是改变vector中元素的数目。

resize可以有两个参数，第一个是要改变的大小，第二个是扩展的多余空间填充的数字。

如果第一个参数比当前的vector元素数目要小，vector的容量要缩减到resize的第一个参数大小并移除超出第一个参数大小的元素同时销毁他们。

如果第一个参数比当前vector元素数目要大，在vector的末尾扩展需要的元素数目，如果第二个参数指定了，扩展的新元素初始化为第二个指定的元素，否则按类型默认初始化。
 

reserve的使用

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector <int> s;
	cout << " capacity :" << s.capacity() << endl;
	for (int i = 0; i < 50; i++)
	{
		s.push_back(i);
	}
	cout << " capacity :" << s.capacity() << endl;
	s.reserve(100);
	cout << " capacity :" << s.capacity() << endl;
	system("pause");
	return 0;
}

4、vector的增删改查

push_back、pop_back的用法

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;
	for (int i = 0; i <= 10; i++)
	{
		v.push_back(i);
	}
	for (auto & i : v)
	{
		cout << i << ' ';
	}
	cout << endl;
	v.pop_back();
	v.pop_back();
	for (auto & i : v)
	{
		cout << i << ' ';
	}
	system("pause");
	return 0;
}

find、insert、erase的用法 

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;
	for (int i = 0; i <= 5; i++)
	{
		v.push_back(i);
	}
	for (auto & i : v)
	{
		cout << i << ' ';
	}
	cout << endl;
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
	//使用find查找3所在的位置
	v.insert(pos,30);//在pos位置前插入30
	for (auto & i : v)
	{
		cout << i << ' ';
	}
	cout << endl;
	pos = find(v.begin(), v.end(), 3);
	v.erase(pos);//删除pos所在位置的数据
	for (auto & i : v)
	{
		cout << i << ' ';
	}
	cout << endl;
	system("pause");
	return 0;
}

swap、operator[]的用法 

#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
	int a[] = { 1, 2, 3, 4, 5 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	v[0] = 10;//通过[]来读写第0个位置
	cout << v[0] << endl;
 
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << ' '; //通过[i]的方式遍历vector
	}
	cout << endl;
 
	vector<int> tmp;
	tmp.swap(v);
	cout << "v的内容 :";
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << ' '; 
	}
	cout << endl;
 
 
	cout << "tmp的内容 :";
	for (int i = 0; i < tmp.size(); i++)
	{
		cout << tmp[i] << ' '; 
	}
	cout << endl;
	system("pause");
	return 0;
}

 

三、迭代器失效的问题

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
	vector<int> v;
	for (int i = 0; i <= 5; i++)
	{
		v.push_back(i);
	}
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
	v.erase(pos); //删除pos位置的数据，导致pos迭代器失效
	cout << *pos << endl; //这样会导致非法访问
 
	
	vector<int>::iterator pos1 = find(v.begin(), v.end(), 3);
	v.insert(pos1,30); //在pos1位置前插入数据，导致pos1迭代器失效
	//insert会导致迭代器失效，是因为insert可能会导致增容，增容后pos1还指向原来的空间，而原来的空间已经被释放了
	cout << *pos1 << endl; //这样会导致非法访问
 
 
	system("pause");
	return 0;
}

 

四、模拟实现vector

namespace Jiang
{
 
	template <class T>
	class vector
	{
		T * m_start;
		T * m_finish;
		T * m_endOfStorage;
	public:
		typedef T * iterator;
		typedef const T * const_iterator;
 
		vector() :
			m_start(nullptr),
			m_finish(nullptr),
			m_endOfStorage(nullptr)
		{
 
		}
 
		vector(int n, const T &val = T()) :
			m_start(nullptr),
			m_finish(nullptr),
			m_endOfStorage(nullptr)
		{
			reserve(n);
 
			for (int i = 0; i < n; i++)
			{
				m_start[i] = val;
			}
			m_finish = m_start + n;
		}
 
		vector(T * start, T * end) :
			m_start(nullptr),
			m_finish(nullptr),
			m_endOfStorage(nullptr)
		{
			int _size = end - start;
			reserve(_size);
 
			for (int i = 0; i < _size; i++)
			{
				m_start[i] = start[i];
			}
			m_finish = m_start + _size;
		}
 
		iterator begin()
		{
			return m_start;
		}
 
		iterator end()
		{
			return m_finish;
		}
 
		size_t size()
		{
			return m_finish - m_start;
		}
 
		size_t capacity()
		{
			return m_endOfStorage - m_start;
		}
 
		T & operator [] (int i)
		{
			return m_start[i];
		}
 
		const T & operator [] (int i) const
		{
			return m_start[i];
		}
 
		void reserve(size_t _size)
		{
			int _capacity = capacity();
 
			if (_capacity < _size)
			{
				if (_capacity == 0)
				{
					_capacity = 1;
				}
 
				while (_capacity < _size)
				{
					_capacity *= 2;
				}
			}
 
			T * tmp = new T[_capacity];
			m_endOfStorage = tmp + _capacity;
			int oldsize = size();
			m_finish = tmp + oldsize;
			if (m_start != nullptr)
			{
				for (int i = 0; i < oldsize; i++)
				{
					tmp[i] = m_start[i];
				}
				delete[] m_start;
			}
			m_start = tmp;
		}
 
		void resize(size_t _size, const T &val = T())
		{
			reserve(_size);
 
			for (int i = size(); i < _size; i++)
			{
				m_start[i] = val;
			}
 
			m_finish = m_start + _size;
		}
 
		iterator insert(iterator pos, const T &val)//insert防止迭代器失效，返回的是一个迭代器
		{
			int tmp = pos - m_start;
			reserve(size() + 1);
			pos = m_start + tmp;
 
			int i;
			for (i = size() - 1; i >= pos - m_start; i--)
			{
				m_start[i + 1] = m_start[i];
			}
 
			*pos = val;
 
			m_finish++;
 
			return pos;
		}
 
		iterator insert(iterator pos, int n, const T &val) 
		{
			int tmp = pos - m_start;
			reserve(size() + n);
			pos = m_start + tmp;
 
			int i;
			for (i = size()- 1; i >= pos - m_start; i--)
			{
				m_start[i + n] = m_start[i];
			}
 
			for (i = 0; i < n; i++)
			{
				pos[i] = val;
			}
 
			m_finish += n;
 
			return pos;
		}
 
		iterator insert(iterator pos, const T * start, const T * end)//前置const 不能改内容， 后置const（T * const end）不能改指向
		{
			int tmp = pos - m_start;
			int extsize = end - start;
			reserve(size() + extsize);
			pos = m_start + tmp;
 
			int i;
			for (i = size() - 1; i >= pos - m_start; i--)
			{
				m_start[i + extsize] = m_start[i];
			}
 
			for (i = 0; i < extsize; i++)
			{
				pos[i] = start[i];
			}
 
			m_finish += extsize;
 
			return pos;
		}
 
		iterator erase(iterator pos)
		{
			int i;
 
			for (i = pos - m_start; i < size() - 1; i++)
			{
				m_start[i] = m_start[i + 1];
			}
			m_finish--;
 
			return pos;
		}
 
		iterator erase(iterator start, iterator end)
		{
			int i;
			int extsize = end - start;
 
			for (i = start - m_start; i < size() - extsize; i++)
			{
				m_start[i] = m_start[i + extsize];
			}
			m_finish -= extsize;
 
			return start;
		}
 
		void push_back(const T &val)
		{
			reserve(size() + 1);
 
			*m_finish = val;
			m_finish++;
		}
 
		void pop_back()
		{
			m_finish--;
		}
	};
};

简单测试一下我们自己模拟出来的vector的某些函数