C++——vector模拟实现(上）

2022-12-09 96

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 笔记

vecotr模拟实现

源代码里面，核心成员是下面红框三个

观察这里的代码发现这里的迭代器都是原生指针

#include<iostream>
#include<assert.h>
using namespace std;
namespace my_space
{
  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;
    }
    vector()
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {}
    ~vector()
    {
      delete[] _start;
      _start = _finish = _end_of_storage = nullptr;
    }
    size_t capacity() const
    {
      return _end_of_storage - _start;
    }
    const T& operator[](size_t pos) const
    {
      assert(pos < size());
      return _start[pos];
    }
    T& operator[](size_t pos)
    {
      assert(pos < size());
      return _start[pos];
    }
    size_t size() const
    {
      return _finish - _start;
    }
    void reserve(size_t n)
    {
      if (n > capacity())
      {
        size_t sz = size();
        T* tmp = new T[n];
        if (_start)
        {
          memcpy(tmp, _start, sizeof(T) * sz);
          delete[] _start;
        }
        _start = tmp;
        _finish = _start + sz;
        _end_of_storage = _start + n;
      }
    }
    void push_back(const T& x)//加const防止隐式类型转换的中间常量传参错误，引用可避免深拷贝
    {
        if (_finish == _end_of_storage)
        {
          reserve(capacity() == 0 ? 4 : capacity() * 2);
        }
        *_finish = x;
        ++_finish;
    }
    void pop_back()
    {
      assert(_finish > _start);
      --_finish;
    }
  private:
    iterator _start;
    iterator _finish;
    iterator _end_of_storage;
  };
}；

insert

  void insert(iterator pos, const T& x)
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      if (_finish == _end_of_storage)
      {
        reserve(capacity() == 0 ? 4 : capacity() * 2);
      }
      // 挪动数据
      iterator end = _finish - 1;
      while (end >= pos)
      {
        *(end + 1) = *end;
        --end;
      }
      *pos = x;
      ++_finish;
    }

这种写法有一个缺陷

在3的前面插入30，此时程序正常运行

屏蔽掉一条语句后，会出错

这是因为扩容时出现了问题，pos本来是指向start中的，扩容之后start被销毁，新空间是tmp,pos就成了野指针

pos失效了

    void insert(iterator pos, const T& x)
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      if (_finish == _end_of_storage)
      {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
      }
      // 挪动数据
      iterator end = _finish - 1;
      while (end >= pos)
      {
        *(end + 1) = *end;
        --end;
      }
      *pos = x;
      ++_finish;
    }

这样就不会出错了，用相对位置记住pos之前所在位置

如果连续插入有时会报错，有时则不会

这是因为pos的修改不会影响p，pos是形参，p有可能会失效，有可能不会失效取决于有没有扩容，所以在p位置插入数据后，不要再去访问p，因为有可能会失效

但是如果用引用，就跟库里面的insert不一致了，我们尽量要跟库里面保持一致

还有一种情况，当空间足够时，我们插入数据也会崩，也会导致迭代器失效

it指向2时满足条件，在2的前面插入4

然后++it，it仍然指向2，这样每次++it会导致it一直指向2，所以程序会崩

修改方法就是用一个变量来接收insert的返回值，库里面的insert，会返回新插入数据的下标，我们接收这个下标跟库里面的insert保持一致

这样就可以

如果时偶数，对it++俩次即可

  iterator insert(iterator& pos, const T& x)
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      if (_finish == _end_of_storage)
      {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
      }
      // 挪动数据
      iterator end = _finish - 1;
      while (end >= pos)
      {
        *(end + 1) = *end;
        --end;
      }
      *pos = x;
      ++_finish;
      return pos;
    }
void test_vector1()
  {
    vector<int> v;
    v.reserve(10);
    v.push_back(1);
    v.push_back(2);
    v.push_back(4);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    auto it = v.begin();
    while (it != v.end())
    {
      if (*it % 2 == 0)
      {
        it = v.insert(it, *it * 2);
        ++it;
      }
      ++it;
    }
    for (size_t i = 0; i < v.size(); ++i)
    {
      cout << v[i] << " ";
    }
    cout << endl;
  }

去掉reserve扩容之后，插入很多数据，程序仍然可以正常运行

erase

    void erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      iterator begin = pos + 1;
      while (begin < _finish)
      {
        *(begin - 1) = *begin;
        ++begin;
      }
      --_finish;
    }