【C++】深入探索：从零开始模拟实现C++中的Vector容器

template<class T>
class vector
{	
private:
	iterator _start;		// 指向数据块的开始
	iterator _finish;		// 指向有效数据的尾
	iterator _endOfStorage;  // 指向存储容量的尾
};

template<class T>  
class vector
{
public:
    //常规迭代器和const迭代器
	typedef T* iterator;
	typedef const T* const_iterator;
    
    //迭代器相关函数
	iterator begin()
	{
		return _start;
	}
	iterator end()
	{
		return _finish;
	}
	const_iterator begin() const
	{
		return _start;
	}
	const_iterator end() const 
	{
		return _finish;
	}

private:  
    //定义成员变量
    iterator _start = nullptr;  
    iterator _finish = nullptr;  
    iterator _endOfStorage = nullptr;  
};

template<class T>  
class vector{  
    // ...  
public:  
    vector() {}  
    // 编译器会自动调用默认初始化列表  
};

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

vector(int n, const T& val = T())
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);//下面会实现
	}
}

//类模板的成员函数可以是函数模板
//使用这个模板，就可以用其他容器的迭代器初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

//v2(v1)
vector(const vector<T>& v)
{
	reserve(v.capacity());//下面会实现
	for (auto e : v)
	{
		push_back(e);
	}
}

//vector<int>v = {1, 2, 3, 4}
vector(initializer_list<T> il)
{
	reserve(il.size());
	for (auto& e : il)
	{
		push_back(e);
	}
}

//v1 = v2
// 
//故意使用传值
//v是v2的拷贝
vector<T>& operator=(vector<T> v)
{
	swap(v);//后面实现
	return *this;
}

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

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

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		//如果T 是string或者vector，使用memcpy就容易造成string的浅拷贝
		// 后面delete[] _start会释放空间，还会对每个string调用析构函数,如果使用memcpy，那么在delete之后，新空间中的string还是析构的string
		//memcpy(tmp, _start, size() * sizeof(T));
		for (int i = 0; i < sz; i++)
		{
			tmp[i] = _start[i];
		}
		delete[] _start;
		_start = tmp;
		//_finish = tmp + size();//这里调用 size() 函数的时候，_start已经发生了变化，此时的返回值（ _finish - _start） 并不是真正的size
		_finish = tmp + sz;
		_end_of_storage = tmp + n;
	}
}

void resize(size_t n, const T& val = T())//调用对应的默认构造,int这些内置类型在模板出来以后也有了自己的构造,如int i = int(1);
{
	if (n > size())
	{
		//插入
		reserve(n);
		while (_finish < _start + n)
		{
			*_finish = val;
			_finish++;
		}
	}
	else
	{
		//删除
		_finish = _start + n;
	}
}

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

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

void insert(iterator pos, const T& val)
{
	assert(pos >= _start);
	assert(pos <= _finish);
	if (_finish == _end_of_storage)
	{
		size_t p = pos - _start;
		reserve(capacity() == 0 ? 4 : 2 * capacity());//原来的空间回收了，pos指向的地址失效
		pos = p + _start;
	}
	iterator it = _finish - 1;
	while (it >= pos)
	{
		*(it + 1) = *it;
		it--;
	}
	*pos = val;
	++_finish;
}

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

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