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

【C++】vector的模拟实现（下）

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

删除所有的偶数


void vectorTest5()
{
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(6);
  auto it = v.begin();
  while (it != v.end())
  {
    if (*it % 2 == 0)
    {
      it = v.erase(it);
    }
    else
    {
      it++;
    }
  }
  for (auto e : v)
  {
    cout << e << " ";
  }
  cout << endl;
}


注：删除 it 位置后，我们需要接收一下 erase 函数的返回值，erase 函数的返回值为删除元素的下一个元素的位置。如果不接受 erase 函数的返回值，就会有可能出现各种情况。见下图：


323a478aca7f4fc9b372b45dc3bb1588.png23a35ce6ba20473daf906080faace250.png


注：我们要统一认为调用 erase(it) 函数后，迭代器 it 会失效。


front 和 back


T& front()
{
  assert(!empty());
  return *_start;
}
const T& front() const
{
  assert(!empty());
  return *_start;
}
T& back()
{
  assert(!empty());
  return *(_finish - 1);
}
const T& back() const
{
  assert(!empty());
  return *(_finish - 1);
}


swap 和 clear


void swap(vector<T>& v)
{
  std::swap(_start, v._start);
  std::swap(_finish, v._finish);
  std::swap(_endofstorage, v._endofstorage);
}
void clear
{
  _finish = _start;
}


注：swap 函数交换两个类对象成员变量的值就行了，clear 函数不能将 _start 置为 nullptr，否则将会造成内存泄漏问题。


析构函数


~vector()
{
  delete[] _start;
  _start = _finish = _endofstorage = nullptr;
}


拷贝构造函数


传统写法1


vector(const vector<T>& v)
{
  size_t Size = v.size();
  _start = new T[Size];
  for (size_t i = 0; i < Size; ++i)
  {
    _start[i] = v._start[i];
  }
  _finish = _endofstorage = _start + Size;
}


注：该写法不能用 memcpy 函数来拷贝数据，因为这样会导致浅拷贝问题（将会在下面的内容讲解）。


传统写法2


vector(const vector<T>& v)
  : _start(nullptr)
  , _finish(nullptr)
  , _endofstorage(nullptr)
{
  reserve(v.capacity());
  //reserve(v.size());
  for (auto& e : v)
  {
    push_back(e);
  }
}


注：该写法使用范围 for 来尾插数据，一定要加引用。因为 e 有可能是自定义类型，不用引用的话，会存在拷贝构造。


现代写法


// 用迭代器来构造对象
template <class InputIterator>
vector(InputIterator first, InputIterator last)
  : _start(nullptr)
  , _finish(nullptr)
  , _endofstorage(nullptr)
{
  while (first != last)
  {
    push_back(*first);
    ++first;
  }
}
vector(const vector<T>& v)
  : _start(nullptr)
  , _finish(nullptr)
  , _endofstorage(nullptr)
{
  vector<T> tmp(v.begin(), v.end());
  swap(tmp);
}

c6120b1f76c94fe0a695da7250b3952b.png



赋值运算符重载


// v1 = v2
// v1 = v1 极少数情况，且能保证正确性，所以这样写没有什么问题
vector<T>& operator=(vector<T> v)
{
  swap(v);
  return *this;
}


4b5625859783430186420f791ca575ee.png


用 n 个 val 来构造


vector(size_t n, const T& val = T())
  : _start(nullptr)
  , _finish(nullptr)
  , _endofstorage(nullptr)
{
  reserve(n);
  for (size_t i = 0; i < n; ++i)
  {
    push_back(val);
  }
}


c54aaa56373849d09256b6f0f8e7d9f6.png

其实只写这个函数接口的话，会带来一个问题。我们来看一下。


42e7d92d48fe491287cd3845a2ed3feb.png


我本来想要 10 个 1来构造出来一个 vector 对象，编译器怎么给我报了个非法间接寻址的错误呢？原因是在这，因为用迭代器去构造对象的函数比上面写的用 n 个 val 构造对象的函数更匹配（int 需要类型转换成 size_t，而迭代器模板构造函数不用类型转换），编译器会调用更加匹配的函数，所以就导致了非法间接寻址。


1acbaf7e518949cbae0d578243ded25a.png



那如果我们就是想用 n 个 val 来构造对象的函数，应该解决呢？我们可以再多写个下面的函数来形成函数重载。


vector(int n, const T& val = T())
  : _start(nullptr)
  , _finish(nullptr)
  , _endofstorage(nullptr)
{
  reserve(n);
  for (int i = 0; i < n; ++i)
  {
    push_back(val);
  }
}


54561b5d69d842a5ac1ce181be773a4b.png


👉memcpy 带来的浅拷贝问题👈


现在我们模拟实现的 vector 已经差不多完成了，那我们拿上一篇博客写的杨辉三角来验证一下我们写的 vector 对不对。


21b2802df5454e66ade554178e6e5996.png


我们一运行起来，程序就崩溃了。为什么这样子呢？其实就是 memcpy 带来的浅拷贝问题。


为了分析方便，我们换一个例子来说明这个问题，然后再回过头来分析杨辉三角的问题。

520b06f096e14c3bbf368e237c0d29c1.png


可以看到，向 vv 尾插4个 v，没有任何的问题。那插入5个 v呢？


4de8716d4a1949cba4694532841ce408.png


插入5个 v，就出现问题了。为什么呢？因为插入5个 v 就要扩容，而扩容就要将原来的数据拷贝到新空间里。reserve 函数里的拷贝数据是采用 memcpy 函数来拷贝数据，而 memcpy 函数是按照字节来拷贝的，是浅拷贝，而我们所想要的是深拷贝。原来问题就是出现在这里。那我们再调试起来看看。



39cc0c7fdea54491afed0b3d8eead5ca.png


5d08ad440bba47ffae25a722ae96fafc.png5fda1370034e4946baebd44d3bbe55e9.png


那我们怎么解决这个问题呢？其实很简单，只需要修改一下 reserve 函数里的拷贝数据的形式就可以了。

59e5eed7ebf34da18ba5f223501ce3b8.png


void reserve(size_t n)
{
  if (n > capacity())
  {
    size_t oldSize = size();
    T* tmp = new T[n];
    // _start为nullptr时，不需要拷贝数据
    if (_start)
    {
      //memcpy(tmp, _start, sizeof(T) * oldSize);
      for (size_t i = 0; i < oldSize; ++i)
      {
        // 自定义类型需要深拷贝，调用其赋值运算符重载
        tmp[i] = _start[i];
      }
      delete[] _start;
    }
    _start = tmp;
    _finish = tmp + oldSize;
    _endofstorage = tmp + n;
  }
}

c3b43eb8433a4ceda470fa9187310a1e.png


修改过后，我们的程序就可以跑起来了。那我们再来跑一下杨辉三角的程序，看能不能跑起来。


d211a6a682ca44289365c66d386048f3.png


可以看到，杨辉三角的程序也是可以跑起来的，因为其问题也是扩容时的浅拷贝导致的。


完整代码


#pragma once
namespace Joy
{
  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;
    }
    vector()
      : _start(nullptr)
      , _finish(nullptr)
      , _endofstorage(nullptr)
    {}
    vector(int n, const T& val = T())
      : _start(nullptr)
      , _finish(nullptr)
      , _endofstorage(nullptr)
    {
      reserve(n);
      for (int i = 0; i < n; ++i)
      {
        push_back(val);
      }
    }
    vector(size_t n, const T& val = T())
      : _start(nullptr)
      , _finish(nullptr)
      , _endofstorage(nullptr)
    {
      reserve(n);
      for (size_t i = 0; i < n; ++i)
      {
        push_back(val);
      }
    }
    template <class InputIterator>
    vector(InputIterator first, InputIterator last)
      : _start(nullptr)
      , _finish(nullptr)
      , _endofstorage(nullptr)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    void swap(vector<T>& v)
    {
      std::swap(_start, v._start);
      std::swap(_finish, v._finish);
      std::swap(_endofstorage, v._endofstorage);
    }
    vector(const vector<T>& v)
      : _start(nullptr)
      , _finish(nullptr)
      , _endofstorage(nullptr)
    {
      vector<T> tmp(v.begin(), v.end());
      swap(tmp);
    }
    vector<T>& operator=(vector<T> v)
    {
      swap(v);
      return *this;
    }
    ~vector()
    {
      delete[] _start;
      _start = _finish = _endofstorage = nullptr;
    }
    T& operator[](size_t pos)
    {
      assert(pos < size());
      return _start[pos];
    }
    const T& operator[](size_t pos) const 
    {
      assert(pos < size());
      return _start[pos];
    }
    void reserve(size_t n)
    {
      if (n > capacity())
      {
        int oldSize = size();
        T* tmp = new T[n];
        if (_start)
        {
          for (size_t i = 0; i < oldSize; ++i)
          {
            tmp[i] = _start[i];
          }
          delete[] _start;
        }
        _start = tmp;
        _finish = tmp + oldSize;
        _endofstorage = tmp + n;
      }
    }
    void resize(size_t n, const T& val = T())
    {
      if (n > capacity())
      {
        reserve(n);
      }
      if (n > size())
      {
        while (_finish < _start + n)
        {
          *_finish = val;
          ++_finish;
        }
      }
      else
      {
        _finish = _start + n;
      }
    }
    void push_back(const T& val = T())
    {
      if (_finish == _endofstorage)
      {
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
      }
      *_finish = val;
      ++_finish;
    }
    void pop_back()
    {
      assert(!empty());
      --_finish;
    }
    bool empty() const
    {
      return _start == _finish;
    }
    iterator insert(iterator pos, const T& val)
    {
      assert(pos >= _start);
      assert(pos < _finish);
      if (_finish == _endofstorage)
      {
        size_t len = pos - _start;
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
        pos = _start + len;
      }
      // Ų
      iterator end = _finish - 1;
      while (end >= pos)
      {
        *(end + 1) = *end;
        --end;
      }
      *pos = val;
      ++_finish;
      return pos;
    }
    iterator erase(iterator pos)
    {
      assert(!empty());
      assert(pos >= _start);
      assert(pos < _finish);
      iterator begin = pos + 1;
      while (begin < _finish)
      {
        *(begin - 1) = *begin;
        ++begin;
      }
      --_finish;
      return pos;
    }
    void clear()
    {
      _finish = _start;
    }
  private:
    T* _start;
    T* _finish;
    T* _endofstorage;
  };
}


👉总结👈


本篇博客讲解了 vector 的模拟实现，带大家理解 vector 的底层实现。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️




文章标签：
C++
编译器
关键词：
C++ vector
游客mpbbpgnnu5sxe
目录
相关文章
睡觉待开机
|
7月前
|
存储 编译器 C++
【C++】vector介绍+模拟实现
【C++】vector介绍+模拟实现
睡觉待开机
63 1
羑悻的小杀马特
|
16天前
|
算法 编译器 C++
模拟实现c++中的vector模版
模拟实现c++中的vector模版
羑悻的小杀马特
50 28
ephemerals__
|
4月前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器，包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组，能够根据需要自动调整大小，提供了丰富的操作接口，如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后，还展示了如何使用`vector`创建字符串数组，体现了`vector`在实际编程中的灵活性和实用性。
ephemerals__
175 4
oioihoii
|
3月前
|
存储 对象存储 C++
C++ 中 std::array＜int, array_size＞ 与 std::vector＜int＞ 的深入对比
本文深入对比了 C++ 标准库中的 `std::array` 和 `std::vector`，从内存管理、性能、功能特性、使用场景等方面详细分析了两者的差异。`std::array` 适合固定大小的数据和高性能需求，而 `std::vector` 则提供了动态调整大小的灵活性，适用于数据量不确定或需要频繁操作的场景。选择合适的容器可以提高代码的效率和可靠性。
oioihoii
106 0
ephemerals__
|
3月前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理，并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表，使用三个迭代器（指针）来维护数组，分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码，帮助读者更好地理解和掌握 `vector` 的实现细节。
ephemerals__
76 0
白子寰
|
5月前
|
存储 C++ 索引
【C++打怪之路Lv9】-- vector
【C++打怪之路Lv9】-- vector
白子寰
46 1
半截诗
|
5月前
|
安全 测试技术 C++
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化2
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化
半截诗
99 6
半截诗
|
5月前
|
安全 测试技术 C++
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化1
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化
半截诗
128 7
努力学习的小廉
|
5月前
|
编译器 C++
【C++】—— vector模拟实现
【C++】—— vector模拟实现
努力学习的小廉
58 1
半截诗
|
5月前
|
编译器 C语言 C++
【C++篇】解密 STL 动态之魂：全面掌握 C++ vector 的高效与优雅
【C++篇】解密 STL 动态之魂：全面掌握 C++ vector 的高效与优雅
半截诗
93 3