【C++】vector的底层原理及实现

文章目录

• vector的底层结构
• 迭代器
• 容量操作
• • size()
  • capacity()
  • reserve()
  • resize()
  • 默认成员函数
  • • 构造
    • • 无参构造函数
      • 带参构造函数
      • 析构
      • 拷贝构造
      • 赋值重载
      • operator[ ]
      • 插入删除操作
      • • insert()任意位置插入
        • erase()任意位置删除
        • push_back()尾插
        • pop_back()尾删

          vector的底层结构

          我们的目的不是去模拟实现vector，而是更深入地理解vector的底层原理，更好地提升自己。本篇将简单地模拟实现vector，更好地理解它的构造和原理。参考：vector使用说明

          在C++的STL中，vector是最常用的容器之一，底层是一段连续的线性内存空间（泛型的动态类型顺序表），可以支持随机访问。vector可以存储各种类型，int、char、string等，所以它是一种类模板，可以套用各种类型。

          STL标准库中vector的核心是这样定义的，这里的alloc涉及到内存池的知识，我们可以先不用管。

          

          vector的底层会用三个指针，利用三个指针相减来实现动态存储。

          我们自己定义一个vector类

          template
          class vector
          {
          public:
          	typedef T* iterator;//迭代器
          	typedef const T* const_iterator;//常量迭代器
          private:
          	iterator _start;
          	iterator _finish;
          	iterator _end_of_storage;
          }
          

          ---

          迭代器

          vector的迭代器是一个原生指针,他的迭代器和string相同都是操作指针来遍历数据。

          迭代器返回的是存储数据的起始位置和末尾的下一个位置，区间是左开右闭的[_start, _finish)

          实现了迭代器，我们在代码测试时就可以使用范围for了。

          iterator begin()
          {
          	return _start;
          }
          iterator end()
          {
          	return _finish;
          }
          const_iterator begin() const
          {
          	return _start;
          }
          const_iterator end() const
          {
          	return _finish;
          }
          

          ---

          容量操作

          size()

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

          ---

          capacity()

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

          ---

          reserve()

          这个函数十分重要，因为vector许多地方都会用reserve()去扩容，并且还有几个非常容易搞错的地方。

          reserve只能扩容，不能增容，因此要进行判断是否需要扩容，缩容就不进行操作。

          扩容的步骤是：申请一块更大的新空间，再将旧空间数据移动到新空间中，最后释放旧空间。

          下面这种写法有什么问题？

          void reserve(size_t n)
          {
          	if (n > capacity())
          	{
          		//申请新空间
          		T* tmp = new T[n];
          		if (_start)
          		{
          			memcpy(tmp, _start, sizeof(T) * old_size);
          			//释放旧空间
          			delete[] _start;
          		}
          		_start = tmp;
          		_finish = tmp + size();
          		_end_of_storage = _start + n;
          	}
          }
          

          错误一：倒数第二行的_finish没有发生变化

          看这段代码的最后三行，_start先指向新空间的起始位置，_finish再调用size()的话，此刻的size()已经不是当初的size()了。size()的返回值是_finish - _start，而原本的_start已经改变成了tmp，此时_finish的值 = _start + _finish - _start = _finish；所以_finish没有发生变化。

          
          

          解决方法有两种：

          1._start和_finish赋值的顺序调换一下，先改变_finish，再改变_start。

          2.挪动数据前先保留原本的size()；

          我们这里采用第二种写法。

          void reserve(size_t n)
          {
          	if (n > capacity())
          	{
          		T* tmp = new T[n];
          		size_t old_size = size();//保留之前的size
          		if (_start)
          		{
          			memcpy(tmp, _start, sizeof(T) * old_size);
          			delete[] _start;
          		}
          		_start = tmp;
          		_finish = tmp + old_size;
          		_end_of_storage = _start + n;
          	}
          }
          

          2.不能用memcpy去拷贝内容，而用赋值去拷贝内容。

          对于int、char等内置类型，可以使用memcpy不会出问题。对于自定义类型一般也没有问题，但是对于动态申请资源的自定义类型，memcpy就会发生浅拷贝，导致一块空间析构两次。

          比如vector类型，此时的T是string类型。上一篇我们了解过string的底层原理，string底层用的是char*指针_str来存储字符串的地址，因此需要动态申请空间。

          所以我们是在申请的空间（_start）上面又申请了一块空间（_str），如果我们使用memcpy去拷贝_start中的内容到tmp中；就会把申请的_str指向的地址拷贝给tmp，这样_start和tmp中的_str就会指向同一块空间，再执行delete[] _start;的时候就会执行string的析构函数把这块空间释放。

          

          所以不能用memcpy浅拷贝，解决方法：

          一个个遍历用=赋值，对于string这种深拷贝的类，调用的是string的赋值重载完成深拷贝。

          注意：这里的string使用的是STL库中的string类。

          void reserve(size_t n)
          {
          	if (n > capacity())
          	{
          		T* tmp = new T[n];
          		size_t old_size = size();//保留之前的size
          		if (_start)
          		{
          			for (size_t i = 0; i  
           
          resize()
           
          resize函数用于改变vector的大小，调整vector中元素的数量。
           
           
           
          n > size()：多余空间添加元素（第二个参数）
          n 
          	if (n 
          		_finish = _start + n;
          	}
          	else
          	{
          		reserve(n);
          		while (_finish != _start + n)
          		{
          			*_finish++ = val;
          		}
          	}
          }
          }
          
          	resize(n, val);
          }
          
          	if (_start)
          	{
          		delete[] _start;
          		_start = _finish = _end_of_storage = nullptr;
          	}
          }
          
          	reserve(v.size());
          	for (auto& e : v)//引用防止调用拷贝构造
          	{
          		push_back(e);
          	}
          }
          
          	_start = new T[v.size()];
          	for (size_t i = 0; i  
          删除虽然不会扩容（不用保存pos指针的相对位置），但是删除一个元素后，后面的元素都会向前移动，此时迭代器指向空间虽然不变，但内容变成了下一个元素，我们在使用的时候要注意这个问题。
           
          int main()
          {
          	vector v1;
          	v1.push_back(1);
          	v1.push_back(2);
          	v1.push_back(2);
          	v1.push_back(6);
          	auto it = v1.begin();
          	//法一：边使用边更新
          	while (it != v1.end())
          	{
          		if (*it % 2 == 0)
          		{
          			it = v1.erase(it);
          		}
          		else
          		{
          			it++;
          		}
          	}
          	//法二：使用完将迭代器减一，防止++出现走两步的情况
          	while (it != v1.end())
          	{
          		if (*it % 2 == 0)
          		{
          			v1.erase(it);
          			it--;
          		}
          		it++;
          	}
          }
           
          push_back()尾插
           
          实现insert()函数后，我们就可以直接复用。
           
          void push_back(const T& val)
          {
          	/*if (_finish == _end_of_storage)
          	{
          		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
          		reserve(newcapacity);
          	}
          	*_finish++ = val;*/
          	insert(end(), val);
          }
           
          pop_back()尾删
           
          同样直接复用erase()，让erase()自己判断合法性。
           
          void pop_back()
          {
          	/*assert(size() > 0);
              _finish--;*/
          	erase(_finish - 1);
          }
           
          vector模拟实现代码