【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现

简介: 【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现

1. 前言

和string的学习不同

vector即要掌握它的用法

更要会自己去实现一个vector

本章重点:

熟悉STL库中vector的接口函数
自己实现一个简易vector类
本章只实现容量相关函数
和构造,析构,拷贝构造函数

注:vector其实就是顺序容器

string类只用考虑存储字符

然而vector中可以存储任一类型

所以vector的自我实现需要用模板


2. 熟悉vector的接口函数

还是借助老朋友:cplusplus来查阅文档

库中的vector的模板参数有两个

后一个是内存池,用来提升空间利用效率

对于现阶段的学习而言可有可无


2.1 vector的构造与拷贝构造

常见的构造有:

vector<int> v1;
vector<int> v2(10,1);
vector<int> v3(v2);

v2:构造并初始化10个值为1的顺序表

vector可以用迭代器区间初始化:

string str("abcdefg");
vector<string> vv(str.begin(),str.end());

2.2 vector迭代器的使用

和string一样,vector有正向和反向
两种迭代器,且使用方法和string相同

vector<int> vv{1,2,3,4,5,6};
vector<int>::iterator it = vv.begin();
while(it!=vv.end())
{
  cout<<*it;
  it++;
}

2.3 vector空间相关函数

vector的空间相关的函数

和string的机会一模一样

如果你看了文档还不懂的话

可以先阅读此篇文章:string接口函数


2.4 vector的增删查改

push_back和pop_back

都是老朋友了,这里就不多说了

在介绍insert和erase之前

先来了解几个算法库的函数


2.41 find,swap和sort

这三个函数都在头文件:algorithm

find函数:参数是一段迭代器区间
以及在此区间你需要查找的值
找到后返回这个值对应的迭代器位置
若找不到,则返回迭代器last

find的使用:

vector<int> vv{1,2,3,4,5,6,7,8,9};
auto pos = find(vv.begin(),vv.end(),5);
cout<<*pos;

注:使用auto是为了简写迭代器也可以用

vector< int >::iterator替代

swap想必是大家的常客了

这里给它个面子,就不介绍它了

sort非常方便,它内部实现是快排

我们只需要传一个迭代器区间

就可以将整个区间排好序

sort的使用:

vector<int> vv{5,7,3,9,6,4,1,2,8};
sort(vv.begin().vv.end());

2.42 insert和erase

和string不同,vector的insert

的参数pos不是整型,而是迭代器

默认是在pos位置前插入一个数据

insert和find常常配合在一起使用

在整型5前面插入一个100:

vector<int> vv{1,2,3,4,5,6,7,8,9};
auto pos = find(vv.begin(),vv.end(),5);
vv.insert(pos,100);

和string的erase不同,vector

的erase一次只删除一个数据

然而string如果使用缺省值就是

将全部数据删完

vector的erase甚至可以删除一段区间

删除顺序表中值为100的元素

vector<int> vv{1,2,3,4,5,6,7,8,9,100};
auto pos = find(vv.begin(),vv.end(),100);
vv.erase(pos);
//删除一个区间
vv.erase(vv.begin()+2,vv.end()-2);

2.43 随机访问operator[ ]

vector中最喜欢用的是[ ]

它支持随机访问,是否方便

operator[]的使用:

vector<int> vv{1,2,3,4,5,6,7,8,9};
for(int i=0;i<vv.size();i++)
{
  cout<<vv[i]<<" ";
}

3. vector的模拟实现

首先要关注的是成员变量

vector是顺序表,所以和实现C语言

时的顺序表一样,至少有三个参数

  1. 指向一段空间的指针
  2. 空间的有效大小
  3. 空间的实际大小

由于vector的迭代器就是普通指针

所以成员变量的类型其实是迭代器

template<class T>
class vector
{
public:
  typedef T* iterator;
private:
  iterator _start;
  iterator _finish;
  iterator _endof_storage;

这里使用迭代器作为三个参数的类型
是因为:求vector的size和capacity时
可以直接使用finish-start
也就是指针相减求出长度

成员变量和空间的关系:


3.1 vector容量相关函数

上来首先要考虑的容量相关的函数:

  • size
  • capacity
  • empty
  • resize
  • reverse

前三个十分简单:

size_t size() const
{
  return _finish - _start;
}
size_t capacity() const
{
  return _endof_storage - _finish;
}
bool empty() const
{
  return (size()==0);
}

3.11 reverse函数

reverse只会改变capacity的大小
并不会改变size的大小

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

注:当n小于capacity时,不进行扩容

由于C++内存管理的new
无法像C语言的realloc一样原地扩容
所以必须先开辟n个空间,再将数据
拷贝到新空间,且释放旧空间


3.12 resize函数

resize即会改变size大小
也会改变capacity大小

resize要分三种情况:

  1. n大于capacity时
  2. n大于size小于capacity时
  3. n小于size时

它们的解决方案分别是:

  • 直接套用reversezhu
  • 初始有效值不变,在此之后
    初始化新的内容
  • 直接将size缩小到n
void resize(size_t n, const T& val = T())
{
  if (n > capacity())
  {
    reserve(n);
  }
  if (n > size())
  {
    // 初始化填值
    while (_finish < _start + n)
    {
      *_finish = val;
      ++_finish;
    }
  }
  else
  {
    _finish = _start + n;
  }
}

注:参数val=T()使用了匿名对象

C++将内置类型特殊处理过

int/char等等都被升级为了类

所以可以使用int()表示匿名对象

int tmp1 = int();
int tmp2 = int(10);

int的缺省值为0


3.2 vector的构造函数

  1. 首先最简单的无参构造:
vector()
  :_start(nullptr)
  , _finish(nullptr)
  , _end_of_storage(nullptr)
{}
  1. 紧接着是带参的构造函数
    我们跟着STL库的风格走:
vector(size_t n, const T& val = T())
  :_start(nullptr)
  , _finish(nullptr)
  , _end_of_storage(nullptr)
{
  reserve(n);//开辟n个空间
  for (size_t i = 0; i < n; ++i)
  {
    push_back(val);//给初始值赋值
  }
}
  1. 最后是使用迭代器区间来构造
    比如我想在顺序表中存放string类型:
string str("abcdefg");
vector<string> vv(str.begin(),str.end());

此时在模板类中还应该有一个模板

template <class InputIterator>
vector(InputIterator first, InputIterator last)
  :_start(nullptr)
  , _finish(nullptr)
  , _end_of_storage(nullptr)
{
  while (first != last)
  {
    push_back(*first);
    ++first;
  }
}

注:inputiterator取名是模仿STL的
你也可以取任一除了T的名字


3.3 vector的析构函数

vector的析构函数非常简单

只需要将空间释放

并且将各个指针置为空就行了

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

3.4 vector的拷贝构造函数

拷贝构造的实现有很多种写法

大家可以先自己尝试一下

vector(const vector<T>& v)
  :_start(nullptr)
  , _finish(nullptr)
  , _endof_storage(nullptr)
  {
    reserve(v.size());
    for (const auto& e : v)
    {
      push_back(e);
    }
  }

4. 总结以及拓展

vector模拟实现的全部代码我将在

下一篇文章中分享给大家

可以发现:STL的神奇之处在于
它把所有接口函数都做了统一化处理
每一个容器的接口函数的使用都相似
但是内部实现被这种封装隐藏起来了
进一步又体现了C++的三大特性:
封装

并且C++实现了所有容器通用的算法库

比如sort和find都只需要传迭代器

然而所有容器都会被迭代器封装

所以一份代码就能实现对不同容器的操作

拓展题目:

熟悉了vector的基本使用

可以尝试解决一下下面几个问题:

留给大家当作小试牛刀了~


🔎 下期预告:迭代器失效和深浅拷贝问题 🔍


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