C++入门第七篇--STL模板--vector模拟实现

简介: C++入门第七篇--STL模板--vector模拟实现

前言:

有了前面的string库的介绍,在这里我就不再介绍vector库了,而是直接模拟实现了。

vector库的概念和作用:

vector库是针对于数组的数据类型的容器,它有点类似我们曾经实现过的顺序表,你完全可以按照顺序表去理解vector,针对顺序表,我们自然少不了增删查改的功能,所以接下来让我们模拟实现一下vector库。

模拟实现过程:

1.私有成员变量的设置:

在这里,我们这样设置我们的私有成员变量,由于文档中C/C++库的函数大部分是用迭代器实现的,故我们模拟的时候也使用迭代器去操作,故成员如下:

private:
  iterator _start;
  iterator _finish;
  iterator _endofstorage;

其中_start指向顺序表开头,_finish指向顺序表的数字的结尾,而_endofstorage则控制容量,指向容量的结尾

但是我们C++中是没有所谓的iterator的,但是我们知道iterator的本质是指针,故我们对类型重命名如下:

typedef T* iterator;
typedef const T* const_iterator;

2.构造函数 析构函数 拷贝构造函数:

私有成员建立好后,我们下一个便是构建基本的三个函数:构造,析构,拷贝构造。

首先是构造函数:

vector()
  :_start(nullptr)
  , _finish(nullptr)
  , _endofstorage(nullptr)
{}

这里就是常规的全让指针为空,因为我们会在调整容量的位置去为这三个成员变量赋值

析构函数:

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

这里需要注意的点就是:我们是需要在堆区上动态开辟空间的,故我们的析构函数是必须显式实例化的,要让析构函数释放掉我们的堆区空间。

拷贝构造函数:

vector(const vector<T>& s)
  :_start(nullptr)
  , _finish(nullptr)
  , _endofstorage(nullptr)
{
  for (auto& ch : s)
  {
    push_back(ch);
  }
}

再拷贝构造这里,我使用了遍历尾插的方式,或许你会说,直接memcpy不是更好么,但是我们的顺序表不仅仅要存储内置类型,有时也要存储自定义类型,而memcpy对应的是一种浅拷贝,一旦涉及到指针的问题,就会有多次释放的危险,故我们在这里采取尾插的方式,即自定义类型会调用其赋值运算符重载,内置类型则直接赋值,这样就很好的避免了多次释放的问题。

3.赋值运算符重载:

void swap( vector<T>& tmp)
{
  std::swap(_start, tmp._start);
  std::swap(_finish, tmp._finish);
  std::swap(_endofstorage, tmp._endofstorage);
}
vector<T>& operator=( vector<T> tmp)
{
  swap(tmp);
  return *this;
}

我在这里采取的现代写法,和string一样,采用一个变量tmp来打工的方式将值转给*this,大体的写法概念不变,我这里不过多赘述了。

4.size长度 capacity容量:

size用来返回顺序表的长度,而capacity用来返回顺序表的容量

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

5.首尾迭代器返回:

iterator begin()
{
  return _start;
}
iterator end()
{
  return _finish;
}
const_iterator begin()const
{
  return _start;
}
const_iterator end()const
{
  return _finish;
}

在这里我们写了两个版本,一个是可读可写版本,一个是可读不可写版本,分别返回不同的迭代器

6.下标访问操作符[]重载:

其基本和我们字符串的写法区别不大:

T& operator[](size_t pos)
{
  assert(pos < size());
  return _start[pos];
}
const T& operator[](size_t pos) const
{
  assert(pos < size());
  return _start[pos];
}

同样也是两个版本,可改与不可改

7.扩容!!!(本次实现的重点!)

扩容,是我们本次实现的重点,在这里牵扯到一个很关键的问题:迭代器失效。

何为迭代器失效呢?

先看下面的代码:

void reserve(size_t n)
{
  if (n > capacity())
  {
    T* tmp = new T[n];
    if (_start)
    {
      int i = 0;
      for (i = 0; i < size(); i++)
      {
        tmp[i] = _start[i];
      }
      delete _start;
    }
    _start = tmp;
    _finish = _start + size();
    _endofstorage = _start + capacirty();
  }
}

这段代码就涉及到严重的迭代器失效的问题,问题出在我们的delete被销毁后,我们对应的size()和capacity()本质上指向的是之前的被销毁的数组的地址,这样我们使用函数是得不到正确的长度的,因为迭代器此时的地址是无效的,这便是我们所谓的迭代器失效,你可以看这张图理解:

所以,我们可以这样去修改程序:

void reserve(size_t n)
{
  size_t sz = size();
  if (n > capacity())
  {
    T* tmp = new T[n];
    if (_start)
    {
      int i = 0;
      for (i = 0; i < size(); i++)
      {
        tmp[i] = _start[i];
      }
      delete _start;
    }
    _start = tmp;
    _finish = _start + sz;
    _endofstorage = _start + n;
  }
}

即先用一个变量将长度存储起来,而不是再用失效的迭代器返回长度和容量,在这里就是sz来存储,这样,我们就不会出现我们的长度是错误的问题了。

7.改变数组长度:

void resize(size_t n, const T& x = T())//改变数组长度
  {              //注意,内置类型是可以调用构造函数的,在模板这个章节是支持的,在这里别忘了加一个const,因为我们的缺省值是常量,不加const引用权限会放大
    if (n <= capacity())
    {
      _finish = _start + n;
    }
    else
    {
      reserve(n);
      //剩下来填数据:
      while (_finish < _start + n)
      {
        *_finish = x;
        _finish++;
      }
    }
  }

解决了扩容问题,我们其他的都很好解决了,这里也是一样,我们考虑两种情况即可,但是注意依旧用赋值不要用memcpy,因为涉及到浅拷贝的问题。

8.尾插 尾删:

尾插:

void push_back(const T& x)  //尾插
{
  if (_finish == _endofstorage)
  {
    reserve(capacity() == 0 ? 4 : 2 * capacity());
  }
  *_finish = x;
  _finish++;
}

尾删:

void push_pop()
{
  _finish--;
}

没什么好说的,顺手就应该写出来。

9.任意插 任意删:

任意删:

iterator& erase(iterator pos)
  {
    assert(pos >= _start);
    assert(pos <= _finish);
    iterator cur = pos + 1;
    while (cur < _finish)
    {
      *(cur - 1) = *cur;
      cur++;
    }
    _finish--;
    return pos;
  }

任意删的思路和我们顺序表的任意删差不多,直接覆盖即可,强调一下别忘了对我们传入的迭代器进行检验就好。

但是任意删有一个细节就是,我们会涉及到迭代器失效的问题,即这个位置被删除后再想针对这个位置删除就是出现问题,所以我们返回pos,即删除后的下一个位置的指针,这样就可以一直删,不会删除一次就失效了。

任意插:

void insert(iterator pos, const T& x)//任意插
{
  assert(pos >= _start);
  assert(pos <= _finish);//这里可以等于,方便尾插
  if (_finish == _endofstorage)
  {
    size_t range = pos - _start;//在这里先存储一个长度变量方便后续迭代器失效时重新指定位置
    reserve(capacity() == 0 ? 4 : 2 * capacity());
    pos = _start + range;//由于扩容之后pos失效,那样的话pos不在新数组上,故我们要存储一个整型,方便扩容之后把pos重新带到新数组上来,别忘了任意插也存在扩容后迭代器失效的问题,我们的pos也会停留在之前的数组上被销毁之后就丢失了,要重新给到新的数组上
  }
  iterator end = _finish - 1;
  while (end >= pos)//这里要等于,保证其能在pos的位置之前插而不是正好插入pos位置
  {
    *(end + 1) = *end;
    end--;
  }
  *pos = x;
  _finish++;
}

在任意插这里,我们需要注意一个扩容的问题,凡是涉及到扩容和删除的问题,当我们使用迭代器去操作的时候,就要最好看一看是否涉及到迭代器失效的问题,在任意删这里就涉及到了,po针对的是被删除的数组的地址,但我们扩容后,pos的原位置直接失效了,故我们需要在扩容后调整pos到新数组的对应位置上,即:

if (_finish == _endofstorage)
  {
    size_t range = pos - _start;//在这里先存储一个长度变量方便后续迭代器失效时重新指定位置
    reserve(capacity() == 0 ? 4 : 2 * capacity());
    pos = _start + range;//由于扩容之后pos失效,那样的话pos不在新数组上,故我们要存储一个整型,方便扩容之后把pos重新带到新数组上来,别忘了任意插也存在扩容后迭代器失效的问题,我们的pos也会停留在之前的数组上被销毁之后就丢失了,要重新给到新的数组上
  }

然后一个常规的插入pos即可,这里最关键的便是针对迭代器失效我们应该如何处理。

总结:

以上便是我们vector模拟实现的全部内容,和string一样,我们模拟实现vector最关键的目的是学会一些思路,以及熟练的去使用vector,这是最关键的。
补充一句,WBG加油!!!!

目录
相关文章
|
22小时前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
34 21
|
26天前
|
编译器 C语言 C++
【c++丨STL】list模拟实现(附源码)
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构,相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口,然后详细讲解了节点、迭代器及容器的实现过程。 最终,通过这些步骤,我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现,并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣,建议先掌握相关基础知识后再阅读本文,以便更好地理解内容。
32 1
|
1月前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构,适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码,读者可以更好地理解如何使用这些接口。最后,作者总结了`list`的特点和适用场景,并预告了后续关于`list`模拟实现的文章。
55 7
|
2月前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器,包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组,能够根据需要自动调整大小,提供了丰富的操作接口,如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后,还展示了如何使用`vector`创建字符串数组,体现了`vector`在实际编程中的灵活性和实用性。
107 4
|
1月前
|
存储 对象存储 C++
C++ 中 std::array<int, array_size> 与 std::vector<int> 的深入对比
本文深入对比了 C++ 标准库中的 `std::array` 和 `std::vector`,从内存管理、性能、功能特性、使用场景等方面详细分析了两者的差异。`std::array` 适合固定大小的数据和高性能需求,而 `std::vector` 则提供了动态调整大小的灵活性,适用于数据量不确定或需要频繁操作的场景。选择合适的容器可以提高代码的效率和可靠性。
81 0
|
1月前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理,并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表,使用三个迭代器(指针)来维护数组,分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码,帮助读者更好地理解和掌握 `vector` 的实现细节。
50 0
|
15天前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
56 19
|
15天前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
39 13
|
15天前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
43 5
|
15天前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
34 5
AI助理

你好,我是AI助理

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