C++初阶学习第九弹——探索STL奥秘(四)——vector的深层挖掘和模拟实现

简介: C++初阶学习第九弹——探索STL奥秘(四)——vector的深层挖掘和模拟实现

前言:

在前面我们已经学习了string的使用及其模拟实现,并且我们也已经学习了vector的使用,今天我们就来学习一下vector的模拟实现


一、 vector的基本成员变量

我们之前已经学习了vector的使用,所以也基本了解了其机制,现在我们来看一下vector工作的基本机制

从图中我们可以看出,vector的操作机制实际上是通过三个指针来实现的:

_start、_finish、_endOfStorage

所以vector的基本成员变量为:

#include<iostream>
using namespace std;
//命名一个命名空间,在这个命名空间中实现我们自己的vector,这样能避免受库中vector的影响
namespace zda
{
  template<class T>
  class vector
  {
  privated:
    T* _start;      //指向有效数据的头
    T* _finish;     //指向有效数据的尾
    T* _endOfStorage;    //指向容量的尾
  };
}

因为vector的本质上与顺序表很相似,只是存储的数据上变的更加多元化了,所以我们可以对基本成员做一些调整,将其改成迭代器相关的,方便我们后面写类成员函数

改进后:

#include<iostream>
using namespace std;
//命名一个命名空间,在这个命名空间中实现我们自己的vector,这样能避免受库中vector的影响
namespace zda
{
  template<class T>
  class vector
  {
  public:
    // Vector的迭代器是一个原生指针
    typedef T* iterator;
    typedef const T* const_iterator;
 
  privated:
    iterator _start;      //指向有效数据的头
    iterator _finish;     //指向有效数据的尾
    iterator _endOfStorage;    //指向容量的尾
  };
}

接下来,我们就开始进入今天的正题,模拟vector的五大步骤:

1、构造和销毁

2、迭代器相关

3、容量相关

4、元素访问

5、vector的修改操作

二、 vector的逐步实现

1、构造和销毁

构造的方法主要有以下五种:

·  默认构造

· 构造同时将前n个初始化

· 迭代器构造法

· 拷贝构造

· operator=运算符重载

    //一、vector的构造销毁
    //1、默认构造
    vector()
      :_start(nullptr)
      ,__finish(nullptr)
      ,_endOfStorage(nullptr)
    {}
 
    //2、构造同时将前n个初始化
    vector(size_t n, const T& m = T())
      :_start(nullptr)
      , __finish(nullptr)
      , _endOfStorage(nullptr)
    {
      reserve(n);     //开辟n个大小的空间,这个函数在后面
      while (n--)
      {
        push_back(m);     //尾插,也在后面讲
      }
    }
    //但是上面这个函数会有一个特殊情况出现
    //例如对于vector<int> v(5,3)
    //由于v中的参数是(int,int),所以编译器容易把它与迭代器相关的函数去配对
    //所以对于上面这个函数我们又写了一个vector(int n, const T& m = T())类型的来避免错误发生
    //这种情况下参数一定都为int型的,所以我们可以按顺序表的方式来写这个函数
    vector(int n, const T& m = T())
      :_start(new T[n])
      , __finish(nullptr)
      , _endOfStorage(nullptr)
    {
      for (int i = 0; i < n; i++)
      {
        _start[i] = m;
      }
    }
 
    //3、迭代器构造法
    //为了实现不同迭代器的传参构造,我们这里再创建一个迭代器模板
    template<class InputInterator>
    vector(InputInterator first, InputInterator last)
    {
      while (fast != last)
      {
        push_back(*first);     //尾插的时候会检查扩容,所以也可以不写reserve函数
        first++;
      }
    }
 
    //4、拷贝构造
    vector(const vector<T>& v)
      :_start(nullptr)
      ,_finish(nullptr)
      ,_endOfStorage(nullptr)
    {
      reserve(v.capacity());
      iterator it = begin();
      const_iterator vit = v.cbegin();       //这里涉及到const迭代器的内容,也是在后面讲
      while (vit != v.cend())
      {
        *it++ = *vit++;
      }
      _finish = it;
    }
 
    //5、operator=运算符重载
    vector<T>& operator=(vector<T> v)
    {
      swap(v);    //由于这里的v是对目标对象的复制,是开辟的新空间,所以我们完全可以swap直接交换而得
      return *this;
    }
 
    //析构
    ~vector()
    {
      if (_start)
      {
        delete _start;
        _start = _finish = _endOfStorage = nullptr;
      }
    }

2、迭代器相关

    // 迭代器相关(迭代器主要就是找到头尾)
    iterator begin()
    {
      return _start;
    }
 
    iterator end()
    {
      return _finish;
    }
 
    const_iterator cbegin() const
    {
      return _start;
    }
 
    const_iterator cend() const
    {
      return _finish;
    }

3、容量相关

容量相关的最重要的就是扩容,就是reserve函数,同时我们也需要注意一下resize函数,这两者各自的特点需要记清,这些前面文章有讲到,我们这里只强调一下:

resize函数即可以扩容,也可以缩容,同时还可以初始化,这个函数创造性挺大

size_t size() const
{
  return _finish - _start;
}
 
size_t capacity() const
{
  return _endOfStorage - _start;
}
 
bool empty() const
{
  return _start == _finish;
}
 
void reserve(size_t n)
{
  if (n > capacity())
  {
    size_t oldSize = size();
    // 1. 开辟新空间
    T* tmp = new T[n];
 
    // 2. 拷贝元素
    // 这里不能直接使用memcpy,原因我们将放到下面专门讲
    //if (_start)
    //  memcpy(tmp, _start, sizeof(T)*size);
 
    if (_start)
    {
      for (size_t i = 0; i < oldSize; ++i)
        tmp[i] = _start[i];
 
      // 3. 释放旧空间
      delete[] _start;
    }
 
    _start = tmp;
    _finish = _start + oldSize;
    _endOfStorage = _start + n;
  }
}
 
void resize(size_t n, const T& value = T())
{
  // 1.如果n小于当前的size,则数据个数缩小到n
  if (n <= size())
  {
    _finish = _start + n;
    return;
  }
 
  // 2.空间不够则增容
  if (n > capacity())
    reserve(n);
 
  // 3.将size扩大到n
  iterator it = _finish;
  _finish = _start + n;
  while (it != _finish)
  {
    *it = value;
    ++it;
  }
}

4、元素访问

元素访问关键就是运算符重载(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];
}
 
T& front()
{
  return *_start;
}
 
const T& front()const
{
  return *_start;
}
 
T& back()
{
  return *(_finish - 1);
}
 
const T& back()const
{
  return *(_finish - 1);
}

5、vector的修改操作

vector的修改操作最关键的就是insert函数和erase函数,就是在任意位置插入和删除,尾插尾删可以直接调用这两个函数来实现,但这两个函数细节也挺多,具体实现细节看下面实现过程

// vector的修改操作
void push_back(const T& x)      //尾插,可以直接调用insert函数
{
  insert(end(), x);
}
 
void pop_back()         //尾删,跟尾插一样,可以调用erase函数
{
  erase(end() - 1);
}
 
void swap(vector<T>& v)      //这个交换函数在上面构造时是有用到的
{
  std::swap(_start, v._start);
  std::swap(_finish, v._finish);
  std::swap(_endOfStorage, v._endOfStorage);
}
 
iterator insert(iterator pos, const T& x)
{
  assert(pos <= _finish);
 
  // 空间不够先进行增容
  if (_finish == _endOfStorage)
  {
    //size_t size = size();
    size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;
    reserve(newCapacity);
 
    // 如果发生了增容,需要重置pos
    pos = _start + size();
  }
 
  iterator end = _finish - 1;
  while (end >= pos)
  {
    *(end + 1) = *end;
    --end;
  }
 
  *pos = x;
  ++_finish;
  return pos;
}
 
// 返回删除数据的下一个数据
// 方便解决:一边遍历一边删除的迭代器失效问题
// (迭代器失效问题在vector中会发生,不知道的可以看我之前文章)
iterator erase(iterator pos)
{
  // 挪动数据进行删除
  iterator begin = pos + 1;
  while (begin != _finish) {
    *(begin - 1) = *begin;
    ++begin;
  }
 
  --_finish;
  return pos;
}

三、总结

上面的就是vector的模拟实现的全部代码段,这些还不是vector的全部内容,还有vector复制等几个细节我们还没讲,这个感兴趣的可以关注一下,将在下一篇讲解这些细小知识点

感谢各位大佬观看,创作不易,还请各位大佬点赞支持!!!

相关文章
|
1天前
|
设计模式 存储 C++
【C++/STL】:stack/queue的使用及底层剖析&&双端队列&&容器适配器
【C++/STL】:stack/queue的使用及底层剖析&&双端队列&&容器适配器
20 2
|
22小时前
|
存储 编译器 C++
【C++ 初阶路】--- 类和对象(下)
【C++ 初阶路】--- 类和对象(下)
7 1
|
22小时前
|
存储 编译器 C语言
【C++初阶路】--- 类和对象(中)
【C++初阶路】--- 类和对象(中)
7 1
|
22小时前
|
安全 编译器 程序员
【C++初阶】--- C++入门(上)
【C++初阶】--- C++入门(上)
8 1
|
1天前
|
编译器 C++ 容器
【C++/STL】:list容器的深度剖析及模拟实现
【C++/STL】:list容器的深度剖析及模拟实现
8 2
|
21小时前
|
编译器 C语言 C++
C++ STL中list迭代器的实现
C++ STL中list迭代器的实现
C++ STL中list迭代器的实现
|
1天前
|
存储 C++ 容器
【C++/STL】:list容器的基本使用
【C++/STL】:list容器的基本使用
6 1
|
1天前
|
存储 算法 C++
【C++/STL】:vector容器的基本使用
【C++/STL】:vector容器的基本使用
13 1
|
21小时前
|
存储 算法 编译器
【C++航海王:追寻罗杰的编程之路】vector
【C++航海王:追寻罗杰的编程之路】vector
3 0
|
22小时前
|
存储 安全 编译器
【C++初阶】--- C++入门(下)
【C++初阶】--- C++入门(下)
4 0