C++ vector实现

2022-05-22 01:53:20

文章目录

引入
一、成员变量
二、主要接口模拟

引入

vector英文翻译是向量，这个名字可以说是很形象了。vector在C++中是一个可以动态增容的数组，它像string一样拥有一个随机的迭代器，支持随机访问vector的位置。vector可以说就是C语言中的顺序表，但是又有顺序表不具有的优点，比如使用了模板，支持不同类型的vector同时存在。

一、成员变量

每写一个类，我认为应该优先考虑的就是成员变量。但是成员变量往往需要在成员函数的实现过程中确认。还好STL中有实现好的一份，我们参考一下。

namespace my_stl //因为我的vector名字和stl里相同，所以namespace封装一下
{
template<class T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
private:
iterator _start; //指向vector的第一个位置
iterator _finish; //指向vector的最后一个位置的下一个位置
iterator _end_of_storage; //指向vector的容量的最后一个位置的下一个位置
};
}

二、主要接口模拟

我们顺着stl的实现来一步一步走。较简单的只提供代码，不做讲解。

2.1 size && capacity && operator[ ]

size_t size() const{
	return _finish - _start;
}
size_t capacity() const{
	return _end_of_storage - _start;
}
T& operator[](size_t pos){
	assert(pos < size());
	return _start[pos];
}
const T& operator[](size_t pos) const{
	assert(pos < size());
	return _start[pos];
}

2.2 begin && end

iterator begin(){
	return _start;
}
iterator end(){
	return _finish;
}
// const迭代器
const_iterator begin() const{
	return _start;
}
const_iterator end() const{
	return _finish;
}

2.3 默认成员函数

构造函数有好几个版本，只实现几个。

// 无参构造,禁止隐式类型转换
explicit vector()
 :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}
 //一个参数n的构造函数
explicit vector(size_t n, const T& val = T())
:_start(new T[n]), _finish(_start), _end_of_storage(_start + n) {
	for(size_t i = 0; i < n; ++i){
		*(_finish++) = val; 
	}
}
//迭代器构造函数
template <class InputIterator>
  vector (InputIterator first, InputIterator last)
  :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){
  		reserve(last - first);
		while(first != last){
			push_back(*first);
			++first;
		}  
  }
//initializer_list 
vector(initializer_list<T> il){
	auto it = il.begin();
	while(it != il.end()){
		push_back(*it);
		++it;
	}
}

几点注意：前两个构造函数不接受隐式类型转换。后两个代码有大量重复。可以重写。

public:
template <class InputIterator>
  vector (InputIterator first, InputIterator last)
  :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){
    reserve(last - first);
  	range_initialize(first, last);
  }
  
  vector(initializer_list<T> il){
	range_initialize(il.begin(), il.end());
 }
 // 复用的部分
private:
template<class InputIterator>
void range_initialize(InputIterator first, InputIterator last){
	while(first != last){
			push_back(*first);
			++first;
		}  
}

拷贝构造

// traditional 写法
vector(const vector<T>& v)
:_start(new T[v.capacity()])
,_finish(_start)
,_end_of_storage(_start + v.capacity())
{
	for (size_t i = 0; i < v.size(); ++i){
	*(_finish++) = v[i];
  }
}
// mordern写法
  vector(const vector<T>& v)   //拷贝构造现代写法
:_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)   
	{
		     reserve(v.capacity()); //提前开好空间
		 	for (const auto& e : v)
				push_back(e);
	}
	
// 更mordern的写法
void swap(vector<T>& v){
	::swap(_start, v._start);
	::swap(_finish, v._finish);
	::swap(_end_of_storage, v._end_of_storage);
}
vector(const vector<T>& v)
:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
	vector<T> tmp(v.begin(), v.end());
	swap(tmp);
}
// C++ 11  移动构造
vector(vector<T>&& v)
:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
	swap(v);
}

代码中出现的未知函数的实现在下面给出。
operator=

// traditional 写法
vector<T>& operator=(const vector<T>& v){
	if(this != &v){
      vector<T> tmp(v);
	  swap(tmp);
	}
	return *this;
}
// modern写法 pass-by-value
vector<T>& operator=(vector<T> v){
	if(this != &v)
	swap(v);
	return *this;
}
// C++ 11 移动赋值
vector<T>& operator=(vector<T>&& v){
	swap(v);
	return *this;
}

实际上移动赋值可以不用写，因为赋值的现代写法就包括了移动赋值。
析构

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

reserve && resize

vector是可以动态增容的数组，所以自然提供增容函数。

void reserve(size_t n){
	assert(n > capacity());
	size_t sz = size();
	T* tmp = new T[n]; //开空间
	delete[] _start;   //释放旧空间
	for(size_t i = 0; i < size(); ++i){
		tmp[i] = _start[i];
	} //拷贝数据，利用赋值 + 循环

	_start = tmp;
	_finish = _start + sz; //这里不能加上 size(),不然有问题
	_end_of_storage = _start + n;
}

void resize(size_t n, const T& val = T()){
	if(n <= size()){
		_finish = _start + n;
		return ;
	}
	if(n > capacity()){
		reserve(n);
	}
	for(size_t i = size(); i < n; ++i){
		*(_finish++) = val;
	}
}

插入删除操作

void push_back(const T& val){
	/*if(size() == capacity()){
		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);
	}
	*(_finish++) = val; */
	insert(end(), val);
}

void pop_back(){
	assert(size() > 0);
	--_finish;
}

iterator insert(iterator pos, const T& val = T()) //返回迭代器位置，防止迭代器失效
{
	size_t position = pos - _start;
	assert(pos >= _finish && pos <= _finish);
	if(size() == capacity()){
		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);
	}
	
	iterator end = _finish;
	while(end >= _start + position){
		*(end + 1) = *end;
		--end;
	}
	*(_start + position) = val;
	++_finish;
	return _start + position;
}

iterator erase(iterator pos){
	assert(pos >= _finish && pos <= _finish);
	iterator begin = pos;
	while(begin < _finish){
		*begin = *(begin + 1);
		++begin;
	}
	--finish;
	return pos;
}

迭代器失效问题：当我们调用某些使容量变动的函数时，例如reserve，push_back,可能会引起迭代器失效。因为增容可能导致重新开辟空间，导致pos指向释放过的空间。
实际上，vector的删除操作也会导致迭代器失效。但是删除操作不会重新开辟空间。究其原因是pos迭代器对应的值被删除了，导致pos的值锁定的值变了，删除效果变了。
我们可以在使用前对迭代器重新赋值即可。
(全文完)

码农公寓