【C++】容器篇(一)—— vector 的基本概述以及模拟实现

简介: 【C++】容器篇(一)—— vector 的基本概述以及模拟实现

前言:

在之前,我们已经对 string类进行了基本的概述,并且手动的实现了string类中常用的接口函数。本期,我将带领大家学习的是STL库中的一个容器 -- vector 的学习。相比于之前的string类,本期的 vector 相对来说实现起来略微难一点,难点就在于要考虑关于 “迭代器失效”方面和“深浅拷贝”的问题。


前言

在正式的学习之前,我们先来看看STL库中的容器有哪些,让大家先混个脸熟,在接下来,对于其他的容器我也会给大家进行相关的讲解。

  • STL库中的容器如下(勾画的接下来我都会给大家讲解):

💨 而对于 map、set等则是要等到之后在给大家讲解,因为要涉及关于 红黑树的相关知识;

💨 而对于像第一个【arry】这个我们十分的熟悉了,就没有必要在进行讲解了,而【deque】和【queue】二者之间也有很多的不同之处;

💨 而对于【bitset】(位集),我们只需简单的了解即可,它主要的功能是提供一些成员函数,使程序员不必通过位运算就能很方便地访问、修改其中的任意一位


(一)基本介绍

1、相关定义

既然要学习vector,那么首先就需要知道到底什么是vector,定义如下:

  • vector是STL库中的一种序列式容器事实上和数组差不多(但它比数组更优越),由于其大小(size)可变,常用于数组大小不可知的情况下来替代数组。
  • 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问,和数组一样高效。

2、vector的引入

  1. 一般来说数组不能动态拓展,因此在程序运行的时候不是浪费内存,就是造成越界
  2. 而 vector 正好弥补了这个缺陷,它不像数组那样,它的大小是可以动态改变的,相当于可拓展的数组(动态数组),它的随机访问快,在中间插入和删除慢,但在末端插入和删除快,而且它的大小会被容器自动处理。

3、vector的优点

  1. 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效;
  2. 对于其它不在末尾的删除和插入操作,效率更低;
  3. 比起list 和 forward_list 统一的迭代器和引用更好。

4、vector使用本质

本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。

其做法是:分配一个新的数组,然后将全部元素移到这个数组。

就时间而言,这是 一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。


(二)vector的使用

vector学习时一定要学会查看文档:vector的文档介绍,vector在实际中非常的重要,在实际中我们熟悉常见的接口就可以,下面列出了哪些接口是要重点掌握的。

1、vector的定义

2、vector iterator 的使用

3、vector的空间增长

4、vector的增删查改

大家通过文档不难发现,vector容器跟之前学习的string类的接口很相似。因此,通过之前对string的学习,并且掌握的话对于本次学习的vector学习到掌握是很容易的!!!


(三)接口函数的介绍

接下来,我就将为大家介绍常用的接口以及实现的过程!!!

1、Member functions

对于构造,我们通过阅读文档可以发现,文档给出的构造有四种,分别是:

  • 默认构造
  • n个val构造
  • 迭代区间构造
  • 拷贝构造


接下来,我直接给大家展示相关方法是如何进行函数构造的。

1️⃣n个val构造

  • 代码如下:
void test1()
{
  //n个val构造
  vector<int>arr(10,1); //ten ints with value 1
  for (int i = 0; i < arr.size(); ++i)
  {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main()
{
  test1();
  return 0;
}
  • 解释说明:

上述代码我们构造包含 10个元素的容器。每个元素都是 1 的副本。


2️⃣迭代区间构造

  • 代码如下:
void test()
{
    vector<int>arr(10,1);
  //迭代区间构造
  vector<int>tmp(arr.begin(), arr.end());
  for (int i = 0; i < tmp.size(); ++i)
  {
    cout << tmp[i] << " ";
  }
  cout << endl;
}
int main()
{
  test();
  return 0;
}
  • 解释说明:

上述通过构造一个容器,其中包含与范围 [first、last)(特别注意迭代区间的范围是左闭右开) 一样多的元素,每个元素都以相同的顺序从该区域中的相应元素构造。

拓展说明:

对于迭代器构造,不知道大家有没有发现文档中给出的描述:

迭代器不应该叫做【iterator】吗,这里怎么叫做【inputiterator】呢?

  1. 这就要说到一个问题了,那就是迭代器是分类型的(说起来很复杂,我简单讲一下)。
  2. 不同的迭代器除了之前说过的正向、反向 这样的使用属性之外,还有相关的特性属性,比如双向、单向等;
  3. 因此在这里就表示你使用时即可传单向,也可以传双向,以及随机等(即可以传任意类型)

例如以下:

string str("have a good day");
  vector<int>vv(str.begin(), str.end());
  for (int i = 0; i < vv.size(); ++i)
  {
    cout << vv[i] << " ";
  }
  cout << endl;

输出的即是对应的 ASCll 码值。除此之外,还可以进行【++】或【--】操作。


3️⃣拷贝构造

  • 代码如下:
void test()
{
  vector<int>arr;  //默认构造
  arr.push_back(1);
  arr.push_back(2);
  arr.push_back(3);
  arr.push_back(4);
  arr.push_back(5);
  //拷贝构造
  vector<int> tmp(arr);
  for (auto e : tmp)
  {
    cout << e << " ";
  }
  cout << endl;
}
  • 解释说明:

复制构造函数,以相同的顺序构造一个容器,其中包含 arr 中每个元素的副本。


2、Iterators

接下来就是关于正向迭代器和反向迭代器的介绍,这个我相信大家在之前的学习中都有了解,我就不过多阐述。

1️⃣begin()和end()

  • 代码如下:
void test()
{
  vector<int>arr;
  arr.push_back(1);
  arr.push_back(2);
  arr.push_back(3);
  arr.push_back(4);
  arr.push_back(5);
  vector<int>::iterator it = arr.begin();
  while (it != arr.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
}

2️⃣rbegin()和rend()

  • 代码如下:
void test()
{
  vector<int>arr;
  arr.push_back(1);
  arr.push_back(2);
  arr.push_back(3);
  arr.push_back(4);
  arr.push_back(5);
  vector<int>::reverse_iterator rit = arr.rbegin();
  //auto rit = arr.rbegin();
  while (rit != arr.rend())
  {
    cout << *rit << " ";
    rit++;
  }
  cout << endl;
}

3、Capacity

对于容量的相关接口,跟之前学的string是类似的。

这里需要讲明的一点是关于 【capacity】扩容的问题,capacity的代码在 vs 和 g++ 下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。 这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义 的。vs是PJ版本STL,g++是SGI版本STL。

  • 用以下测试代码分别在两种环境下运行后:
// 测试vector的默认扩容机制
void TestVectorExpand()
{
  size_t sz;
  vector<int> v;
  sz = v.capacity();
  cout << "making v grow:\n";
  for (int i = 0; i < 100; ++i)
  {
    v.push_back(i);
    if (sz != v.capacity())
    {
      sz = v.capacity();
      cout << "capacity changed: " << sz << '\n';
    }
  }
}
  • 在vs下的结果:

  • 在g++下的结果:

接下来,对于reserve 和 resize,我们在后面的接口函数模拟实现上具体的讲解,以及带大家来理解迭代器失效的问题!!


(四)vector模拟实现

1、成员变量

我这里的实现风格整体来说是按照库里面的实现方式来进行操作的(如果大家有兴趣,可以去库里面看下源码)

  • 首先,我们这里实现的vector是 typedef出来的,具体如下(分为普通版本和const版本):
typedef T* iterator;
typedef const T* const_iterator;
  • 而对于类的成员变量如下:
private:
    iterator _start;
    iterator _end;
    iterator _end_of_storage;
  • 解释说明:

⚔️ _start:表示指向数据的开始位置;

⚔️ _end:表示指向数据的结尾位置的下一个位置;

⚔️ _end_of_storage:表示的是整个空间的大小。


2、成员函数

1️⃣构造函数

这些都跟之前是一样的,在这里就不多说了,具体如下:

vector()
      : _start(nullptr)
      , _end(nullptr)
      , _end_of_storage(nullptr)
    {}

2️⃣析构函数

~vector()
    {
      if (_start)
      {
        delete[] _start;
        _end = _end_of_storage = _start = nullptr;
      }
    }

3️⃣拷贝构造

  • 现代写法:
//现代写法
    vector(const vector<T>& arr)
    {
      vector<int> tmp(arr.begin().arr.end());
      swap(tmp);
    }
  • 传统写法:
vector(const vector<T>& arr)
    {
      _start = new T[arr.capacity()];
      for (size_t i = 0; i < arr.size(); ++i)
      {
        _start[i] = arr._start[i];
      }
      _end = _start + arr.size();
      _end_of_storage = _start + arr.capacity();
    }

3、迭代器

1️⃣begin() 和 end()

这里我提供了两个版本的,分别是普通版本和const版本的实现。

  • 具体如下:
iterator begin()
    {
      return _start;
    }
    iterator end()
    {
      return _end;
    }
    const_iterator begin()const
    {
      return _start;
    }
    const_iterator end()const
    {
      return _end;
    }

对于反向迭代器,我放在之后的学习中再去讲解,因为将会涉及一些其他的东西在里面。


4、容量

1️⃣size()

理解这应该很容易理解,对于有效位数据位的大小,就为【_end】位置与【_start】位置的距离为多少。

  • 具体如下:
//长度大小
    size_t size()const
    {
      return _end - _start;
    }

2️⃣capacity()

理解对于数据所占空间的大小,就为首元素位置与整体空间大小的差值。

  • 具体如下:
//空间大小
    size_t capacity()const
    {
      return _end_of_storage - _start;
    }

3️⃣empty()

  • 具体如下:
bool empty()
    {
      return _start ==  _end;
    }

4️⃣reserve()

特点reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。

  • 代码展示:
void reserve(size_t n)
    {
      //首先先判断是否需要开辟新空间
      if (n > capacity())
      {
        //开新空间
        T* tmp = new T[n];
        if (_start)
        {
          //元素拷贝到新空间
          memcpy(tmp, _start, sizeof(T)*size());
          //释放旧空间
          delete[] _start;
        }
        _start = tmp;
        _end = tmp + size();
        _end_of_storage = tmp + n;
      }
    }

上述模拟实现的vector中的reserve接口中,会使用 memcpy 进行的拷贝,但是大家通过代码有没有发现什么问题呢?

  • 当我们用测试用例去打印结果的时候,会发生程序挂掉了:

  • 我们通过调试去观察是什么原因导致的问题,具体如下:

现象解释:

  1. 首先,我们知道size() = _end - _start;
  2. 按理说释放之后应该为0,因为 tmp=_start,因此我们可以把上述带入公式带入代码中换掉,我们就不难得出一点,此时代码就为 【tmp + _end - _start(tmp) 】,所以此时最终为0了;
  3. 相当于_start 是一个地址,而最终却是 0 减 一个地址。即_end 还是之前的,而_start 却不是之前的_start 了;
  4. 因此,最好的解决办法就是在事先保留一份最初的 size() 即可。
  • 代码如下:
void reserve(size_t n)
    {
      //首先先判断是否需要开辟新空间
      if (n > capacity())
      {
        size_t num = size();
        //开新空间
        T* tmp = new T[n];
        if (_start)
        {
          //元素拷贝到新空间
          memcpy(tmp, _start, sizeof(T)*size());
          //释放旧空间
          delete[] _start;
        }
        _start = tmp;
        _end = _start + num;
        _end_of_storage = _start + n;
      }
    }

最终通过上诉我们得出一点:

  1. 如果拷贝的是 自定义类型的元素,memcpy既高效又不会出错;
  2. 但如果拷贝的是自定义类型元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅拷贝

结论:如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为memcpy是 浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。

5️⃣resize()

resize在开空间的同时还会进行初始化,影响size。

  • 代码展示:
void resize(size_t n, const T& val = T())
    {
      if (n < size())
      {
        _end = _start + n;
      }
      else
      {
        if(n > capacity())
          reserve(n);
        while (_end != _start + n)
        {
          _end = val;
          ++_end;
        }
      }
    }
  • 注意这里的val初始化时初始化为 T();
  • 当单独使用T()时,当前行结束就会自动调用销毁,而当时用 const  T& val =T() 就可以延长生命周期。

5、元素访问

1️⃣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];
    }

6、修改

1️⃣push_back()

//尾插
    void push_back(const T& X)
    {
      //先判断空间
      if (_end == _end_of_storage)
      {
        reserve(capacity() == 0 ? 4 : capacity() * 2);
      }
      //移动元素
      *_end = X;
      ++_end;
    }

2️⃣pop_back()

void pop_back()
    {
      assert(!empty()); //注意判空
       --_end;
    }

3️⃣insert()

意思很简单,即在 pos 位置出插入 val 元素即可。但是这里却有一个很坑的点,那就是不小心写出来的代码就会引起迭代器失效的问题。

  • 大家先看以下代码:
void insert(iterator pos, const T& val)
    {
      assert(pos >= _start);
      assert(pos <= _end);
      if (_end == _end_of_storage)
      {
        reserve(capacity() == 0 ? 4 : capacity() * 2);
      }
      iterator finish = _end - 1;
      while (finish >= pos)
      {
        *(finish + 1) = *finish;
        --finish;
      }
      *pos = val;
      ++_end;
    }

此时,数组中只有4个元素(即数组中有四个元素),当我们想在第三个位置处插入元素0时,我们打印对应的结果,就会发现结果报错:

但是,当我们提前先把 5 也放入数组(即数组中有5个元素),此时再去进行插入操作时,结果又是正确的:

那么上述是什么问题导致的呢?我们先调试看看:

解释说明:

  • 通过上述我们不难看出一个问题,程序只走了一步扩容操作,pos 位置此时没有发生变化,而 _start 和 _end 已经发送改变了。
  • 此时这种情况就是一种经典的迭代器失效现象

解决方法:

  • 我们需要更新 pos位置 ,根据相对位置来判断扩容之后处于新空间的位置是多少。
  • 纠正写法:
void insert(iterator pos, const T& val)
    {
      assert(pos >= _start);
      assert(pos <= _end);
      if (_end == _end_of_storage)
      {
        size_t len = pos - _start;  //迭代器失效问题(野指针)
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
      }
      iterator finish = _end - 1;
      while (finish >= pos)
      {
        *(finish + 1) = *finish;
        --finish;
      }
      *pos = val;
      ++_end;
    }

但是上述改了之后是不是就 ok l呢?其实并不是的,程序其实还有 bug。

此时,很多小伙伴就会说我都已经更新了pos呀,但是我们经过调试之后发现没有起作用在这里:

解释说明:

  • 最主要的原因就是这里是值传递,形参的改变是不会改变实参的,所以说外面的pos依旧没有实现更新操作,依旧会失效。

💨  正确写法是通过返回值去解决问题的,返回的是迭代器,即新插入元素的位置

  • 正确代码:
iterator  insert(iterator pos, const T& val)
    {
      assert(pos >= _start);
      assert(pos <= _end);
      if (_end == _end_of_storage)
      {
        size_t len = pos - _start;  //迭代器失效问题(野指针)
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
      }
      iterator finish = _end - 1;
      while (finish >= pos)
      {
        *(finish + 1) = *finish;
        --finish;
      }
      *pos = val;
      ++_end;
      return pos;
    }

4️⃣erase()

这里主要的就是从后往前删除的,这点需要大家注意一下。

  • 代码如下:
void erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos < _end);
      iterator start = pos + 1;
      while (start != _end)
      {
        *(start - 1) = *start;
        ++start;
      }
      --_end;
    }

此时问题又来了,上述这样写会不会也有迭代器失效的问题呢?

💨  首先,我们简单的测试一下:

  • 从上述结果我们不难发现,经过验证程序是没有问题的。

💨  接下来,我们在去看看在库中表现如何:

解释说明:

  1. erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代 器不应该会失效;
  2. 但是:如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置是 没有元素的,那么pos就失效了.因此删除vector中任意位置上元素时,vs就认为该位置迭代器失效 了。
  • 如果大家下去验证,发现不管是不是在结束的位置,编译器都会默认程序崩溃。

我们通过调试可以发现,库中默认的检查手段直接就是使得程序发送崩溃了:

注意:

  • 说明一点的是代码的结果还跟环境有关,大家可以去linux下进行测试看看结果是怎么样的

💨  与vector类似,string在插入+扩容操作+erase之后,迭代器也会失效:

void TestString()
{
     string s("hello");
     auto it = s.begin();
     // 放开之后代码会崩溃,因为resize到20会string会进行扩容
     // 扩容之后,it指向之前旧空间已经被释放了,该迭代器就失效了
     // 后序打印时,再访问it指向的空间程序就会崩溃
     //s.resize(20, '!');
     while (it != s.end())
     {
         cout << *it;
         ++it;
     }
     cout << endl;
     it = s.begin();
     while (it != s.end())
     {
         it = s.erase(it);
         // 按照下面方式写,运行时程序会崩溃,因为erase(it)之后
         // it位置的迭代器就失效了
         // s.erase(it); 
         ++it;
     }
}

终上所述,我们认为在erase之后,pos是会发生失效的,因此建议不要访问,行为结果未定义(具体跟编译器有关系)


5️⃣swap()

void swap(vector<T>&arr)
    {
      swap(_start, arr.start);
      swap(_end, arr.end);
      swap(_end_of_storage, arr._end_of_storage);
    }

总结

到此,关于vector的全部内容便讲解完毕了,接下来我们简单的总结一下本文都学了什么

  1. 首先,在开头我先给大家介绍了关于 STL库中的容器有哪些,让大家初步的认识了各个容器,对其有个基本的印象;
  2. 其次,先给出了关于vector的基本概念介绍,让大家知道vector的作用以及优势;
  3. 接下来,我们通过结合文档内容,带大家去认识了vector中最常用的接口并模拟实现了各个函数接口;
  4. 最后,关于vector最重要的便是关于迭代器失效的问题以及解决方法(重点)需要大家掌握。

以上全是全文的基本内容了。感谢大家的阅读与支持!!!

相关文章
|
2天前
|
C++ 索引 容器
黑马c++ STL部分 笔记(9) map/multimap容器
黑马c++ STL部分 笔记(9) map/multimap容器
|
2天前
|
C++ 容器
黑马c++ STL部分 笔记(8) set/ multiset 容器
黑马c++ STL部分 笔记(8) set/ multiset 容器
|
2天前
|
存储 C++ 容器
黑马c++ STL部分 笔记(7) list容器
黑马c++ STL部分 笔记(7) list容器
|
2天前
|
C++ 容器
黑马c++ STL部分 笔记(6) queue 容器
黑马c++ STL部分 笔记(6) queue 容器
|
2天前
|
C++ 容器
黑马c++ STL部分 笔记(5) stack容器
黑马c++ STL部分 笔记(5) stack容器
|
2天前
|
C++ 容器
黑马c++ STL部分 笔记(3) deque容器
黑马c++ STL部分 笔记(3) deque容器
|
2天前
|
C++ 容器
黑马c++ STL部分 笔记(3) vector容器
黑马c++ STL部分 笔记(3) vector容器
|
2天前
|
C++ 容器
黑马c++ STL部分 笔记(2) string容器
黑马c++ STL部分 笔记(2) string容器
|
6天前
|
Prometheus 监控 Cloud Native
构建高效稳定的Docker容器监控体系
【5月更文挑战第20天】 在微服务架构日益普及的今天,Docker作为其重要的实现技术之一,承载着大量应用的运行。然而,随之而来的是对于容器健康状态、资源使用情况以及性能指标的监控需求急剧增加。本文旨在探讨构建一个高效且稳定的Docker容器监控体系,不仅涵盖了监控工具的选择与配置,还详细阐述了监控数据的分析与处理流程。通过精心设计的监控策略和实时响应机制,我们能够确保系统的稳定性,并及时发现及处理潜在的问题。
|
3天前
|
Prometheus 监控 Cloud Native
Ubantu docker学习笔记(九)容器监控 自带的监控+sysdig+scope+cAdvisor+prometheus
Ubantu docker学习笔记(九)容器监控 自带的监控+sysdig+scope+cAdvisor+prometheus