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++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
46 12
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
55 16
类和对象(中 )C++
本文详细讲解了C++中的默认成员函数,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系,如构造函数的主要任务是初始化对象,而非创建空间;析构函数用于清理资源;拷贝构造与赋值运算符的区别在于前者用于创建新对象,后者用于已存在的对象赋值。同时,文章还探讨了运算符重载的规则及其应用场景,并通过实例加深理解。最后强调,若类中存在资源管理,需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。
类和对象(上)(C++)
本篇内容主要讲解了C++中类的相关知识,包括类的定义、实例化及this指针的作用。详细说明了类的定义格式、成员函数默认为inline、访问限定符(public、protected、private)的使用规则,以及class与struct的区别。同时分析了类实例化的概念,对象大小的计算规则和内存对齐原则。最后介绍了this指针的工作机制,解释了成员函数如何通过隐含的this指针区分不同对象的数据。这些知识点帮助我们更好地理解C++中类的封装性和对象的实现原理。
|
2月前
|
【c++】继承(继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员)
本文深入探讨了C++中的继承机制,作为面向对象编程(OOP)的核心特性之一。继承通过允许派生类扩展基类的属性和方法,极大促进了代码复用,增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式(public、protected、private)、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题,并对比了继承与组合的优缺点。最后总结指出,虽然继承提高了代码灵活性和复用率,但也带来了耦合度高的问题,建议在“has-a”和“is-a”关系同时存在时优先使用组合。
131 6
类和对象(下)C++
本内容主要讲解C++中的初始化列表、类型转换、静态成员、友元、内部类、匿名对象及对象拷贝时的编译器优化。初始化列表用于成员变量定义初始化,尤其对引用、const及无默认构造函数的类类型变量至关重要。类型转换中,`explicit`可禁用隐式转换。静态成员属类而非对象,受访问限定符约束。内部类是独立类,可增强封装性。匿名对象生命周期短,常用于临时场景。编译器会优化对象拷贝以提高效率。最后,鼓励大家通过重复练习提升技能!
|
4月前
|
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
119 19
AI助理

你好,我是AI助理

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