【C++】—— vector模拟实现-阿里云开发者社区

vector 接口预览

namespace HL
{
  template<class T>
  class vector
  {
    //迭代器iterator
    typedef T* iterator;
    typedef const T* const_iterator;

  public:
    //默认成员函数
    vector();
    vector(size_t n, const T& val = T());
    vector(int n, const T& val = T());
    vector(const vector& v);
    template<class InputIterator>
    vector(InputIterator first, InputIterator last);
    ~vector();
    vector<T>& operator=(vector v);
    //Iterator
    iterator& begin();
    iterator& end();
    const_iterator begin() const;
    const_iterator& end() const;
    //Capacity
    size_t size() const;
    size_t capacity() const;
    bool empty() const;
    void reserve(size_t n);
    void resize(size_t n, const T& val = T());
    //Modifiers
    void push_back(const T& val);
    void pop_back();
    void insert(iterator pos, const T& val);
    template<class InputIterator>
    void insert(iterator pos, InputIterator first, InputIterator last);
    iterator erase(iterator pos);
    void swap(vector<T>& v);
    //Element access:
    T& operator[](size_t i);
    const T& operator[](size_t i) const;
    
  private:
    iterator start;
    iterator finish;
    iterator end_of_storage;
  };

};

vector模拟实现

vector成员变量

vector成员变量，和顺序表的成员变量有所不同，不再是指针、size和capacity了，而是迭代器 start、finish和end_of_storage。

start指向起始位置、finish指向最后一个数据的下一个位置（表示数据的末尾）、end_of_storage指向这一块空间的最后。

默认成员函数

构造函数

1、无参构造

无参构造，就是默认构造函数，将成员变量都初始化成nullptr。

vector()
  :start(nullptr)
  ,finish(nullptr)
  ,end_of_storage(nullptr)
{}

2、构造并初始化成n个val值

理论上，我们只需要写一个函数vector(size_t n, const T& val = T());即可，但是如果两个参数都是int类型，（即vector v(5,1);）编译器在编译时，认为T已经实例化成了int，对于两个int类型，编译器就会选择更为匹配的模版

template vector(InputIterator first, InputIterator last);

所以这里写一个vector(int n, const T& val = T()); 让上面这种情况匹配这个函数。

vector(size_t n, const T& val = T())
{
  start = new T[n];
  for (size_t i = 0; i < n; i++)
  {
    start[i] = val;
  }
  end_of_storage = finish = start + n;
}
vector(int n, const T& val = T())
{
  start = new T[n];
  for (int i = 0; i < n; i++)
  {
    start[i] = val;
  }
  end_of_storage = finish = start + n;
}

3、使用一段迭代器区间进行初始化

使用迭代器区间进行初始化，这里不一定是vector的迭代器，所以写成模板。

template<class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
      size_t sz = last - first;
      start = new T[sz];
      finish = start;
      while (first != last)
      {
        *finish = *first;
        ++finish;
        ++first;
      }
      end_of_storage = start + sz;
    }

4、拷贝构造

这里要注意，需要深拷贝，而不是浅拷贝。

vector(const vector& v)
    {
      size_t sz = v.size();
      size_t cp = v.capacity();
      start = new T[sz];
      for (int i = 0; i < sz; i++)
      {
        start[i] = v[i];
      }
      finish = start + sz;
      end_of_storage = start + cp;
    }

析构函数

析构函数比较简单，释放动态开辟的空间即可。

~vector()
    {
      if (start)
        delete[] start;
      start = finish = end_of_storage = nullptr;
    }

赋值运算符重载

赋值运算符重载，这个编译器自动生成的是浅拷贝，我们需要写一个深拷贝的。

这里有多种写法，首先就是传统写法，我们自己释放、开辟空间再拷贝数据

vector<T>& operator=(const vector& v)
    {
      if (start)
        delete[] start;
      size_t sz = v.size();
      start = new T[sz];
      for (int i = 0; i < sz; i++)
      {
        start[i] = v[i];
      }
      finish = end_of_storage = start + sz;
    }

还有现代写法，我们这里传参不使用引用，而使用传值传参；这样生成的形参对象再与我们的this(对象)进行交换；这样形参出了作用域就自动调用析构函数，不用我们去处理了。（这个需要先实现交换函数）

vector<T>& operator=(vector v)
    {
      swap(v);
      return *this;
    }

注意事项： 在赋值的过程中没有使用memcpy函数，因为这个函数只是将数值拷贝过去(浅拷贝)；

如果我们vector 示例化是vector 这样的自定义类型，使用浅拷贝就可能会出现问题；所以这里采用一个一个进行赋值操作，这样就会去调用自定义类型的赋值运算符重载；而不只是简单的浅拷贝了。

iterator 迭代器

vector 的迭代器这里实现的是原生指针；迭代器相关函数：begin()、end()这些都比较简单就不过多描述了。

//迭代器iterator
    typedef T* iterator;
    typedef const T* const_iterator;
    iterator& begin()
    {
      return start;
    }
    iterator& end()
    {
      return finish;
    }
    const_iterator begin() const
    {
      return start;
    }
    const_iterator& end() const
    {
      return finish;
    }

Capacity

capacity容量相关的函数，主要在于调整空间大小和设置内容。

size、capacity、empty

size_t size() const
    {
      return finish - start;
    }
    size_t capacity() const
    {
      end_of_storage - start;
    }
    bool empty() const
    {
      return start == finish;
    }

reserve

reserve，调整空间大小；即扩容。

void reserve(size_t n)
    {
      if (n > capacity())
      {
        iterator tmp = T[n];
        size_t sz = size();
        for (int i = 0; i < sz; i++)
        {
          tmp[i] = start[i];
        }
        if (start)
          delete[] start;
        start = tmp;
        finish = start + sz;
        end_of_storage = start + n;
      }
    }

resize()

void resize(size_t n, const T& val = T())
    {
      reserve(n);
      if (n < size())
      {
        finish = start + n;
      }
      else {
        for (int i = size(); i < n; i++)
        {
          start[i] = val;
        }
        finish = start + n;
      }
    }

Modifiers

modifiers 增删查改、vector头插头删效率很低，就不提供头插头删接口了。

push_back、pop_back

尾差、尾删，直接在vector最后插入删除数据。

void push_back(const T& val)
    {
      if (capacity() == size())
      {
        size_t n = (capacity() == 0) ? 4 : 2 * capacity();
        reserve(n);
      }
      *finish = val;
      ++finish;
    }
    void pop_back()
    {
      assert(start != finish);
      --finish;
    }

insert

insert函数，在某个位置插入n(可以是1)个数据。或者插入一段迭代器区间的数据。

iterator insert(iterator pos, const T& val)
{
  // 空间不够先进行增容
  if (finish == end_of_storage)
  {
    size_t newCapacity = (capacity() == 0) ? 1 : capacity() * 2;
    reserve(newCapacity);
    // 如果发生了增容，需要重置pos
    pos = _start + size();
  }
  //挪动数据
  iterator p = finish;
  while (p != pos)
  {
    *p = *(p - 1);
    --p;
  }
  *pos = val;
  finish += 1;
  return pos;
}
template<class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last)
{
  //这里如果迭代器不是原生指针或者内存空间不连续就不能进行 - 操作了
  size_t sz = last - first;
  size_t n = pos - start;
  reserve(sz + size());
  pos = start + n;
  //挪数据
  iterator p = finish - 1;
  while (p >= pos)
  {
    *(p + sz) = *p;
    --p;
  }
  //插入数据
  for (size_t i = 0; i < sz; i++)
  {
    pos[i] = first[i];
  }
  finish += sz;
}

这里，扩容之后还用一个迭代器失效问题，需要重新给pos赋值。

erase

erase就是删除某个位置的数据，直接将后面数据往前移动即可

iterator erase(iterator pos)
    {
      size_t sz = finish - pos;
      for (int i = 0; i < sz; i++)
      {
        pos[i] = pos[i + 1];
      }
      finish -= 1;
      return pos;
    }

clear、swap

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 clear()
    {
      finish = start;
    }

Element access

operator[ ]

下标访问，直接返回start[i]即可。

T& operator[](size_t i)
    {
      return start[i];
    }
    const T& operator[](size_t i) const
    {
      return start[i];
    }

代码总览

#pragma once
#include<iostream>
#include<assert.h>
namespace HL
{
  template<class T>
  class vector
  {
    //迭代器iterator
    typedef T* iterator;
    typedef const T* const_iterator;
  public:
    //默认成员函数
    vector()
      :start(nullptr)
      ,finish(nullptr)
      ,end_of_storage(nullptr)
    {}
    vector(size_t n, const T& val = T())
    {
      start = new T[n];
      for (size_t i = 0; i < n; i++)
      {
        start[i] = val;
      }
      end_of_storage = finish = start + n;
    }
    vector(int n, const T& val = T())
    {
      start = new T[n];
      for (int i = 0; i < n; i++)
      {
        start[i] = val;
      }
      end_of_storage = finish = start + n;
    }
    vector(const vector& v)
    {
      size_t sz = v.size();
      size_t cp = v.capacity();
      start = new T[sz];
      for (int i = 0; i < sz; i++)
      {
        start[i] = v[i];
      }
      finish = start + sz;
      end_of_storage = start + cp;
    }
    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
      size_t sz = last - first;
      start = new T[sz];
      finish = start;
      while (first != last)
      {
        *finish = *first;
        ++finish;
        ++first;
      }
      end_of_storage = start + sz;
    }
    ~vector()
    {
      if (start)
        delete[] start;
      start = finish = end_of_storage = nullptr;
    }
    /*vector<T>& operator=(vector v)
    {
      swap(v);
      return *this;
    }*/
    vector<T>& operator=(const vector& v)
    {
      if (start)
        delete[] start;
      size_t sz = v.size();
      start = new T[sz];
      for (int i = 0; i < sz; i++)
      {
        start[i] = v[i];
      }
      finish = end_of_storage = start + sz;
    }
    //Iterator
    iterator& begin()
    {
      return start;
    }
    iterator& end()
    {
      return finish;
    }
    const_iterator begin() const
    {
      return start;
    }
    const_iterator& end() const
    {
      return finish;
    }
    //Capacity
    size_t size() const
    {
      return finish - start;
    }
    size_t capacity() const
    {
      end_of_storage - start;
    }
    bool empty() const
    {
      return start == finish;
    }
    void reserve(size_t n)
    {
      if (n > capacity())
      {
        iterator tmp = T[n];
        size_t sz = size();
        for (int i = 0; i < sz; i++)
        {
          tmp[i] = start[i];
        }
        if (start)
          delete[] start;
        start = tmp;
        finish = start + sz;
        end_of_storage = start + n;
      }
    }
    void resize(size_t n, const T& val = T())
    {
      reserve(n);
      if (n < size())
      {
        finish = start + n;
      }
      else {
        for (int i = size(); i < n; i++)
        {
          start[i] = val;
        }
        finish = start + n;
      }
    }
    //Modifiers
    void push_back(const T& val)
    {
      if (capacity() == size())
      {
        size_t n = (capacity() == 0) ? 4 : 2 * capacity();
        reserve(n);
      }
      *finish = val;
      ++finish;
    }
    void pop_back()
    {
      assert(start != finish);
      --finish;
    }
    iterator insert(iterator pos, const T& val)
    {
      // 空间不够先进行增容
      if (finish == end_of_storage)
      {
        size_t newCapacity = (capacity() == 0) ? 1 : capacity() * 2;
        reserve(newCapacity);
        // 如果发生了增容，需要重置pos
        pos = _start + size();
      }
      //挪动数据
      iterator p = finish;
      while (p != pos)
      {
        *p = *(p - 1);
        --p;
      }
      *pos = val;
      finish += 1;
      return pos;
    }
    template<class InputIterator>
    void insert(iterator pos, InputIterator first, InputIterator last)
    {
      //这里如果迭代器不是原生指针或者内存空间不连续就不能进行 - 操作了
      size_t sz = last - first;
      size_t n = pos - start;
      reserve(sz + size());
      pos = start + n;
      //挪数据
      iterator p = finish - 1;
      while (p >= pos)
      {
        *(p + sz) = *p;
        --p;
      }
      //插入数据
      for (size_t i = 0; i < sz; i++)
      {
        pos[i] = first[i];
      }
      finish += sz;
    }
    iterator erase(iterator pos)
    {
      size_t sz = finish - pos;
      for (int i = 0; i < sz; i++)
      {
        pos[i] = pos[i + 1];
      }
      finish -= 1;
      return 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 clear()
    {
      finish = start;
    }
    //Element access:
    T& operator[](size_t i)
    {
      return start[i];
    }
    const T& operator[](size_t i) const
    {
      return start[i];
    }
    
  private:
    iterator start;
    iterator finish;
    iterator end_of_storage;
  };
};

到这里，vector模拟实现就结束了，希望你能有所收获

感谢各位大佬支持并指出问题

如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！

【C++】—— vector模拟实现