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模拟实现

vector的简单介绍

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

2、reserve()的实现

3、resize()的实现

4、insert()的实现

5、earse()的实现

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

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

vector模拟实现

vector的简单介绍

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

2、reserve()的实现

3、resize()的实现

4、insert()的实现

5、earse()的实现

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

热门文章

最新文章

相关电子书