【C++初阶】--- vector容器功能模拟实现-EW帮帮网

1.什么是vector？

在 C++ 里，std::vector 是标准模板库（STL）提供的一个非常实用的容器类，它可以看作是动态数组
在这里插入图片描述

2.成员变量

iterator _start;：指向 vector 中第一个元素的指针。
iterator _finish;：指向 vector 中最后一个元素的下一个位置的指针。
iterator _end_of_storage;：指向 vector 所分配内存空间的末尾的指针。

template<class T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
private:
	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _end_of_storage = nullptr;
}

3.构造函数

3.1默认构造

因为三个成员变量都有缺省值，我们只需要显示写默认构造即可，他们会在初始化链表处初始化。

//写法1：
vector()
{}
//写法2：
vector() = default;//C++11支持强制生成默认构造

3.2拷贝构造

调用 reserve 函数，提前为新 vector 对象分配足够的内存空间，其大小和 v 的元素数量相同，此步骤可以避免后续添加元素时的频繁扩容。
借助范围 for 循环遍历 v 中的每个元素，使用引用 auto& 避免不必要的拷贝（特别是当元素为自定义类型时）。
对 v 中的每个元素，调用 push_back 函数将其添加到新 vector 对象的末尾。

//拷贝构造
vector(const vector<T>& v)
{
	//提前开好空间
	reserve(v.size());

	//如果元素是自定义类型,用引用可以减少拷贝
	for (auto& ch : v)
	{
		//尾插数据
		push_back(ch);
	}
}

3.3迭代器构造函数

迭代器构造函数需要我们传两个迭代器，我们使用范围for将元素尾插至新构造的vector对象中，构造的范围是[first,last)
注意：类模板的成员函数，也可以是函数模板，我们可以将这个迭代器构造函数写成模板，优点是可以用不同的类构造vector对象，前提是元素类型需相同，如：int

//迭代器构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}

3.4半缺省构造函数

我们可以通过半缺省构造函数构造一个有n个val值得vector对象

使用resver提前开好空间，避免后续插入元素时频繁扩容
使用for循环尾插n个值为val的元素，如果不传参使用的是缺省值T()
对于内置类型（如 int、double、char 等），T() 会进行值初始化。对于数值类型，会初始化为 0；对于指针类型，会初始化为 nullptr。
对于自定义类型，T() 会调用该类型的默认构造函数。如果没有显式定义默认构造函数，编译器会自动生成一个（前提是该类没有其他带参数的构造函数

注意：我们使用半缺省构造函数的时候传参需要注意，如下：如果不显示第一个参数是size_t，编译器会优先调用更符合的构造函数，即会上面的迭代器构造函数

//u表示10是size_t类型
vector<int> v1(10u,1);

//用n个val进行构造，T()是匿名对象
vector(size_t n, const T& val = T())
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		//如果用这种，_finish记得++
		//*_finish = val;
		//_finish++;

		push_back(val);
	}
}

4.析构函数

三个指针指向同一块空间的不同位置，使用delete释放的时候我们需要使用指向vector中第一个元素的指针，同一块空间不能进行多次释放。

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

5.iterators

5.1begin()/end()

//普通对象使用
iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}

//const对象使用
const_iterator begin() const
{
	return _start;
}

const_iterator end() const
{
	return _finish;
}

6.内联函数

6.1size()

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

6.2capacity()

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

6.3empty()

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

6.4clear()

void clear()
{
	_finish = _start;
}

6.5swap()

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

6.7=运算符重载

普通写法：

先清除当前vector对象中的所有元素
提前开头看见，避免后续频繁扩容
使用范围for依次将元素尾插至当前vector对象

//赋值运算符重载
vector<T>& operator=(const vector<T>& v)
{
	if (this != &v)
	{
		//先清理原先数据
		clear();
		//提前开好空间
		reserve(v.size());

		//如果数据是自定义类型可以减少拷贝
		for (auto& ch : v)
		{
			push_back(ch);
		}
	}
	return *this;
}

现代写法：

//赋值运算符重载，现代写法
//这里是拷贝，不是引用，且不加const
vector<T>& operator=(vector<T> v)
{
	swap(v);
	return *this;
}

6.8[]运算符重载

//普通对象使用
T& operator[](size_t i)
{
	//i不能越界
	assert(i < size());

	return _start[i];
}

//const对象使用
const T& operator[](size_t i) const
{
	//i不能越界
	assert(i < size());

	return _start[i];
}

7.尾插/尾删元素

7.1push_back()

判断空间是否已满，已满需进行扩容操作，使用三木操作符，如果当前vector对象空间对空，扩容至4个元素，不为空则选择2倍扩容。
尾插元素，_finish指针向后移动一位

//尾插
//如果是自定义类型，用引用可以减少拷贝
void push_back(const T& x)
{
	//扩容
	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	}
	*_finish = x;
	_finish++;
}

7.2pop_back()

判断当前vector对象中是否还剩余元素，元素为0则断言失败
还有元素则将_finish指针前移一位

//尾删
void pop_back()
{
	//判空
	assert(!empty());
	_finish--;
}

8.在pos位置插入删除元素

8.1insert()

判断pos位置的有效性，可插入范围为[_start,_finish]
判断空间是否足够，不够则进行扩容操作
注意：如果进行扩容操作，则会造成迭代器失效，需要更新下迭代器
将pos位置及之后的数据向后移动一位
在pos位置插入元素，返回pos位置的迭代器

//在pos位置插入数据
iterator insert(iterator pos, const T& x)
{
	//pos有效性
	assert(pos >= _start && pos <= _finish);

	//扩容
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		//扩容后pos迭代器会失效,需要更新一下
		pos = _start + len;
	}

	//将pos及之后的数据往后移动一位
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}

	*pos = x;
	++_finish;

	return pos;
}

8.2erase()

判断pos位置的有效性，可删除范围为[_start,_finish)
将pos之后的数据向前移动一位，将pos位置的数据进行覆盖
别忘了将_finish指针也前移一位

//删除pos位置的数据
template<class T>
void vector<T>::erase(iterator pos)
{
	//pos有效性
	assert(pos >= _start && pos < _finish);

	//向前移动数据
	iterator it = pos + 1;
	while (it != end())
	{
		*(it - 1) = *it;
		it++;
	}
	--_finish;
}

9.空间大小和数据大小调整

9.1resize()

将vector对象中的数据个数调整至n个，如果n小于当前元素个数，将当前元素个数调整为n，如果n大于当前元素个数，使用val对其进行填充。

//调整长度
template<class T>
void vector<T>::resize(size_t n, T val)
{
	//n小于长度，缩减长度
	if (n < size())
	{
		_finish = _start + n;
	}
	//n大于长度，在后面补元素
	else
	{
		//可能需要扩容
		reserve(n);
		//从原数据结尾开始补
		while (_finish < _start + n)
		{
			//*_finish = val;
			//_finish++;
			push_back(val);
		}
	}
}

9.2reserve()

将空间大小扩容至n，如果n小于当前空间大小，不进行操作和改变

保存旧空间大小old_size,否则后续：
_start = tmp;
_finish = tmp + size();
而size()是_finish-_start,从而_finish = tmp + size()=_start+_finish-_start=_finish
new新空间，大小为n
将原对象内容进行深拷贝，不能使用memcpy进行拷贝
释放原空间，更新成员变量

template<class T>
void vector<T>::reserve(size_t n)
{
	//n大于空间大小才扩容
	if (n > capacity())
	{
		size_t old_size = size();
		//new个新空间
		T* tmp = new T[n];
		//memcpy对于内置类型是深拷贝，对于自定义类型是浅拷贝,所以不能用memcpy
		//memcpy(tmp, _start, size() * sizeof(T));
		for (size_t i = 0; i < size(); i++)
		{
			tmp[i] = _start[i];
		}

		//销毁旧空间数据
		delete[] _start;
		_start = tmp;
		_finish = tmp + old_size;
		_end_of_storage = tmp + n;
	}
}

10打印vector对象内容

C++规定：没有实例化的类模板里取东西，编译器不能区分这里的const_vector是类型还是变量，在前面加上typename表示取的是类型。
当然也可以使用auto自动识别类型。

//打印顺序表的模板
template<class T>
void print_vector(const vector<T>& v)
{
	//auto it = v.begin();
	typename vector<T>::const_iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	/*	for (auto ch : v)
		{
			cout << ch << " ";
		}
		cout << endl;*/
}

通用打印模板：

//通用打印模板
template<class Container>
void print_vector(const Container& v)
{
	auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	
	//或者
	//for (auto ch : v)
	//{
	//	cout << ch << " ";
	//}
	//cout << endl;
}

【C++初阶】--- vector容器功能模拟实现