编程宝库 - 技术改变世界

编程宝库

Search

C语言编程技术

C语言快速掌握位段使用

C++11新特性之右值引用与完美转发详解

C++模拟实现vector的示例代码

1.前言

大家在学习C++的时候一定会学到STL（标准模板库），这是C++标准库中最重要的组成部分，它包含了常用的数据结构和算法。今天呢，我们首先来学习STL中的vector容器

2.vector介绍

vector的数据安排和操作方式与我们平时使用的数组非常相似，唯一的区别在于数组是一个固定空间，而vector的空间可以随着元素的改变而发生改变。

还是和之前一样，vector的使用方式大家可以去查阅官方文档std::vector - cppreference.com

3.vector模拟实现

vector维护的是一个线性空间，所以无论其元素为什么类别，普通指针都可以作为vector的迭代器而满足所有必要条件。vector要和普通数组一样支持随机存取，而普通指针正有这样的能力。

为了维护一个vector我们只需要三个指针，一个使用空间的头，一个使用空间的尾，一个指向可用空间的尾。

第一个和第二个指针的作用我知道，但是为什么要有第三个指针呢？

这是为了降低计算机空间配置的成本，每次申请一块小空间和申请一块大空间的时间成本差不多，所以vector在申请空间的时候，通常会多申请一些空间，以备将来可能的扩充。

template <typename T>
class vector
{
private:
  iterator _start;
  iterator _end;
  iterator _endOfStorage;
public:
  typedef T* iterator;
  typedef const T* const_iterator;

};

3.1 迭代器接口

接下来我们来补充一下vector的迭代器接口，

template <typename T>
class vector
{
private:
  //...
public:
  iterator begin() { return _start; }
  iterator end() { return _end; }
  size_t size() const
  {
      return size_t(_end - _start);
  }
  size_t capacity() const
  {
      return size_t(_endOfStorage - begin());
  }
  bool empty() const 
  {
      return begin() == end();
  }
  T& operator[](size_t n)
  {
      return *(begin() + n);
  }
  T& fornt(){return *begin()};
  T& back() { return *(end() - 1); }
};

vector的迭代器就是原生指针，我们只是将这个原生指针进行一下封装，让使用者按照我们想要的方式来使用即可。

3.2 vector元素操作

3. 2. 1 删除元素

首先，我们实现一个比较简单的操作：pop_back()，将指向使用空间的尾的迭代器向前移动

void pop_back()
{
  if (_end > _start)
  {
      --_end;
  }
}

实现完简单的pop_back，接下来我们去实现一个较为困难的接口，可以在任意位置进行删除的erase接口。

//清除[first, last)的元素
iterator erase(iterator first, iterator last)
{
  assert(first >= _start && last <= _end);
  iterator ret = first;
  while(last != end())
  {
      *first = *last;
      first++;
      last++;
  }
  _end = first;
  return ret;
}

因为我们没有实现空间配置器，所以在这里的删除我们并不释放空间，只是将后面的内容往前挪动后，改变_end的指向就好了。

实现完区间erase之后，之后的位置erase和clear我们都可以去复用了

//清除指定位置元素
iterator erase(iterator positon)
{
  assert(positon + 1 <= end());
  return erase(positon, positon + 1);
}
//清空
void clear()
{
  erase(begin(), end());
}

细心的朋友会发现，erase的返回值不是void，而是起始位置的迭代器，这是为什么呢？

迭代器失效

迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃。

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
  int a[] = {0, 1, 2, 3, 4};
  vector<int> v(a, a + sizeof(a) / sizeof(int));
  //寻找3的位置
  auto p = find(v.begin(), v.end(), 3);
  //删除3
  v.erase(p);
  //访问3
  cout << *p << endl; //输出4
  return 0;
}

erase删除p位置元素后，p位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果p刚好是最后一个元素，删完之后p刚好是end的位置，而end位置是没有元素的，那么p就失效了。

所以为了避免迭代器失效的问题，给erase添加了返回值，通过这个返回值来更新迭代器的值，防止迭代器失效。

3. 2. 2 空间配置

接下来我们来实现对vector的存储空间进行配置的两个接口reserve 和 resize。

首先是reserve，它只需要改变空间大小，并将原本vector空间内的内容拷贝到新空间中即可

void reserve(size_t n)
{
  size_t sz = size();
  //申请空间大于当前空间，扩容
  if (n > capacity())
  {
      T *tmp = new T[n];
      if (_start)
      {
          //将原本空间内容拷贝到新空间
          for (int i = 0; i < size(); ++i)
          {
              tmp[i] = _start[i];
          }
          delete[] _start;
      }
      _start = tmp;
  }
  //改变指针
  _end = _start + sz;
  _endOfStorage = _start + n;
}

接下来是resize，它和reserve有所不同，reserve只是开辟新空间，而resize还可以进行初始化

void resize(size_t n, const T &val = T())
{
  //空间不够，复用reserve进行扩容
  if (n > capacity())
  {
      reserve(n);
  }
  //元素不够，将后面的内容初始化
  if (n > size())
  {
      for (int i = size(); i < n; i++)
      {
          _start[i] = val;
      }
      _end = _start + n;
  }
  else
  {
      _end = _start + n;
  }
}

3. 2. 3 添加元素

这次我们先从比较难的insert开始吧，insert可以在指定位置插入元素

iterator insert(iterator pos, const T &x)
{
  assert(pos >= _start && pos <= _end);
  //空间不够，进行扩容
  if (_end == _endOfStorage)
  {
      size_t n = pos - _start;
      size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
      reserve(newCapacity);
      pos = _start + n;
  }
  
  //挪动数据，给新元素空出位置插入
  iterator finish = _end - 1;
  while (finish >= pos)
  {
      *(finish + 1) = *finish;
      --finish;
  }
  *pos = x;
  ++_end;
  return pos;
}

完成了困难的insert后，我们再去实现简单的push_back

void push_back(const T &x)
{
  //空间不够 扩容
  if (_end == _endOfStorage)
  {
      size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
      reserve(newCapacity);
  }
  *_end = x;
  ++_end;
}

3. 3 构造与析构

构造函数

首先是构造函数，vector的构造函数平时用的比较多的有以下三个版本

//无参构造
vector()
  : _start(nullptr), _end(nullptr), _endOfStorage(nullptr)
{
}
//迭代器区间构造
template <class InputIterator>
vector(InputIterator first, InputIterator last)
  : _start(nullptr), _end(nullptr), _endOfStorage(nullptr)
{
  while (first != last)
  {
      push_back(*first);
      ++first;
  }
}

vector(int n, const T &val)
  : _start(nullptr), _end(nullptr), _endOfStorage(nullptr)
{
  reserve(n);
  while (n--)
  {
      push_back(val);
  }
}

拷贝构造

在这里我选择的是一种比较简单的写法，使用迭代器区间构造函数去创建一个临时对象，然后将临时对象的资源与此对象进行一个互换

vector(const vector<T> &t)
  : _start(nullptr), _end(nullptr), _endOfStorage(nullptr)
{
  vector<T> tmp(t.begin(), t.end());
  swap(tmp);
}

void swap(vector<T> &t)
{
  std::swap(_start, t._start);
  std::swap(_end, t._end);
  std::swap(_endOfStorage, t._endOfStorage);
}

析构函数

析构函数将new出来的空间，delete掉即可

~vector()
{
  if (_start)
  {
      delete[] _start;
      _start = _end = _endOfStorage = nullptr;
  }
}

关于C++模拟实现vector的示例代码的文章就介绍至此，更多相关C++ vector内容请搜索编程宝库以前的文章，希望以后支持编程宝库！

下一节：C++11新特性之右值引用与完美转发详解

C语言编程技术

一、左值与右值顾名思义，左值就是只能放在等号左边的值，右值是只能放在等号右边的值。在C++Prime一书中，对左值和右值的划分为，左值是一个表示数据的表达式，右值是一个即将销毁的值(通常 ...

C语言快速掌握位段使用

C++11新特性之右值引用与完美转发详解