学习vector底层的必要性

vector 底层通过动态数组实现，学习其内存分配策略，能让我们明白如何避免不必要的内存分配和拷贝操作，迭代器失效问题、扩容策略等

vector类对象基本函数实现

namespace bit
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;

		vector()
			:_start(nullptr)
			,_finish(nullptr)
			,_end_of_storage(nullptr)
		{}

		vector(const vector<T>& v)
			:_start(nullptr)
			,_finish(nullptr)
			,_end_of_storage(nullptr)
		{
			_start = new T[v.capacity()];
			memcpy(_start, v._start, sizeof(T) * v.size());
			_finish = _start + v.size();
			_end_of_storage = _start + capacity();
		}

		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _end_of_storage;
			}
		}
	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

我们这里先了解迭代器的本质也是指针类型，后续会针对迭代器进行详细的本质剖析

传送门：C++效率掌握之STL库：list底层剖析及迭代器万字详解

在这里插入图片描述

此图选自《STL源码剖析》这本书，有时间建议去读一读这本书，会对STL库有更详细且清晰的认识，所以 _start 是头指针，_finish 是有效字节的尾指针，_end_of_storage 是容量的尾指针，实现基本的构造、析构、拷贝，注意都是 iterator 类型，为了方便配合迭代器使用

vector类对象的遍历

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;
}

iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}

operator= 通过值传递 v，会调用 vector 的拷贝构造函数创建一个临时对象，然后将当前对象和这个临时对象进行交换，最后返回当前对象的引用

🔥值得注意的是： 这种实现方式具有异常安全性，如果拷贝构造函数抛出异常，当前对象的状态不会被改变，同时避免了手动管理内存

vector类对象的扩容追加

void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * size());
			delete[] _start;
		}

		_finish = tmp + size();
		_start = tmp;
		_end_of_storage = _start + n;
	}
}

void resize(size_t n, const T& val = T())
{
	if (n < size())
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		while (_finish != _start + n)
		{
			*_finish = val;
			++_finish;
		}
	}
}

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

void pop_back(const T& x)
{
	erase(--end());
}

reserve：注意不要写成 _finish = _start + size()，必须写在 _start = tmp ，因为 size() 的计算依赖于 _start ，所以要在 _start 没有被改变前计算

resize：如果 n 小于当前大小，会截断 vector；如果 n 大于当前大小，会将 vector 扩展到 n 个元素，并使用 val 填充新增的元素

🔥值得注意的是： push_back 函数 reserve 时要判断下是因为扩容是 *2 ，避免空间为 0 时扩容 *2 导致出错

string类对象的插入、删除

iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start && pos <= _finish);

	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
		pos = _start + len;
	}

	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}

	*pos = x;
	++_finish;

	return pos;
}

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

insert：

• 扩容处理： 当容器已满 _finish == _end_of_storage 时，能够自动进行扩容操作，保证有足够的空间插入新元素

• 元素移动逻辑： 通过将插入位置之后的元素依次向后移动一个位置，为新元素腾出空间，实现了在指定位置插入元素的功能

• 返回值： 函数返回指向插入元素的迭代器，方便调用者后续操作

🔥值得注意的是： size_t len = pos - _start 和 pos = _start + len 的目的是通过记录插入位置相对于起始位置的偏移量 len，在扩容后可以正确恢复插入位置

vector类对象的其余操作

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

size_t size() const
{
	return _finish - _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);
}

🔥值得注意的是：

常量正确性是 C++ 编程中的一个重要原则，它确保对象在被声明为 const 时，其状态不会被意外修改。当一个对象被声明为 const 时，只能调用该对象的 const 成员函数。如果没有 const 版本的 [] 运算符，就无法通过 const 对象访问其元素
虽然理论上仅提供 const 版本的 [] 运算符是可行的，但在实际编程中这样做会有诸多局限性，const 版本的 [] 运算符返回的是 const 引用，这意味着通过该运算符获取的元素不能被修改。在很多场景下，我们需要对容器中的元素进行修改操作，如果只有 const 版本的 [] 运算符，就无法实现这一功能

使用memcpy拷贝问题

int main()
{
	 bite::vector<bite::string> v;
	 v.push_back("1111");
	 v.push_back("2222");
	 v.push_back("3333");
	 return 0;
}

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

void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * size());
			delete[] _start;
		}

		_finish = tmp + size();
		_start = tmp;
		_end_of_storage = _start + n;
	}
}