C++---vector模拟实现

一、准备

1、使用模板

在类外部使用模板，保证模拟实现的vector是通用的

template<class T>
class vector
{}；

2、重命名迭代器

typedef T* iterator;
typedef const T* const_iterator;

3、打印

vector类没有流提取功能，手动实现打印

在类外部实现

template<class T>
void print_vector(const vector<T>& v)
{
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}
template<class Container>
void print_container(const Container& v)
{
	for (auto e : v)
	{
		cout << e << ' ';
	}
	cout << endl;
}

二、私有成员

vector使用指针

private:
	iterator _start = nullptr;
	iterator _finish = nullptr;//相当于size
	iterator _end_of_storage = nullptr;//相当于capacity

三、构造与赋值

1、默认构造

vector() = default;//默认值
vector(size_t n, const T& val = T())
{ 
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}

2、拷贝构造

①

vector(const vector<T>& v)
{
	reserve(v.size());
	for (auto& e : v)
	{
		push_back(e);
	}
}

②迭代器拷贝

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

3、析构函数

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

5、赋值重载

void swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator=(vector<T> v)
{
	swap(v);
	return *this;
}

四、功能实现

1、迭代器

iterator begin()
{
	return _start;
}
iterator end()
{
	return _finish;
}
const_iterator begin() const
{
	return _start;
}
const_iterator end() const
{
	return _finish;
}

2、size和capacity

指针相减

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

3、[]重载

T& operator[](size_t i)
{
	assert(i < size());
	return _start[i];
}
//const 版本
const T& operator[](size_t i) const
{
	assert(i < size());
	return _start[i];
}

4、开空间

迭代器失效:给tmp开空间，然后将start中的数据移入tmp，delete start，size是由指针相减返回的，start=tmp，导致start指向的空间改变，但是finish还在原来的位置，最后导致size不再是原来的size，所以在删除start之前要保存old_size；

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

5、尾插

void push_back(const T& x)
{
	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	}
	*_finish = x;
	++_finish;
}

6、任意位置插入

如果空间已经满了，就要先保存pos于start的相对位置，因为开空间的话，start改变，pos的位置就失效了，开空间后要更新pos

iterator insert(iterator pos, const T& val)
{
	assert(pos >= _start);
	assert(pos <= _finish);
	//判断空间是否已满
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		pos = _start + len;
	}
	iterator it = _finish;
	while (it != pos)
	{
		*it = *(it - 1);
		--it;
	}
	*pos = val;
	++_finish;
	return pos;
}

7、尾删

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

8、resize

n<size：start保留前n个数据

n>pos：在start后追加数据val使数据个数到n

void resize(size_t n, const T& val = T())
{
	if (n <= size())
	{
		_finish = _start + n;
	}
	else
	{
		//直接开n的空间
		//reserve(n);
		if (capacity() < n)
		{
			reserve(n < 2 * capacity() ? 2 * capacity() : n);
		}
		while (_finish < _start + n)
		{
			*_finish = val;
			++_finish;
		}
	}
}

9、删除任意位置数据

iterator erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);
	iterator it = pos + 1;
	while (it != pos)
	{
		*(it - 1) = *it;
		it++;
	}
	--_finish;
	return pos;
}