vector类模拟实现(c++)(学习笔记)

简介: 基本框架:

基本框架:

namespace xty
{
  template<class T>
  class vector 
  {
  public:
    typedef T* iterator;
  ///
  //...
  ///
  private:
    iterator _strat;  //起始位置
    iterator _finish;  //最后一个元素的下一个地址
    iterator _end_of_storage;  //容量的最后一个元素
  };
}

vector的大致形状如下:黄色代表每天满的地方。


构造函数

使用初始化列表实现一个简单的无参构造函数。

    //无参构造函数
    vector()
      :_finish(nullptr),
      _start(nullptr),
      _end_of_storage(nullptr)
    {}


析构函数

记住要带[]即可。

    ~vector()
    {
      delete[] _start; //用带括号的
      _start = nullptr;
      _finish = nullptr;
      _end_of_storage = 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);
    }

push_back

size()

    size_t size() const
    {
      return _finish - _start;
    }

capacity()

    size_t capacity() const 
    {
      return _end_of_storage - _start;
    }

reserve()

因为push_back涉及到扩容函数,需要实现reserve()。

如下示例:

    void  reserve(size_t n)
    {
      if (n > capacity())
      {
        T* tem = new T[n];
        if (_start)
        {
          memcpy(tem, _start, sizeof(T)*size()); //拷贝过去
          delete[] _start;
        }
        _start = tem;
        _finish = _start + size();   //error
        _end_of_storage = _start + n;
      }
    }

问题1:_finish赋值出错,出bug了,是因为size()函数,调用了空指针,导致报错。

改正:

因为delete之后,原数据就被清空了,所以可以提前保存一下size()的大小。

    void  reserve(size_t n)
    {
      if (n > capacity())
      {
        T* tem = new T[n];
        const size_t sz = size();  //提前保存sz
        if (_start)
        {
          memcpy(tem, _start, sizeof(T)*size()); //拷贝过去
          delete[] _start;
        }
        _start = tem;
        _finish = _start + sz;  //使用sz赋值
        _end_of_storage = _start + n;
      }
    }

push_back()

逻辑比较简单,在vector的尾部添加一个val,就需要一些前置函数。

    //尾插
    void push_back(const T& val)
    {
      //满了扩容
      if (_finish  == _end_of_storage)
      {
        reserve(capacity() == 0 ? 4 : capacity() * 2);
      }
      //插入数据
      *_finish = val;
      _finish++;
    }

迭代器实现

该逻辑也比较简单,注意实现const的版本。

非const和const版本

    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;
    }

pop_back()

尾删。

    bool empty()
    {
      return _start == _finish;
    }
    //尾删
    void pop_back()
    {
      assert(!empty());
      _finish--;
    }

resize()

和string逻辑差不多。

    void resize(size_t n, const T& val = T())
    {
      //一样大,直接返回
      if (n == size())   
      {
        return;
      }
      if (n<size())   //小于直接修改_finish
      {
        while (n != size())
        {
          --_finish; 
        }
      }
      else
      {
        if (n > capacity())   //大于容量先扩容
        {
          reserve(n);
        }
        while (n != size())
        {
          push_back(val);
        }
      }
    }

优化:该函数多次调用push_back()使用while,效率低。

    void resize(size_t n, const T& val = T())
    {
      if (n == size())
      {
        return;
      }
      if (n < size())
      { 
        _finish = _start + n;  //直接移动_finish
      }
      else
      {
        if (n > capacity())
        {
          reserve(n);
        }
        while (_finish != _start + n)  //使用指针操作,减少调用
        {
          *_finish = val;
          _finish++;
        }
      }
    }

insert()***重点

传入迭代器的位置,插入一个元素。

    void insert(iterator pos ,const T& val)
    {
      //检测pos位置是否合法
      assert(pos >= _start);
      assert(pos <= _finish);
      // 满了需要扩容
      if (_finish == _end_of_storage)
      {
        reserve(capacity() == 0 ? 4 : capacity() * 2);
      }
      //从后往前移动
      iterator end = _finish;
      while (end > pos)
      {
        *end = *(end - 1);
        end--;
      }
      *pos = val;   //在该位置赋值
      _finish++;
    }

算法问题1:会造成迭代器失效,迭代器失效,实际就是迭代器底层对应指针所指[空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。

该程序正常来说没有问题,当出现扩容的时候,reserve()会删除原来的空间,去申请新的空间,因此会导致pos指向的那段空间被释放掉,pos变成野指针。


改正:记录插入的相对位置,扩容后根据相对位置更新pos的值。

    void insert(iterator pos, const T& val)
    {
      //检测pos位置是否合法
      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;    //扩容后重新给pos值
      }
      //从后往前移动
      iterator end = _finish;
      while (end > pos)
      {
        *end = *(end - 1);
        end--;
      }
      *pos = val;   //在该位置赋值
      _finish++;
    }

算法问题2:执行insert后,如果扩容,pos位置已经改变了,而函数外面的pos因为是值传递,并没有修改,同样导致了野指针的问题。(迭代器再一次失效!

解决办法:

pos传引用可以吗?

不可以。如下图:如果传入v.begin(),会报错。因为begin()是传值返回,传值返回有一个临时变量,而临时变量具有常性,不能被修改,insert里面就不能修改了!

8a8d201f208d4b3691301c44f1394132.png


857fa135a39d448f89332f04d8082acf.png

通过返回值解决可以吗?

可以,我们可以利用insert返回值的特性,来更新pos防止失效!

如下图:这样就解决问题了。

934d4027831246c8a252f02ffc8931a9.png

最终版本:

    iterator insert(iterator pos, const T& val)
    {
      //检测pos位置是否合法
      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;    //扩容后重新给pos值
      }
      //从后往前移动
      iterator end = _finish;
      while (end > pos)
      {
        *end = *(end - 1);
        end--;
      }
      *pos = val;   //在该位置赋值
      _finish++;
      return pos;
    }

总结:使用insert后,我们默认迭代器失效!因为我们不知道何时执行扩容操作,因此需要重新对pos赋值,防止这类情况发生!

erase()***重点

指定位置执行删除操作。

    void erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos < _finish);
      auto end = pos + 1;
      while (end < _finish)
      {
        //后给前,从前往后
        *(end - 1) = *end;
        end++;
      }
      _finish--;
    }

问题1:erase会导致迭代器失效?

==会导致!==如果删除最后一个位置,最后一个位置就变成了空位置,导致pos也指向了不该指向的位置。因此,erase()执行过后,应该重新给pos赋值再使用!

最终版本:添加返回值。

    iterator erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos < _finish);
      auto end = pos + 1;
      while (end < _finish)
      {
        //后给前,从前往后
        *(end - 1) = *end;
        end++;
      }
      _finish--;
      return pos;
    }


最后给大家一个例子自己感受:

该例子在VS2019会报错

#include <iostream>
using namespace std;
#include <vector>
int main()
{
  vector<int> v{ 1, 2, 3, 4 };
  auto it = v.begin();
  while (it != v.end())
  {
    if (*it % 2 == 0)
      v.erase(it);
    ++it;
  }
  return 0;
}
int main()
{
  vector<int> v{ 1, 2, 3, 4 };
  auto it = v.begin();
  while (it != v.end())
  {
    if (*it % 2 == 0)
      it = v.erase(it);
    else
      ++it;
  }
  return 0;
}

再谈构造函数!

这次实现一个可以规定数量和内容的构造函数。

//正常实现
    vector(size_t n, const T& val = T())
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      reserve(n);
      size_t len = n;
      while (n--)
      {
        push_back(val);
      }
    }
    //构造函数由迭代器实现
    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }

当我们满心欢喜的实现好这两个构造函数后,想要测试一下。结果报错了。

输入: vector vx(10,5);

a7760cdbac374328bda7461e34dacdd2.png

这是为什么呢?因为10,5都被编译器认为是int类型,而编译器在函数重载时,会自动调用最合适的,而它认为第二个函数更适合自己(),因此解引用的时候产生非法间接寻址!

因此我们需要再次实现一个int型的函数重载!

    vector(int n, const T& val = T())
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      reserve(n);
      size_t len = n;
      while (len--)
      {
        push_back(val);
      }
    }


迭代器构造还支持以下方法:

  int a[] = { 1, 2, 3 };
  vector<int> v4(a, a + 3);
  for (auto e : v4)
  {
    std::cout << e << " ";
  }
  std::cout << std::endl;
}

拷贝构造函数****(重点)

如果我们不自己实现拷贝构造函数,编译器就会默认生成一个,但是编译器默认生成的是浅拷贝,不可以。

    //拷贝构造
    vector(const vector<T>& v)
    {
      //扩容
      reserve(v.capacity());
      memcpy(_start, v._start, sizeof(T) * v.size());
      _finish = _start + v.size();
    }

现在我们写完这个函数的拷贝构造之后,看看是否有问题:

c6c41b544d2c41c1b3ef5bc2c2260cef.png

提前告诉大家,这个程序会崩溃,因为memcpy()实现的是浅拷贝,他仅仅会拷贝v3的首尾指针,并不会开一个新的空间去存储相应的字符串。所以,程序结束时,调用析构函数,会连续析构两次!

**解决办法:**不适用memcpy()自己实现深拷贝,使用‘=’即可实现,因为string赋值操作就是深拷贝,string的赋值,就会先开空间,再拷贝!

48999b7bc1014cbb8442d31fd1e94f1f.png

    //拷贝构造
    vector(const vector<T>& v)
    {
      //扩容
      reserve(v.capacity());
      //memcpy(_start, v._start, sizeof(T) * v.size());
      for (size_t i = 0; i <v.size(); i++)
      {
        _start[i] = v._start[i];   //变成string对象的拷贝
      }
      _finish = _start + v.size();
    }

但是reverse()也会产生这个浅拷贝的问题,因此将reserve也应该改成深拷贝。

    void  reserve(size_t n)
    {
      if (n > capacity())
      {
        T* tem = new T[n];
        const size_t sz = size();  //提前保存sz
        if (_start)
        {
          //memcpy(tem, _start, sizeof(T)*size()); //拷贝过去
          for (size_t i = 0; i < size(); i++)
          {
            tem[i] = _start[i];
          }
          delete[] _start;
        }
        _start = tem;
        _finish = _start + sz;  //使用sz赋值
        _end_of_storage = _start + n;
      }
    }

这样vector的问题就解决了。但是vector<vector<int>>还有问题!!!请看赋值重载的部分。

=运算符重载***(重点)

这里暴露了一个问题,就是虽然外面的vector是深拷贝,但是里面的vector是浅拷贝,是由于没有写vector的赋值重载,再补充一个赋值重载即可!

    vector<T>& 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(_end_of_storage, v._end_of_storage);
    }

74b41f6fb3b4472bb227ec1ff03e581c.png

目录
打赏
0
0
0
0
1
分享
相关文章
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
【C++篇】深度解析类与对象(中)
在上一篇博客中,我们学习了C++类与对象的基础内容。这一次,我们将深入探讨C++类的关键特性,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载、以及取地址运算符的重载。这些内容是理解面向对象编程的关键,也帮助我们更好地掌握C++内存管理的细节和编码的高级技巧。
【C++篇】深度解析类与对象(上)
在C++中,类和对象是面向对象编程的基础组成部分。通过类,程序员可以对现实世界的实体进行模拟和抽象。类的基本概念包括成员变量、成员函数、访问控制等。本篇博客将介绍C++类与对象的基础知识,为后续学习打下良好的基础。
|
1月前
|
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
70 19
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
53 13
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
56 5
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
43 5
【C++面向对象——类的多态性与虚函数】计算图像面积(头歌实践教学平台习题)【合集】
本任务要求设计一个矩形类、圆形类和图形基类,计算并输出相应图形面积。相关知识点包括纯虚函数和抽象类的使用。 **目录:** - 任务描述 - 相关知识 - 纯虚函数 - 特点 - 使用场景 - 作用 - 注意事项 - 相关概念对比 - 抽象类的使用 - 定义与概念 - 使用场景 - 编程要求 - 测试说明 - 通关代码 - 测试结果 **任务概述:** 1. **图形基类(Shape)**:包含纯虚函数 `void PrintArea()`。 2. **矩形类(Rectangle)**:继承 Shape 类,重写 `Print
50 4
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等