c++中STL的vector简单实现

vector

构造函数 vector()

因为给了缺省值所以这里拷贝构造为空
iterator 是迭代器

vector()
{

}
private:
	iterator _str = nullptr;//首个元素的地址
	iterator _size = nullptr;//尾元素的地址
	iterator _capacity = nullptr;//容量

拷贝构造 vector()

三种拷贝构造
1、正常的拷贝构造
2、拷贝一个区间
3、简结写法

vector(int n, const T& val = T())//正常的拷贝构造
	:_str(nullptr)
	, _size(nullptr)
	, _capacity(nullptr)
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}
template <class InputIterator>
vector(InputIterator str, InputIterator size)//拷贝区间
{
	while (str != size)
	{
		push_back(*str);
		++str;
	}
}
vector(const vector<T>& s)//简结写法
{
	vector<T> tmp(s.begin(), s.end());
	swap(tmp);

}

析构函数 ~vector()

delete掉**_str** 让他指向空 然后让尾部元素也指向空 容量也指向空

~vector()
{
	delete[] _str;
	_str = nullptr;
	_size = _capacity = nullptr;
}

iterator 的定义

迭代器的定义在vector里面是指针

typedef T* iterator;
typedef const T* const_iterator;

begin()与const版本

因为我们定义的变量为迭代器的变量并且是指向了头尾的所以我们这直接给他一个头的位置就可以了

const_iterator begin() const
{
	return _str;
}
iterator begin()
{
	return _str;
}

end()与const版本

我们定义变量的时候给的是尾部的位置 所以这里也可以直接返回尾部

const_iterator end() const
{
	return _size;
}
iterator end()
{
	return _size;
}

增删改查

尾插push_back()

void push_back(const T& val)
{
	if (_size == _capacity)//判断容量够不够
	{
		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);
	}
	*_size = val;
	_size++;
}

尾删pop_back()

void pop_back()
{
	assert(!empty());//判空 如果是空还删什么
	return _size--;
}

指定位置插入insert()

这里要判断pos位置是不是在这个有效数据范围之内
然后要把这个_str到pos这个位置的值存起来
如果不存起来会导致reserve的时候会丢失这个pos位置

iterator insert(iterator pos, const T& val)
{
	assert(pos <= _size);
	assert(pos >= _str);
	if (_size == _capacity)
	{
		size_t len = pos - _str;
		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);
		pos = _str + len;
	}
	//memmove(pos + 1, pos, sizeof(T) * (_size - pos));
	iterator end = _size - 1;
	while (end >= pos)
	{
		(*end + 1) = *end;
		--end;
	}
	
	*pos = val;
	_size++;
	return pos;
}

指定位置删除 erase()

依旧判断pos存不存在
往前覆盖

iterator erase(iterator pos)
{
	assert(pos <= _size);
	assert(pos >= _str);
	//memmove(pos, pos + 1, sizeof(T) * (_size - pos));
	iterator it = pos + 1;
	while (it < _size)
	{
		*(it - 1) = *it;
		++it;
	}
	_size--;
	return pos;
}

operator[]与const版本

用下标访问数据

T& operator[](size_t pos)
{
	assert(pos <= size());
	return _str[pos];
}
const T& operator[](size_t n) const
{
	assert(n < size());
	return _str[n];
}

容量

增容reserve()

不一定增容，在不同平台下可能会缩容，但我这不会写缩容

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t old = size();
		T* tmp = new T[n];
		/*if (_str)
		{
			memcpy(tmp, _str, n * sizeof(T));
		}*/
		for (size_t i = 0; i < size(); i++)
		{
			tmp[i] = _str[i];
		}	
		delete[] _str;
		_str = tmp;
		_size = _str + old;
		_capacity = _str + n;
	}
}

设置容量 resize()

设置容量(会缩容)

void resize(size_t n, const T& value = T())
{
	if (n <= size())//当设置的长度比_size都小
	{
		_size = _str + n;
		_capacity = _str + n;
	}
	else if (n > size() && n < capacity())//_size和_capaticy之间
	{
		_capacity = _str + n;
	}
	else//增容
	{
		reserve(n);
		while (_size < _str + n)
		{
			*_size = value;
			_size++;
		}
	}
}

成员函数

swap()

交换2个vector的内容

void swap(vector<T>& s)
{
	std::swap(_str, s._str);
	std::swap(_size, s._size);
	std::swap(_capacity, s._capacity);
}

size()

有效数据个数

size_t size() const
{
	return _size - _str;
}

capacity()

容量大小

size_t capacity() const
{
	return _capacity - _str;
}

empty()

判空

bool empty()//判断是否为空
{
	return _str == _size;
}

clear()

清空vector

void clear()
{
	_str[0] = '\0';
}

front()

返回首元素

vector& front()
{
	return _str;
}

back()

返回尾元素

vector& back()
{
	return _size;
}

迭代器失效问题

如果出现扩容或者说数据的移动会使迭代器失效
在上面中我处理的尽量不失效的方法，但也可能失效，
在使用insert和erase都有可能发生迭代器失效问题