AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【STL】：vector的模拟实现

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

1. 基本构造

在实现vector之前可以先看一下库里面的vector是如何实现的：

#pragma once
#include <assert.h>
namespace ywh
{
  template<class T>
  class vector
  {
    typedef T* iterator;
    typedef const T* const_iterator;
  public:
    /基本构造///
    //构造
    vector()
    {}
    //析构
    ~vector()
    {
      delete[] _start;
      _start = _finish = _end_of_storage = nullptr;
    }
  private:
    iterator _start = nullptr;   //起始
    iterator _finish = nullptr;  //有效数据个数
    iterator _end_of_storage = nullptr; //有效空间
  };
}

2. 容量相关的接口

2.1 operator[ ]

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

2.2 reserve

关于reserve的实现最主要的就是深拷贝与浅拷贝的问题，使用浅拷贝对于内置类型很容易处理，但是对于自定义类型就会出现麻烦：

需要进行深拷贝，关于自定义类型的赋值重载就是一个深拷贝，所以我们需要使用深拷贝来说实现reserve：

//reserve
    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);
          //采用深拷贝
          for (size_t i = 0; i < sz; i++)
          {
            tmp[i] = _start[i];
          }
          delete[] _start;
        } 
        _start = tmp;
        _finish = _start + sz;
        _end_of_storage = _start + n;
      }
    }

2.3 resize

//resize
    //这里使用匿名对象进行缺省值的传参，由于匿名函数具有常性所以要使用const
    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;
        }
      }
    }

2.4 size、capacity

有效元素的个数从开始位置到数据截止位置

容量是开始位置到空间终止位置

//容量
    size_t capacity() const
    {
      return _end_of_storage - _start;
    }
    //有效个数
    size_t size() const
    {
      return _finish - _start;
    }

3. 迭代器

关于模拟实现的vector只实现正向迭代器，反向迭代器的实现会在stack和queue的适配器模式中详解

/迭代器
    iterator begin()
    {
      return _start;
    }
    iterator end()
    {
      return _finish;
    }
    const_iterator begin() const
    {
      return _start;
    }
    const_iterator end() const
    {
      return _finish;
    }

4. 修改相关接口

4.1 insert、push_back

在insert的时候需要注意的是：假如需要扩容，那么pos还是在旧空间，所以在扩容之前需要将旧空间pos的偏移量记录出来，然后在扩容之后将新空间的pos记录出来。

//在pos位置插入
    void insert(iterator pos, const T& x)
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      if (_finish == _end_of_storage)
      {
        //记录旧空间中pos的偏移量
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        //找出新空间的pos
        pos = _start + len;
      }
      iterator end = _finish - 1;
      while (end >= pos)
      {
        *(end + 1) = *end;
        --end;
      }
      *pos = x;
      ++_finish;
    }
    //尾插
    void push_back(const T& x)
    {
      //复用插入
      insert(end(), x);
    }

insert之后的迭代器会失效，上述中的pos就是迭代器失效的一种案例，在不同的平台下对于迭代器的失效都有不同的检查方法，VS2019上如果使用insert之后的迭代器是不允许进行使用的。

4.2 erase

//删除pos位置
    void erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos < _finish);
      iterator it = pos + 1;
      while (it < _finish)
      {
        *(it - 1) = *it;
        ++it;
      }
      --_finish;
    }

如果我们单纯的看这个代码会感觉erase之后迭代器是不会失效的，但是erase之后迭代器失效会在特殊情况下展示出来，比如要删除偶数：

void Test()
{
  ywh::vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  v.push_back(6);
  ywh::vector<int>::iterator it = v.begin();
  while (it != v.end())
  {
        //删除偶数
    if (*it % 2 == 0)
    {
      v.erase(it);
    }
    it++;
  }
  for (auto e : v)
  {
    cout << e << " ";
  }
  cout << endl;
}

在这里有三种情况：

我们可以看看库里面是如何设计的：

对于返回值的介绍：

返回被删除数据的下一个位置

所以我们需要对我们实现的erase进行调整：

//删除pos位置
    iterator erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos < _finish);
      iterator it = pos + 1;
      while (it < _finish)
      {
        *(it - 1) = *it;
        ++it;
      }
      --_finish;
      //返回删除位置的后一个位置
      return pos;
    }
void Test()
{
  ywh::vector<int> v;
  v.push_back(2);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  v.push_back(6);
  ywh::vector<int>::iterator it = v.begin();
  while (it != v.end())
  {
    if (*it % 2 == 0)
    {
      //删除后自动找到删除位置的下一个位置
      v.erase(it);
    }
    else
    {
      //不符合情况再往后面走
      it++;
    }
  }
  for (auto e : v)
  {
    cout << e << " ";
  }
  cout << endl;
}

5. 拷贝构造和赋值重载和其他构造

5.1 拷贝构造

//拷贝构造
    vector(const vector<T>& v)
    {
            //开辟空间
      reserve(v.capacity());
            //依次尾插
      for (auto e : v)
      {
        push_back(e);
      }
    }

5.2 赋值重载

void swap(vector<T>& v)
{
  std::swap(_start, v._start);
  std::swap(_finish, v._finish);
  std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator=(vector<T> tmp) 
{
  //直接交换
  swap(tmp);
  return *this;
}

5.3 其他构造

//迭代器区间初始化
    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    //n个val构造
    vector(size_t n, const T& val = T())
    {
      reserve(n);
      for (size_t i = 0; i < n; i++)
      {
        //n个val进行尾插
        push_back(val);
      }
    }
    vector(int n, const T& val = T())
    {
      reserve(n);
      for (int i = 0; i < n; i++)
      {
        //n个val进行尾插
        push_back(val);
      }
    }

6. 完整代码

头文件：Vector.h

#pragma once
#include <assert.h>
namespace ywh
{
  template<class T>
  class vector
  {
  public:
    typedef T* iterator;
    typedef const T* const_iterator;
  public:
    /迭代器
    iterator begin()
    {
      return _start;
    }
    iterator end()
    {
      return _finish;
    }
    const_iterator begin() const
    {
      return _start;
    }
    const_iterator end() const
    {
      return _finish;
    }
    /基本构造///
    //构造
    vector()
    {}
    //迭代器区间初始化
    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    //n个val构造
    vector(size_t n, const T& val = T())
    {
      reserve(n);
      for (size_t i = 0; i < n; i++)
      {
        //n个val进行尾插
        push_back(val);
      }
    }
    vector(int n, const T& val = T())
    {
      reserve(n);
      for (int i = 0; i < n; i++)
      {
        //n个val进行尾插
        push_back(val);
      }
    }
    //拷贝构造
    vector(const vector<T>& v)
    {
      //开辟空间
      reserve(v.capacity());
      //依次尾插
      for (auto e : v)
      {
        push_back(e);
      }
    }
    void swap(vector<T>& v)
    {
      std::swap(_start, v._start);
      std::swap(_finish, v._finish);
      std::swap(_end_of_storage, v._end_of_storage);
    }
        //operator=
    vector<T>& operator=(vector<T> tmp) 
    {
      //直接交换
      swap(tmp);
      return *this;
    }
    //析构
    ~vector()
    {
      delete[] _start;
      _start = _finish = _end_of_storage = nullptr;
    }
    ///容量
    //operator[]
    T& operator[](size_t pos)
    {
      assert(pos < size());
      return _start[pos];
    }
    const T& operator[](size_t pos) const
    {
      assert(pos < size());
      return _start[pos];
    }
    //容量
    size_t capacity() const
    {
      return _end_of_storage - _start;
    }
    //有效个数
    size_t size() const
    {
      return _finish - _start;
    }
    //reserve
    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);
          //采用深拷贝
          for (size_t i = 0; i < sz; i++)
          {
            tmp[i] = _start[i];
          }
          delete[] _start;
        } 
        _start = tmp;
        _finish = _start + sz;
        _end_of_storage = _start + n;
      }
    }
    //resize
    //这里使用匿名对象进行缺省值的传参，由于匿名函数具有常性所以要使用const
    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;
        }
      }
    }
    ///修改
    //在pos位置插入
    void insert(iterator pos, const T& x)
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      if (_finish == _end_of_storage)
      {
        //记录旧空间中pos的偏移量
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        //找出新空间的pos
        pos = _start + len;
      }
      iterator end = _finish - 1;
      while (end >= pos)
      {
        *(end + 1) = *end;
        --end;
      }
      *pos = x;
      ++_finish;
    }
    //尾插
    void push_back(const T& x)
    {
      //复用插入
      insert(end(), x);
    }
    //删除pos位置
    iterator erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos < _finish);
      iterator it = pos + 1;
      while (it < _finish)
      {
        *(it - 1) = *it;
        ++it;
      }
      --_finish;
      //返回删除位置的后一个位置
      return pos;
    }
  private:
    iterator _start = nullptr;   //起始位置
    iterator _finish = nullptr;  //有效数据位置
    iterator _end_of_storage = nullptr; //结束位置
  };
}

朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，欲知后事如何，请听下回分解~，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！

文章标签：
C++
stackY
目录
相关文章
戊子仲秋
|
12月前
|
程序员 编译器 C++
【STL】 模拟实现简易 vector
【STL】 模拟实现简易 vector
戊子仲秋
27 0
小小unicorn
|
5月前
|
存储 编译器 C++
【C++初阶】STL详解（四）vector的模拟实现
【C++初阶】STL详解（四）vector的模拟实现
小小unicorn
68 1
秦jh
|
5月前
|
算法 C++ 容器
【C++/STL】vector（常见接口、模拟实现、迭代器失效）
【C++/STL】vector（常见接口、模拟实现、迭代器失效）
秦jh
49 0
烽起黎明
|
10月前
|
Linux 编译器 测试技术
【C++】STL之vector类模拟-3
【C++】STL之vector类模拟
烽起黎明
32 0
烽起黎明
|
10月前
|
C++ 容器
【C++】STL之vector类模拟-2
【C++】STL之vector类模拟
烽起黎明
34 0
烽起黎明
|
10月前
|
安全 C++ 容器
【C++】STL之vector类模拟-1
【C++】STL之vector类模拟
烽起黎明
32 0
求知.
|
10月前
|
存储 算法 C++
STL中vector的用法以及模拟实现
STL中vector的用法以及模拟实现
求知.
47 0
Hayaizo
|
C++
【C++ STL】vector模拟实现
【C++ STL】vector模拟实现
Hayaizo
47 0
【C++ STL】vector模拟实现
诚酱
|
存储 C++ 容器
C++【STL】之vector模拟实现
C++ STL vector类模拟实现，常用接口详细讲解，干货满满！
诚酱
63 0
C++【STL】之vector模拟实现
有礼貌的灰绅士
|
C++
C++STL——vector类与模拟实现（下）
C++STL——vector类与模拟实现
有礼貌的灰绅士
92 0