vector模拟实现-阿里云开发者社区

vector的简单介绍

在C++中，vector 是标准模板库（Standard Template Library，简称 STL）中的一种序列容器（sequence container）。它提供了一个动态大小的数组的功能，允许在数组的末尾快速地添加和删除元素。我们来做一下vector的模拟实现

1、vector的构造函数和析构函数

在C++标准库中，vector有四个构造函数，为了提高我们的英语阅读水平，我们可以看一下英语文档，因为有些翻译软件翻译的不太好；

(1)是一个默认构造。构造一个空的容器；

(2)是构造一个容器，含有n个元素，每个元素都是val的拷贝；

(3)是构造一个容器，可以在[first,last)中变化，每个元素在这个范围里面按照顺序构造(文字解释可能不太好，可以看例子)；

(4)是一个拷贝构造，构造一个容器，从x中拷贝元素，按照相同的顺序，放入容器内；

普通的带参构造函数

  //v2(v1)
  vector(const vector<T>& v)
  {
    reserve(v.capacity());
    for(auto& i :v)
    {
      push_back(i);
    }
  }

带有迭代器的构造函数，加了个类模板，表示支持不同类型的迭代器构造，比如，vector迭代器,string迭代器,

//v2(v1.begin(),v1.end())
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
  while (first != last)
  {
    push_back(*first);
    ++first;
  }
}

为了防止访问冲突，int类型特意单独重载了一个构造函数，否则int类型会在迭代器构造和size_t类型构造之间不知道怎么选择；

//为了防止vector(int n, const T& val = T())与vector(InputIterator first, InputIterator last)
//发生访问冲突，要另外重载一个int n的构造函数，否则vector<int> v1(10,100)编译器会默认选择
//带有迭代器的那个构造，造成冲突了
 
//vector<int> v1(10,100)
vector(size_t n, const T& val = T())
{
  reserve(n);
  for (size_t i = 0; i < n; i++)
  {
    push_back(val);
  }
}
vector(int n, const T& val = T())
{
  reserve(n);
  for (int i = 0; i < n; i++)
  {
    push_back(val);
  }
}

C++11新提供的特性,用initializer_list进行构造，一种新的写法；

也可以这样：

vector<int> v1{ 1,2,3,4,5,6,7,8,9,10 };

或者这样：

vector<int> v2({ 10,20,30,40 });

其实都是一样的

//vectro<int> v1 = { 1,2,3,4,5 };
//C++11新提供的特性
vector(std::initializer_list<T> il)
{
  reserve(il.size());
  for (auto& i : il)
  {
    push_back(i);
  }
}

2、reserve()的实现

void  reserve(size_t n)
{
  if (n > capacity())
  {
    T* tem = new T[n];
    size_t old_size = size();
    //对于一些string，vector类型的，会出现浅拷贝的问题，所以不用memcpy
    //memcpy(tem, _start, size() * sizeof(T));
    for (size_t i = 0; i < old_size; i++)
    {
      tem[i] = _start[i];
    }
    delete[] _start;
    _start = tem;
    _finish = tem + old_size;
    _endofstorage = tem + n;
   }
}

reserve在这里只会扩容空间，不能缩小空间，一般情况下我们扩容空间都会用memecpy拷贝数据，但是这只可以应对vector<int> vector<double>等类型的，遇到vector<string> 就会出现浅拷贝的问题，而用这种赋值的方法就能巧妙地解决问题，用了一个赋值运算符，把_start指向的空间拷贝了一份给tem,然后delete[] _start，这样既释放了旧空间，又开辟了新空间；

还有一点，就是我们扩容空间的，迭代器会失效的问题，size()的底层是迭代器，所以我们要提前保存一下size()，迭代器失效的问题后面也会提到，然后在计算扩容后的_finish就用tem+old_size就可以了。

3、resize()的实现

void resize(size_t n, const T& val = T())//内置类型也具有默认构造函数
{
  if (n > size())
  {
    reserve(n);
    while (_finish < _start + n)
    {
      *_finish = val;
      ++_finish;
    }
  }
  else
  {
    _finish = _start + n;
  }
}

关于resize的缺省值，C++提到了一个巧妙的办法，

const T& val = T()

这是一个匿名对象，C++为了实现这个用法，对原有的基本类型也进行了一些升级，

内置类型也有了构造函数，

int类型的默认构造函数是0,

double类型的默认构造函数是0.0,

char类型的默认构造函数是'\0'

所以这个地方用T()做缺省参数最合适了，

当n>size()时，我们先reserve一下，然后大于size()的地方，用T()填充，

如果n<=size(),直接

_finish = _start + n;

4、insert()的实现

void insert(iterator pos,const T& val)
{
  assert(pos >= _start && pos <= _finish);
 
  if (_finish == _endofstorage)
  {
    size_t len = pos - _start;
    reserve(capacity() == 0 ? 4 : capacity() * 2);
    pos = _start + len;
  }
  iterator it = _finish - 1;
  while (it >= pos)
  {
    *(it + 1) = *it;
    --it;
  }
  *pos = val;
  ++_finish;
}

当我们插入的时候，如果空间满了，要reserve，但是扩容后要更新迭代器；比如我们先记录下来pos的相对位置，len=pos-_start，然后扩容后，再更新pos，然后就向后移动数据，插入元素；

5、earse()的实现

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

earse是有返回值的，返回的是删除元素的下一个位置的迭代器，

6、对于整个大框架来说，我们要注意深浅拷贝问题，迭代器失效问题，构造函数匹配问题，隐式类型转换问题

以下是完整的代码实现：

#pragma once
#include<assert.h>
#include<iostream>
#include<vector>
using namespace std;
 
namespace ljp
{
  //类模板
  template<class T>
  class vector
  {
  public:
    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;
    }
    size_t size() const
    {
      return _finish - _start;
    }
    size_t capacity() const
    {
      return _endofstorage - _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];
    }
 
    vector()
    {}
    //v2(v1)
    vector(const vector<T>& v)
    {
      reserve(v.capacity());
      for(auto& i :v)
      {
        push_back(i);
      }
    }
    //v2(v1.begin(),v1.end())
    template <class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    
    //为了防止vector(int n, const T& val = T())与vector(InputIterator first, InputIterator last)
    //发生访问冲突，要另外重载一个int n的构造函数，否则vector<int> v1(10,100)编译器会默认选择
    //带有迭代器的那个构造，造成冲突了
 
    //vector<int> v1(10,100)
    vector(size_t n, const T& val = T())
    {
      reserve(n);
      for (size_t i = 0; i < n; i++)
      {
        push_back(val);
      }
    }
    vector(int n, const T& val = T())
    {
      reserve(n);
      for (int i = 0; i < n; i++)
      {
        push_back(val);
      }
    }
    
    //vectro<int> v1 = { 1,2,3,4,5 };
    //C++11新提供的特性
    vector(std::initializer_list<T> il)
    {
      reserve(il.size());
      for (auto& i : il)
      {
        push_back(i);
      }
    }
 
    ~vector()
    {
      delete[] _start;
      _start = _finish = _endofstorage = nullptr;
    }
    vector& operator=(vector<T> v)
    {
      swap(v);
      return *this;
    }
    void swap(vector<T>& v)
    {
      std::swap(_start, v._start);
      std::swap(_finish, v._finish);
      std::swap(_endofstorage,v._endofstorage);
    }
    void push_back(const T& val)
    {
      insert(end(), val);
    }
    void pop_back()
    {
      erase(end() - 1);
    }
 
    void  reserve(size_t n)
    {
      if (n > capacity())
      {
        T* tem = new T[n];
        size_t old_size = size();
        //对于一些string，vector类型的，会出现浅拷贝的问题，所以不用memcpy
        //memcpy(tem, _start, size() * sizeof(T));
        for (size_t i = 0; i < old_size; i++)
        {
          tem[i] = _start[i];
        }
        delete[] _start;
        _start = tem;
        _finish = tem + old_size;
        _endofstorage = tem + n;
       }
    }
 
    void resize(size_t n, const T& val = T())//内置类型也具有默认构造函数
    {
      if (n > size())
      {
        reserve(n);
        while (_finish < _start + n)
        {
          *_finish = val;
          ++_finish;
        }
      }
      else
      {
        _finish = _start + n;
      }
    }
 
    bool empty()
    {
      return _start == _finish;
    }
 
    void insert(iterator pos,const T& val)
    {
      assert(pos >= _start && pos <= _finish);
 
      if (_finish == _endofstorage)
      {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
      }
      iterator it = _finish - 1;
      while (it >= pos)
      {
        *(it + 1) = *it;
        --it;
      }
      *pos = val;
      ++_finish;
    }
    iterator erase(iterator pos)
    {
      assert(pos >= _start && pos < _finish);
      iterator it = pos+1;
      while (it <_finish)
      {
        *(it - 1) = *it;
        it++;
      }
      --_finish;
      return pos;
    }
  private:
    iterator _start = nullptr;
    iterator _finish = nullptr;
    iterator _endofstorage = nullptr;
  };
  //函数模板
  template<class T>
  void print_vector(const vector<T>& v)
  {
    for (int i = 0; i < v.size(); i++)
    {
      cout << v[i] << " ";
    }
    cout << '\n';
 
    //typename vector<T>::const_iterator it = v.begin();
    auto it = v.begin();
    //while (it != v.end())
    //{
    //  cout << *it << " ";
    //  ++it;
    //}
    //cout << '\n';
 
    //for (auto i : v)
    //{
    //  cout << i << " ";
    //}
    //cout << '\n';
  }
 
  void test_vector1()
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(4);
    v1.push_back(4);
    print_vector(v1);
 
    vector<double> v2;
    v2.push_back(1.1);
    v2.push_back(2.2);
    v2.push_back(3.1);
    print_vector(v2);
 
    v2.insert(v2.begin(), 11.11);
    print_vector(v2);
 
    v2.insert(v2.begin(), 11.11);
    print_vector(v2);
 
    v2.insert(v2.begin(), 11.11);
    print_vector(v2);
 
    v2.insert(v2.begin(), 11.11);
    print_vector(v2);
 
    v2.insert(v2.begin(), 11.11);
    print_vector(v2);
 
    v2.erase(v2.begin());
    print_vector(v2);
 
    v2.erase(v2.begin() + 4);
    print_vector(v2);
  }
 
  void test_vector2()
  {
    int i = 1;
    int j = int();
    int k = int(2);
 
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    v1.push_back(6);
    print_vector(v1);
 
    v1.resize(10);
    print_vector(v1);
 
    v1.resize(3);
    print_vector(v1);
  }
  void test_vector3()
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(4);
    v1.push_back(4);
    print_vector(v1);
 
    v1.pop_back();
    print_vector(v1);
 
    vector<int> v2(v1);
    print_vector(v2);
 
    vector<int> v3;
    v3.push_back(10);
    v3.push_back(20);
    v3.push_back(30);
 
    v1 = v3;
    print_vector(v1);
    print_vector(v3);
  }
  void test_vector4()
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    print_vector(v1);
 
    vector<int> v2(v1.begin() + 1, v1.end() - 1);
    print_vector(v2);
 
    string str("abcd");
    vector<int> v3(str.begin(), str.end());
    print_vector(v3);
  }
  void test_vector5()
  {
    vector<int> v1(10, 1);
    print_vector(v1);
 
    //0ull;
    //vector<int> v2(10ull, 1);
    vector<int> v2(10u, 1);
    print_vector(v2);
 
    vector<char> v3(10, 'a');
    print_vector(v3);
  }
  void test_vector6()
  {
    //C++11新增的特性，
    std::vector<int> v10 = { 1,2,2,3,4,5 };
 
    auto x = { 1,2,3,4,5,6,7,8,9,10 };
    cout << typeid(x).name() << endl;
    cout << sizeof(x) << endl;
 
    //
    initializer_list<int> y = { 1,2,3,4,5,6,7 };
 
 
    // 单参数的构造函数，隐式类型转换
    string str = "11111"; // 构造 + 拷贝构造 -> 优化 直接构造
    const string& str1 = "11111"; // 构造临时对象，引用的是临时对象
    vector<string> v;
    v.push_back(str);
 
    v.push_back(string("22222"));
    v.push_back("33333");
 
 
    // 不推荐 -- C++11
    //int j = { 1 };
    int k{ 1 };
 
    // 跟上面类似
    // 隐式类型转换+优化
    //vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10 };
    vector<int> v1{ 1,2,3,4,5,6,7,8,9,10 };
    for (auto e : v1)
    {
      cout << e << " ";
    }
    cout << endl;
 
    // 直接构造
    vector<int> v2({ 10,20,30,40 });
    for (auto e : v2)
    {
      cout << e << " ";
    }
    cout << endl;
  }
  void test_vector7()
  {
    vector<string> v;
    v.push_back("11111");
    v.push_back("22222");
    v.push_back("33333");
    v.push_back("44444");
    v.push_back("55555");
 
    for (auto& e : v)
    {
      cout << e << " ";
    }
    cout << endl;
  }
  void test_vector8()
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    v1.push_back(6);
    v1.push_back(7);
    v1.push_back(8);
    print_vector(v1);
 
    // insert以后，it就失效了，不要使用了
    vector<int>::iterator it = v1.begin() + 3;
    v1.insert(it, 40);
 
    cout << *it << endl;
 
    print_vector(v1);
 
    it = v1.begin() + 3;
 
    cout << *it << endl;
  }
 
  void test_vector9()
  {
    //std::vector<int> v1;
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(4);
    v1.push_back(5);
    //v1.push_back(4);
 
    // 删除偶数 -- 迭代器失效以后，不要直接使用，如果要使用按规则重新更新后使用
    //std::vector<int>::iterator it = v1.begin();
    vector<int>::iterator it = v1.begin();
 
    //cout << typeid(it).name() << endl;
    while (it != v1.end())
    {
      if (*it % 2 == 0)
      {
        it = v1.erase(it);
      }
      else
      {
        ++it;
      }
    }
 
    //print_vector(v1);
    for (auto e : v1)
    {
      cout << e << " ";
    }
    cout << endl;
  }
 
}

vector模拟实现