【C++详解】——vector类

news/2024/10/20 18:57:46/

📖 前言：本期介绍vector类。

目录

  • 🕒 1. vector的介绍
  • 🕒 2. vector的使用
    • 🕘 2.1 定义
    • 🕘 2.2 iterator
    • 🕘 2.3 空间增长
    • 🕘 2.4 增删查改
  • 🕒 2. vector的模拟实现
    • 🕘 2.1 构造函数
      • 🕤 2.1.1 无参构造
      • 🕤 2.1.2 拷贝构造
      • 🕤 2.1.3 构造并初始化n个val
    • 🕘 2.2 iterator
    • 🕘 2.3 空间增长
    • 🕘 2.4 增删查改
      • 🕤 2.4.1 insert
      • 🕤 2.4.2 erase
      • 🕤 2.4.3 swap
    • 🕘 2.5 其他
  • 🕒 3. 深拷贝问题
    • 🕘 3.1 vector<vector< int >>
    • 🕘 3.2 vector< string >
  • 🕒 4. 模拟实现vector汇总

🕒 1. vector的介绍

  1. vector是表示可变大小数组的序列容器（可以理解为顺序表）。
  2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
  3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
  4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
  5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
  6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

使用STL的三个境界：能用，明理，能扩展 ，那么下面学习vector，我们也是按照这个方法去学习。

🕒 2. vector的使用

🔎 vector文档介绍
对于vector内部的成员函数，基本上和string相同，因此本文章在模拟实现之前只介绍大多使用函数的函数名以及功能，具体细节会在模拟实现中解释。

🕘 2.1 定义

构造函数声明接口说明
vector()（重点）无参构造
vector（size_type n, const value_type& val = value_type()）构造并初始化n个val
vector (const vector& x)（重点）拷贝构造
vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造

🕘 2.2 iterator

iterator的使用接口说明
begin + end（重点）获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

在这里插入图片描述
这里会出现迭代器失效问题，如图我们发现迭代器可以看成指向某一数据的指针（实际上不一定是指针），但如果出现了扩容的情况（统一看成异地扩容）那么这个迭代器指向的位置就不再是我们想要进行操作的位置，这就是典型的迭代器失效问题，也就是野指针问题。具体介绍将会在下面的模拟实现中进行解释。

🕘 2.3 空间增长

容量空间接口说明
size获取数据个数
capacity获取容量大小
empty判断是否为空
resize（重点）改变vector的size
reserve （重点）改变vector的capacity
  • capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。
  • reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题（即可以直接将扩容一次性到位）。如果比当前容量小时，不缩容，因为缩容有代价，以空间换时间。
  • resize在开空间的同时还会进行初始化，影响size。
// 测试vector的默认扩容机制
void TestVectorExpand()
{size_t sz;vector<int> v;v.reserve(100);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';}}
}

🕘 2.4 增删查改

增删查改接口说明
push_back（重点）尾插
pop_back （重点）尾删
find查找（注意这个是算法模块实现，不是vector的成员接口）
insert在position之前插入val
erase删除position位置的数据
swap交换两个vector的数据空间
operator[] （重点）像数组一样访问

🕒 2. vector的模拟实现

首先定义一个vector类：

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}private: iterator _start; // 0iterator _finish; // sizeiterator _endofstorage; // capacity
};

🕘 2.1 构造函数

🕤 2.1.1 无参构造

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

🕤 2.1.2 拷贝构造

对于拷贝构造有两种写法：

  • 传统写法：开空间、赋值
  • 现代写法：通过迭代器的初始化构造
//传统写法 v2(v1)vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(v.capacity());for (const auto& e : v) // 必须&， 否则会拷贝构造调用拷贝构造，因为如果每一个元素(T)也都是vector，这就会导致拷贝构造调用拷贝构造{push_back(e);}}// 现代写法
template <class InputIterator>
vector(InputIterator first, InputIterator last) // 迭代器初始化:_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{while (first != last){push_back(*first);++first;}
}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{vector<T> tmp(v.begin(), v.end());swap(tmp); // this和tmp进行swap
}

🕤 2.1.3 构造并初始化n个val

vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n);for(size_t i = 0; i < n; i++){push_back(val);}
}

在测试的时候仅仅这样是会出错的，调试也印证了重载函数不会走上面函数，而是会走迭代器。原因为n是size_t而不是int类型，调用此函数就会发生隐式类型转换，编译器觉得不合适，便寻找更好的选择，于是找到了迭代器。解决方案就是再重载一个函数：vector(int n, const T& val = T())。为什么不直接将上一个函数的size_t改成int类型呢？因为我们是在模拟实现库中的vector。

🕘 2.2 iterator

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

🕘 2.3 空间增长

size_t size() const 
{return _finish - _start;
}size_t capacity() const
{return _endofstorage - _start;
}
bool empty() const
{return _finish == _start;
}void resize(size_t n, T val = T())//这里的val是缺省
{if (n > capacity()){reserve(n);}if (n > size()){while (_finish < _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}
}void reserve(size_t n) // 注意迭代器失效问题
{if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = tmp + oldSize;_endofstorage = _start + n;}
}

上面的reserve提到了迭代器失效问题，代码中已解决，即oldSize记录了size()的大小。那如果不记录size()的大小，那么_finish = tmp + size()中的size()由于之前的空间被销毁，也会被置为0,，此时的_finish就与_start就相同。

🕘 2.4 增删查改

这里需要注意迭代器失效问题，迭代器失效与扩容机制息息相关，而增删查改会频繁的调用扩容机制。

首先介绍不涉及迭代器失效的问题的成员函数：

void push_back(const T& x)
{if (_finish == _endofstorage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;++_finish;}
void pop_back()
{assert(!empty());--_finish;
}

下面看看需要考虑迭代器失效问题的成员函数

🕤 2.4.1 insert

// 迭代器失效问题：异地扩容导致的野指针问题
iterator insert(iterator pos, const T& val) // 不传引用是因为有左值的影响：常量，即v.begin()
{assert(pos >= _start);assert(pos < _finish);if (_finish == _endofstorage){size_t len = pos - _start; // 处理失效问题，记录相对位置size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);//扩容导致pos迭代器失效，需要更新处理一下pos = _start + len;}//挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;++_finish;return pos;
}

对于前插，是一定要考虑扩容问题的，而我们实现的方式也只有异地扩容，因此当我们触发了扩容机制后，就会引起迭代器失效的问题：

为了处理这个迭代器失效的问题，我们提前记录pos与_start的相对位置，即通过len = pos - _start记录，最后更新pos = _start + len，就可以解决这里迭代器失效的问题。

虽然函数内部的迭代器失效问题解决了，但我们知道，在这个函数中的pos只是外部pos的一份临时拷贝，改变这里的pos外部的pos并不会改变，因此外部的pos也会由于异地扩容之后导致野指针，那么我们可以采用返回值更新pos。

🕤 2.4.2 erase

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

🕤 2.4.3 swap

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}

🕘 2.5 其他

~vector()//析构
{delete[] _start;_start = _finish = _endofstorage = nullptr;
}// v1 = v2
// v1 = v1;  // 极少数情况，能保证正确性，所以这里就这样写没什么问题vector<T>& operator=(vector<T> v) // 由于直接swap，因此不能传引用
{swap(v);return *this;
}
void clear()
{_finish = _start; // 不能置空，会发现内存泄漏
}

🕒 3. 深拷贝问题

🕘 3.1 vector<vector< int >>

在这里插入图片描述
我们用上面模拟实现的代码进行观察

void test_vectorarray()
{vector<vector<int>> vv;vector<int> v(5, 1);vv.push_back(v);vv.push_back(v);vv.push_back(v);vv.push_back(v);for (size_t i = 0; i < vv.size(); i++){for (size_t j = 0; j < vv[i].size(); j++){cout << vv[i][j] << " ";}cout << endl;}cout << endl;
}

在这里插入图片描述

可以看到，插入四行是没问题的，那再插入一行（加上一个vv.push_back(v);）会怎么样呢

在这里插入图片描述
很明显，扩容出了问题，根据经验，大概率是异地扩容后出现了浅拷贝问题，即我们异地扩容产生的变量的指向仍然是之前指向的位置，并且由于异地扩容之后，会delete[]原空间，这就导致异地扩容的指向也变成了野指针。

在这里插入图片描述
当我们到了第五个push_back，也就是需要扩容的时候，我们发现：tmp与原本_start的位置指向的是同一个位置（注意外部的_start与内部的第一个_start指向的位置是一样的），这是由于memcpy引起的，而我们知道，memcpy所引起的异地扩容会释放旧空间，即释放旧位置所指向的位置，但这一释放，就导致了新开辟的tmp内部的指针变量指向的空间也被释放了。

既然浅拷贝的memcpy不行，那我们就可以通过赋值的方式在拷贝中开辟新空间，进行深拷贝：

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

即将reserve中的memcpy换成如图所示的方式，这样赋值拷贝会开辟新空间（上面的代码中就是开辟了新空间），我们就可以避免浅拷贝的问题。
在这里插入图片描述
因此我们也需要注意： 在C++中要避免使用C语言中的函数：memcpy、realloc、malloc等

🕘 3.2 vector< string >

事实上，string与vector<int>的道理是相同的，如果我们仍然用memcpy，会发现在需要扩容的过程中仍然出现浅拷贝造成的错误，用赋值就没有问题。由此可以理解，自定义类型的情况下都会发生这种扩容出现的问题，而内置类型并不会发生。

void test_vectorstring()
{vector<string> v;v.push_back("1111111111111");v.push_back("1111111111111");v.push_back("1111111111111");v.push_back("1111111111111");v.push_back("1111111111111"); // 扩容for (size_t i = 0; i < v.size(); i++){for (size_t j = 0; j < v[i].size(); j++){cout << v[i][j] << " ";}cout << endl;}cout << endl;
}

🕒 4. 模拟实现vector汇总

//myvector.h
#pragma oncenamespace myvector
{template<class T>class vector{public: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;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}//传统写法 v2(v1)//vector(const vector<T>& v)//	:_start(nullptr)//	, _finish(nullptr)//	, _endofstorage(nullptr)//{//	reserve(v.capacity());//	for (const auto& e : v) // 必须&， 否则会拷贝构造调用拷贝构造，因为如果每一个元素(T)也都是vector，这就会导致拷贝构造调用拷贝构造//	{//		push_back(e);//	}//}vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(n);for (int i = 0; i < n; ++i){push_back(val);}}vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}// 现代写法template <class InputIterator>vector(InputIterator first, InputIterator last) // 迭代器初始化:_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (first != last){push_back(*first);++first;}}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){vector<T> tmp(v.begin(), v.end());swap(tmp); // this和tmp进行swap}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}// v1 = v2// v1 = v1;  // 极少数情况，能保证正确性，所以这里就这样写没什么问题vector<T>& operator=(vector<T> v){swap(v);return *this;}void reserve(size_t n){if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T)*oldSize);for (size_t i = 0; i < oldSize; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = tmp + oldSize;_endofstorage = _start + n;}}void resize(size_t n, T val = T()){if (n > capacity()){reserve(n);}if (n > size()){while (_finish < _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}bool empty() const{return _finish == _start;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void push_back(const T& x){if (_finish == _endofstorage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;++_finish;}void pop_back(){assert(!empty());--_finish;}// 迭代器失效问题：异地扩容导致的野指针问题iterator insert(iterator pos, const T& val) // 不传引用是因为有左值的影响：常量，即v.begin(){assert(pos >= _start);assert(pos < _finish);if (_finish == _endofstorage){size_t len = pos - _start;// 处理失效问题，记录相对位置size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);// 扩容会导致pos迭代器失效，需要更新处理一下pos = _start + len;}// 挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *(begin);++begin;}--_finish;return pos;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}void clear(){_finish = _start;}private:iterator _start;iterator _finish;iterator _endofstorage;};
}

OK，以上就是本期知识点“vector类”的知识啦~~ ，感谢友友们的阅读。后续还会继续更新，欢迎持续关注哟📌~
💫如果有错误❌，欢迎批评指正呀👀~让我们一起相互进步🚀
🎉如果觉得收获满满，可以点点赞👍支持一下哟~

❗ 转载请注明出处
作者：HinsCoder
博客链接：🔎 作者博客主页


http://www.ppmy.cn/news/24004.html

相关文章

【linux】线程概念

【linux】线程概念

概念 什么是线程 在一个程序里的一个执行路线就叫做线程&#xff08;thread&#xff09;。更准确的定义是&#xff1a;线程是“一个进程内部的控制序列” 一切进程至少都有一个执行线程&#xff0c;线程在进程内部运行&#xff0c;本质是在进程地址空间内运行 在Linux系统中&a…
阅读更多...
【大数据Hadoop】Hadoop 3.x 新特性总览

【大数据Hadoop】Hadoop 3.x 新特性总览

Hadoop 3.x 新特性剖析系列11. 概述2. 内容2.1 JDK2.2 EC技术2.3 YARN的时间线V.2服务2.3.1 伸缩性2.3.2 可用性2.3.3 架构体系2.4 优化Hadoop Shell脚本2.5 重构Hadoop Client Jar包2.6 支持等待容器和分布式调度2.7 支持多个NameNode节点2.8 默认的服务端口被修改2.9 支持文件…
阅读更多...
实战打靶集锦-004-My-Cmsms

实战打靶集锦-004-My-Cmsms

**写在前面&#xff1a;**记录一次艰难曲折的打靶经历。 目录1. 主机发现2. 端口扫描3. 服务枚举4. 服务探查4.1 WEB服务探查4.1.1 浏览器访问4.1.2 目录枚举4.1.3 控制台探查4.1.4 其他目录探查4.2 阶段小结5. 公共EXP搜索5.1 CMS搜索5.2 Apache搜索5.3 PHP搜索5.4 MySQL搜索5…
阅读更多...
福利篇1——嵌入式软件行业与公司汇总

福利篇1——嵌入式软件行业与公司汇总

前言 汇总嵌入式软件行业与公司，供参考。 文章目录 前言一、嵌入式软件行业和公司汇总1、芯片行业代表性公司2、人工智能代表性公司1）智能驾驶方向代表性公司2）机器人方向代表性公司3、消费电子领域代表性公司4、传统电子电器领域代表性公司5、国企和军工领域代表性公司6、网…
阅读更多...
js中的自调用表达式

js中的自调用表达式

自调用表达式 由函数表达式创建的函数可以自调用&#xff0c;称之为自调用表达式。 语法 由函数表达式创建函数: const myFn function () {let a 100console.log(a);return a } myFn() //调用后执行&#xff0c;输出100表达式后面紧跟 ( ) 则会自动调用: const myFn fu…
阅读更多...
获取成员userID

获取成员userID

文章目录一、简介二、获取token1、获取秘钥2、获取Token三、获取部门数据1、获取部门列表2、获取子部门ID列表3、获取单个部门详情四、获取成员信息1、读取成员2、获取部门成员3、获取部门成员详情一、简介 同步数据到企微&#xff1a; 企业如果需要从自有的系统同步通讯录到…
阅读更多...
【机器学习】聚类算法（理论）

【机器学习】聚类算法（理论）

聚类算法&#xff08;理论&#xff09; 目录一、概论1、聚类算法的分类2、欧氏空间的引入二、K-Means算法1、算法思路2、算法总结三、DBSCAN算法1、相关概念2、算法思路3、算法总结四、实战部分一、概论 聚类分析&#xff0c;即聚类&#xff08;Clustering&#xff09;&#xf…
阅读更多...
悲观锁、乐观锁以及分布式锁

悲观锁、乐观锁以及分布式锁

1.单机应用乐观锁悲观锁&#xff0c;select 时怎么加排它锁?1.1悲观锁&#xff08;Pessimistic Lock&#xff09;:悲观锁特点:先获取锁&#xff0c;再进行业务操作。即“悲观”的认为获取锁是非常有可能失败的&#xff0c;因此要先确保获取锁成功再进行业务操作。通常所说的“…
阅读更多...
最新文章

Copyright @ 2022~2023