vector模拟实现

目录

vector框架：

构造函数

size函数

capacity函数

reserve函数

尾插函数 

begin()

end()

operator[]

const迭代器

判断是否为空

resize函数

尾删函数

插入函数：

扩容导致迭代器失效：

迭代器不能重复使用

erase使用之后的迭代器失效问题

例如：

swap函数

clear函数

析构函数

拷贝构造

拷贝构造（现代写法）

n个val构造

reserve函数

---

vector框架：

成员变量是三个迭代器： 

#pragma once
 
namespace zsk
{
	template<class T>
	class vector
	{
	public:
		typedef T*iterator;
	private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;
	};
}

构造函数

vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
		}

size函数

size_t size()const
		{
			return _finish - _start;
		}

capacity函数

size_t capacity()const
		{
			return _endofstorage - _start;
		}

reserve函数

void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldsize = size();
				T*tmp = new T[n];
				if (_start)
				{
					memcpy(tmp, _start, sizeof(T)*oldsize);
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + oldsize;
				_endofstorage = _start + n;
			}
		}

尾插函数 

void Push_back(const T&x)
		{
			if (_finish == _endofstorage)
			{
				size_t NewCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(NewCapacity);
			}
			*_finish = x;
			++_finish;
		}

begin()

iterator begin()
		{
			return _start;
		}

end()

iterator end()
		{
			return _finish;
		}

operator[]

T&operator[](size_t pos)
		{
			assert(pos < size());
			return _start[pos];
		}

const迭代器

iterator begin()const
		{
			return _start;
		}

iterator end()const
		{
			return _finish;
		}

判断是否为空

bool empty()const
		{
			return _start == _finish;
		}

resize函数

void resize(size_t n, T val = T())
		{
			if (n > capacity())
			{
				reserve(n);
			}
			if (n > size())
			{
				while (_finish > _start + n)
				{
					*_finish = val;
					_finish++;
				}
			}
			else
			{
				_finsh = _start + n;
			}
		}

尾删函数

void pop_back()
		{
			assert(!empty());
			_finish--;
		}

插入函数：

void insert(iterator pos, const T&val)
		{
			assert(_pos >= _start);
			assert(_pos <= _finish);
			if (_finish == _endofstorage)
			{
				size_t NewCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(NewCapacity);
			}
			iterator end = _finish;
			while (pos < end)
			{
				*end = *(end - 1);
				--end;
			}
			*pos = val;
			++_finish;
		}

扩容导致迭代器失效：

 vector使用的扩容是异地扩容，如图所示：

发生了扩容，新开辟一个空间拷贝数据，释放旧的空间。

 

pos依旧指向旧空间，这时候旧的空间已经被释放了，导致了pos迭代器失效。

处理方法：在扩容时记录迭代器的相对位置。

void insert(iterator pos, const T&val)
		{
			assert(pos>= _start);
			assert(pos< _finish);
			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;
				size_t NewCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(NewCapacity);
				pos = _start + len;
			}
			iterator end = _finish;
			while (pos < end)
			{
				*end = *(end - 1);
				--end;
			}
			*pos = val;
			++_finish;
		}

迭代器不能重复使用

这里发生的是传值传参，并不会影响外界的it1，虽然我们在内部规避了迭代器失效的问题，但是只要发生了扩容，外部依旧会迭代器失效。

迭代器返回插入函数：

iterator insert(iterator pos, const T&val)
		{
			assert(pos>= _start);
			assert(pos< _finish);
			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;
				size_t NewCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(NewCapacity);
				pos = _start + len;
			}
			iterator end = _finish;
			while (pos < end)
			{
				*end = *(end - 1);
				--end;
			}
			*pos = val;
			++_finish;
			return pos;
		}

erase函数

void erase(iterator pos)
		{
			assert(!empty());
			assert(pos >= _start);
			assert(pos < _finish);
			iterator end = _finish-1;
			while (pos < end)
			{
				*(pos) = *(pos + 1);
				pos++;
			}
			__finish;
		}

erase使用之后的迭代器失效问题

答：erase函数使用之后，迭代器可能会失效，取决于不同的编译器，我们在使用erase之后的迭代器最好不要再使用。

例如：

int main()
{
	/*zsk::func();*/
	std::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);
	std::vector<int>::iterator it1 = v.begin();
	if (it1 != v.end())
	{
		if (*it1 % 2 == 0)
		{
			it1 = v.erase(it1);
		}
		else
		{
			it1++;
		}
	}
	cout << *it1;
	
	return 0;
}

我们在调用erase函数之后，迭代器it1失效，我们要重新给it1赋值才能使用it1.

swap函数

void swap(vector&v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}

clear函数

void clear()
		{
			_finish = _start;
		}

析构函数

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

拷贝构造

template <class InputIterator>
		vector(InputIterator first, InputIterator finish)
			:_start = nullptr
			, _finish = nullptr
			, _endofstorage = nullptr
		{
			while (first != finish)
			{
				Push_back(*first);
				first++;
			}
		}

拷贝构造（现代写法）

vector(const vector&v)
			:_start = nullptr
			, _finish = nullptr
			, _endofstorage = nullptr
		{
			vector tmp(v.begin(), v.end());
			swap(tmp);
		} 

n个val构造

explicit vector(int n, const T& val = T())
			:_start = nullptr
			, _finish = nullptr
			, _endofstorage = nullptr
		{
			reserve(n);
			for (int i = 0; i < n; i++)
			{
				Push_back(val);
			}
		}

reserve函数

void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldsize = size();
				T*tmp = new T[n];
				for (int i = 0; i < oldsize; i++)
				{
					tmp[i] = _start[i];
				}
				delete[] _start;
				_start = tmp;
				_finish = _start + oldsize;
				_endofstorage = _start + n;
			}
		}