vector的使用与模拟实现

一、基本接口的调用


#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<algorithm>

using namespace std;

void test_vector1()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	//遍历vector的几种方式
	for (size_t i = 0; i < v.size(); i++)		//1、下标+[]
	{
		cout << v[i] << " ";
	}
	cout << endl;

	vector<int>::iterator it = v.begin();		//2、迭代器
	while (it != v.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	for (auto e : v)			//范围for
	{
		cout << e << " ";
	}
	cout << endl;

	vector<int>::reverse_iterator rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;

	vector<int> v2(++v.begin(), --v.end());		//利用迭代器区间构造对象————区间左闭右开 

	string s("hello world");
	vector<char> v3(s.begin(), s.end());		//其它容器的迭代器只要类型匹配同样适用

	vector<int> v4;
	v4.assign(s.begin(), s.end());				//assign接口类似————中文意思为分配
}

void test_vector2()
{
	vector<int> v;
	v.reserve(10);//开空间改变容量，但不初始化
	//错误访问——————下标引用操作符会检查插入位置是否合法，即小于_size
	//for (size_t i = 0; i < 10; i++)
	//{
	//	v[i] = i;
	//}
	//正确访问
	for (size_t i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	v.resize(20);//开空间+初始化
}

void test_vector3()
{
	int a[] = { 1,2,3,4,5 };
	vector<int> v(a, a + 5);
	//头插
	v.insert(v.begin(), 0);			//第一个参数传入的是迭代器
	//在2前面插入
	vector<int>::iterator pos = find(v.begin(), v.end(), 2);		//find函数位于算法库中algorithm
	if (pos != v.end())		//查找失败会返回end位置的迭代器
	{
		v.insert(pos, 20);
	}
	//sort排序
	sort(v.begin(), v.end());
	sort(v.begin(), v.end(), greater<int>());		//greater<int>是一个仿函数类，需要调用库函数是functional
}

void test_vector4()
{
	int a[] = { 1,2,3,4,5 };
	vector<int> v(a, a + 5);
	//头删
	v.erase(v.begin());		//参数传入下标位置的迭代器，或迭代器区间
	//删除2
	vector<int>::iterator pos = find(v.begin(), v.end(), 2);
	if (pos != v.end())
	{
		v.erase(pos);
	}
}

int main()
{
	test_vector1();
	test_vector2();
	test_vector3();
	test_vector4();
	return 0;
}

vector的重要知识点再回顾

迭代器因insert失效（erase同理）

结论：在insert(pos, x)以后，都认为pos迭代器失效了，不要再去使用pos了。

原因：1、插入可能导致扩容，而异地扩容会导致pos变成“野指针”。
2、就算不扩容，pos指向的位置意义已经变化了，所以也认为失效。

解决方案：insert的返回值是指向新插入元素的迭代器位置。利用返回值赋值给pos即可。

模拟实现vector

	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		vector()
			:_start(nullptr)
			,_finish(nullptr)
			,_endofstorage(nullptr)
		{}
		vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			reserve(v.capacity());
			for (const auto e : v) {
				push_back(e);
			}
		}
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			while (first != last) {
				push_back(*first);
				first++;
			}
		}
		~vector() {
			delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}
		iterator begin() {
			return _start;
		}
		iterator end() {
			return _finish;
		}
		const_iterator begin()const {
			return _start;
		}
		const_iterator end()const {
			return _finish;
		}
		size_t capacity() const{
			return _endofstorage - _start;
		}
		size_t size() const{
			return _finish - _start;
		}
		void reserve(size_t num) {
			if (num > capacity()) {
				size_t sz = size();
				T* tmp = new T[num];
				memcpy(tmp, _start, sz * sizeof(T));
				_start = tmp;
				_finish = _start + sz;
				_endofstorage = _start + num;
			}
		}
		iterator insert(iterator pos, const T& num){
			assert(pos >= begin() && pos <= end());
			if (_finish == _endofstorage) {
				size_t len = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
				pos = _start + len;
			}
			iterator end = _finish - 1;
			while (end >= pos) {
				*(end + 1) = *end;
				end--;
			}
			*pos = num;
			_finish++;
			return pos;
		}
		iterator erase(iterator pos) {
			assert(pos >= begin() && pos < end());
			//删除指定下标的数据，并把其后的数据依次向前挪动
			iterator it = pos + 1;
			while (it != end()){
				*(it - 1) = *it;
				it++;
			}
			--_finish;
			return pos;
		}
		void push_back(const T& num){
			insert(end(), num);
		}
		T& operator[](size_t i) {
			assert(i < size());
			return *(_start + i);
		}
		void swap(vector<T>& v) {
			std::swap(v._start, _start);
			std::swap(v._finish, _finish);
			std::swap(v._endofstorage, _endofstorage);
		}
		vector<T>& operator=(vector<T> v) {
			swap(v);
			return *this;
		}
		void resize(size_t n, const T& val = T()) {
			//开的空间小于size（把超出范围的舍弃）介于size和capacity（初始化_finish以后的空间）
			//大于capacity（要重新开空间，并且初始化_finish以后的空间）
			if (n <= size()){
				_finish = _start + n;
			}
			else{
				if (n > capacity()){
					reserve(n);
				}
				while (_finish < _start + n) {
					*_finish = val;
					_finish++;
				}
			}
		}
	private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;
	};