vector类详解和模拟实现 #C++

定义和结构

作为一种序列式容器，vector的结构和操作与数组非常相似，不同之处在于vector对内存空间使用的灵活性，由于可以进行容量检测和扩容，vector极大提高了内存的利用率。同时，模板的使用可以使用户便捷地进行各种类型数据的存取和操作。本文参考SGI STL实现一个功能相似的vector容器，以达到深入学习的目的。

vector的逻辑结构和物理结构都是连续的，这点在数据结构_顺序表中已做了详细说明。与传统顺序表不同，本文vector的定义中用三个指针维护容器中的有效数据和内存区域，这样做可以方便获取对应的迭代器，也便于进行元素操作。

template<typename T>
class vector
{
private:
  iterator _start;
  iterator _finish;
  iterator _end_of_storage;
	/*…………*/

迭代器

与string相似，vector维护的是一个连续线性空间，普通指针可以作为vector的迭代器。

public:
  typedef T* iterator;
  typedef T* const_iterator;

  iterator begin()
  {
    return _start;
  }

  const_iterator begin() const
  {
    return _start;
  }

  iterator end()
  {
    return _finish;
  }

  const_iterator end() const
  {
    return _finish;
  }

构造&析构和内存管理

需要注意的是构造函数(3)的调用，因为字面常量默认被看做int类型，所以用数个整型变量构造vector<int>时，由于构造函数(5)的模板参数列表更匹配，所以编译器会误调用构造函数(5)。解决方法为额外写一个第一个参数为int的构造函数，以保证编译器选择函数模板时的正确性。

//construct(1)
vector()
  :_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{ }
//construct(2)
vector(const vector<T>& v)
  :_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
  size_t capa = v.capacity();
  iterator tmp = new T[capa];
  //不能直接使用memcpy，否则会对自定义类型进行浅拷贝
  for (int i = 0; i < v.size(); ++i) {
    tmp[i] = v[i];
  }
  _start = tmp;
  _finish = tmp + v.size();
  _end_of_storage = tmp + capa;
}
//construct(3)
//复用了resize接口，后文会介绍
vector(size_t n, const T& val = T())
{
  resize(n, val);
}
//construct(4)
//针对误调用迭代器构造的问题
vector(int n, const T& val = T())
{
  resize(n, val);
}
//construct(5)
template<typename InputIterator>
vector(InputIterator first, InputIterator end)
{
  //[first, end)
  while (first != end)
  {
    push_back(*first);
    ++first;
  }
}
//析构
~vector()
{
  if (_start)
  {
    delete[] _start;
    _start = _finish = _end_of_storage = nullptr;
  }
}

与string相似，vector支持capacity配置和size配置，并在添加元素时检查容量和自动扩容。需要注意的是，配置空间完成后进行数据拷贝时，不能直接使用memcpy，针对自定义类型，memcpy进行的是浅拷贝，而此时需要逐个调用赋值运算符重载进行深拷贝。

void reserve(size_t n)
{
  if (n > capacity())
  {
    int old_size = size();
    iterator tmp = new T[n];
    if (_start)
    {
      //不能直接使用memcpy
      for (int i = 0; i < old_size; ++i) {
        tmp[i] = (*this)[i];
      }
      delete[] _start;
    }
    _start = tmp;
    _finish = _start + old_size;
    _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;
    }
  }
}

元素访问和操作

元素访问

vector支持下标访问，这可以通过下标访问运算符重载实现。

T& operator[](size_t pos)
{
  assert(pos < size());
  return *(_start + pos);
}

const T& operator[](size_t pos) const
{
  assert(pos < size());
  return *(_start + pos);
}

元素操作

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

void push_back(const T& val)
{
  insert(_finish, val);
}

void pop_back()
{
  assert(size() > 0);
  --_finish;
}

iterator insert(iterator pos, const T& val)
{
  assert(pos >= _start && pos <= _finish);
  if (size() == capacity())
  {
    size_t capacity = size() == 0 ? 4 : size() * 2;
    reserve(capacity);
    //扩容后迭代器可能失效，要在内部更新迭代器
    pos = _start + size();
  }
  iterator end = _finish - 1;
  while (end >= pos)
  {
    *(end + 1) = *end;
    --end;
  }
  *pos = val;
  ++_finish;
  return pos;
}

iterator erase(iterator pos)
{
  assert(pos >= _start && pos <= _finish);
  assert(size() > 0);
  iterator begin = pos + 1;
  while (begin < _finish)
  {
    *(begin - 1) = *begin;
    ++begin;
  }
  --_finish;
  return pos;
}
//赋值运算符的现代写法
vector<T>& operator=(vector<T> v)
{
  swap(v);
  return *this;
}

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

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

vector迭代器失效问题

当对容器进行某些操作后，迭代器已经不再指向原本的有效数据，称这种情况为迭代器失效。

导致vector迭代器失效的情况有两种：

1. 扩容导致迭代器失效。迭代器pos作为一个指针，在扩容操作进行开辟空间、移动数据并释放原空间之后，pos依然指向被释放的就空间的某个位置，即野指针，导致原来的pos迭代器失效。
2. 删除元素导致迭代器失效。删除某个元素后，迭代器pos指向的元素已经不存在，导致迭代器失效。

针对第一种情况，可以在扩容后调整pos的位置，使pos重新指向新空间的旧位置；针对第二种情况，可以设置erase()的返回值为最后一个被删除元素的下一个位置，当删除的是最后一个元素时，返回end迭代器。