当前位置： 首页 > java >正文

vector【上】

java 2025/7/25 19:40:04

一、vector的介绍及使用

1.1 vector的介绍

vector - C++ Reference

使用STL的三个境界：能用、明理、能扩展 ， 下面也是按照这样的原理来学习vector的 ！

1.2 vector的使用

vector 学习的时候一定要学会查看文档 vector - C++ Reference ， vector在实际中非常重要 ，下面介绍一些常用的接口 ， 需要重点掌握 。

1.2.1 vector的定义

1.2.2 vector iterator 的使用 

#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<iostream>
using namespace std;int main()
{vector<int> v1;vector<int> v2(10, 1);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);//遍历//下标 + [ ]for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;//迭代器vector<int>::iterator it1 = v1.begin();while (it1 != v1.end()){cout << *it1 << " ";it1++;}cout << endl;//范围forfor (auto ch : v1){cout << ch << " ";}cout << endl;return 0;
}

 

1.2.3 vector 空间增长问题

 

 

  • capacity 的代码在 vs 和 g++ 下分别运行会发现 ，vs 下capacity 是按 1.5倍增长的 ，g++ 是按 2倍增长的 。这个问题经常会考察 ，不要固化的认为 ， vector 增容都是 2 倍，具体增长多少是根据具体的需求定义的 。 vs是PJ版本的STL ， g++是SGL版本的STL。
  • reserve只负责开辟空间 ，如果确定知道需要用多少空间 ， reserve 可以缓解 vector增容代价缺陷问题。
  • resize 在开空间的同时还会进行初始化 ， 影响size 。
// 测试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：运行结果：vs下使用的STL基本是按照 1.5 倍方式扩容：

g++运行结果：linux下使用的STL基本是按照2倍方式扩容： 

making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128
// 如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{
vector<int> v;
size_t sz = v.capacity();
v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容
cout << "making bar 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';
}
}
}

 

1.2.4 vector 增删查改

1) operator[ ] 和 at 的区别 ：  

2）insert : 

void test_vector2()
{vector<int> v1 = { 1,2,3,4,5,6 };vector<int> v2({ 1,2,3,4,5,6 });for (auto e : v1){cout << e << " ";}cout << endl;v1.insert(v1.begin(), 500);for (auto e : v1){cout << e << " ";}cout << endl;v1.insert(v1.begin() + 3, 800);for (auto e : v1){cout << e << " ";}cout << endl;
}

 

3)erase :

	v1.erase(v1.begin()+2);for (auto e : v1){cout << e << " ";}cout << endl;v1.erase(v1.begin() + 3,v1.end()-2);for (auto e : v1){cout << e << " ";}cout << endl;

注意：不太建议频繁使用 insert 和 erase  ， 因为需要挪动数据 ， 代价会比较高 。

二、vector底层

这里我们和string 不同 ， 就不建立 vector.cpp文件了 ， 因为模板不支持分离成两个文件 ， 因为编译的时候会报链接错误 ， 后续会介绍

2.1 reserve

解决方法：用oldSize先把之前size() 存储起来 ！ 

		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);delete[] _start;}_start = tmp;_finish = _start + oldSize;_endofstorage = _start + n;}}

 

2.2 迭代器失效

迭代器的主要作用就是让算法能够不用关心底层数据结构 ， 其底层实际就是一个指针 ， 或者是对指针进行了封装 。 比如 ： vector 的迭代器就是原生态指针T* 。 因此迭代器失效 ， 实际就是迭代器底层对应指针所指向的空间被销毁了 ， 而使用一块已经被释放的空间 ， 造成的后果是程序崩溃 。（即如果继续使用已经失效的迭代器，程序可能会崩溃）。

迭代器失效解决办法：在使用前，对迭代器重新赋值即可

 对于vectoc 可能会导致其迭代器失效的操作有：

扩容引起的野指针

1. 会引起其底层空间改变的操作 ， 都可能使迭代器失效 。 比如 ： resize 、 reserve 、 insert 、assign 、 push_back等 。

我们可以看到在 insert() ，下面的代码没有办法得到正确的结果，原因是 pos 在扩容的时候就已经被释放了，目前是野指针。

	void insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : 2 * capacity());}iterator i = _finish - 1;while (i >= pos){*(i + 1) = *(i);i--;}*pos = x;++_finish;}

修改:

void insert(iterator pos, const T& x)
{assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator i = _finish - 1;while (i >= pos){*(i + 1) = *(i);i--;}*pos = x;++_finish;
}

下面的迭代器  it 为什么失效?

 因为 it 作为实参传给形参 ， 形参的改变不影响实参 ；所以 it 迭代器失效 。 同时 ， 在insert 第一个参数加引用也不能解决这个问题 ， 

 但是，我就是想要访问这个 pos 的迭代器 ，怎么办？

库里给我们提供了对应的函数 ， 

		//迭代器失效：iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator i = _finish - 1;while (i >= pos){*(i + 1) = *(i);i--;}*pos = x;++_finish;return pos;}

 

删除数据导致数据挪动

2. erase 删除 pos 位置元素后 ， pos 位置之后的元素会往前搬挪 ， 没有导致底层空间的改变 ， 理论上讲迭代器不应该会失效 。 但是 ， 如果 pos刚好是最后一个元素 ， 删完之后 pos刚好是 end的位置 ， 而 end 位置是没有元素的 ， 那么 pos就失效了 。 因此删除 vector位置上元素时 ， vs 就认为该位置迭代器失效了 。 

vs强制检查，失效的迭代器不让你访问，如果想要访问，也要更新！

#include<iostream>
using namespace std;
#include <vector>
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据，导致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此处会导致非法访问return 0;
}
		iterator erase(iterator pos){assert(pos >= _start && pos <= _finish);iterator i = pos + 1;while (i < _finish){*(i - 1) = *i;i++;}--_finish;return pos;}

以下代码的功能是删除vector中所有的偶数，请问那个代码是正确的，为什么？ 

#include <iostream>
using namespace std;
#include <vector>
int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}return 0;
}int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);else++it;}return 0;
}

第二个是正确的 ， 因为删除数据 ， 导致数据的挪动 ，  it 已经不是指向之前的位置 ， 可能会导致逻辑问题，VS下会强制检查 ， 失效的迭代器不让你访问 ， 要访问也要更新！

2.3 resize

在给resize() 参数缺省值的时候 ， 我们要考虑到 T 的类型可以为 int , string 等等 ， 所以不能给确切类型的数据 。 C++对内置类型进行了升级，支持默认构造 ，所以缺省值给T() 。 

		void resize(size_t n, T val = T()){if (n <= size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;_finish++;}}}
	void test_vector4(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.resize(10);for (auto e : v1){cout << e << " ";}cout << endl;v1.resize(15,1);for (auto e : v1){cout << e << " ";}cout << endl;}

2.4 拷贝构造

可以先用reserce预开空间 ， 减少频繁扩容 导致的效率降低。

	//v2(v1)vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}

2.5 赋值重载

借用swap , 来简化赋值重载的写法。

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

 

2.6 迭代器构造

类模板的成员函数 ， 也可以是一个函数模板 （可以传任意类型的迭代区间） 

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

2.7 n 个 val构造

	//n个valvector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

此时出现报错 ， 因为我们再次之前实现的迭代器构造 ， 当传 vector<int>v1(10,1) 的时候 ，

所以解决方法就是 ， 另写一个 n 个 val 的构造 ， 但是此时明确类型为 int 

		//n个valvector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}

 

2.8 更深层次的拷贝构造导致的问题

	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);delete[] _start;}_start = tmp;_finish = _start + oldSize;_endofstorage = _start + n;}}

我们可以发现，在 push_back() 4个数据时候没有出现什么问题 ， 但是 ， 多 push_back 一个数值的时候 ， 则出现了问题 。

 原因其实是因为 memcpy 的时候 ， 数组中的string 对象是浅拷贝 。 delete[ ] _start 的时候调用析构 释放资源 ， 所以再次访问 tmp 的时候 ， 所指向的资源已经被释放了  。 

2.9 总代码

vector.h

#pragma once
#include<assert.h>
#include<iostream>
using namespace std;
namespace LF
{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;}vector(){}//类模板的成员函数，也可以是一个函数模板template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//n个valvector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}vector(initializer_list<T> i1){reserve(i1.size());for (auto& e : i1){push_back(e);}}//v2(v1)vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}void swap(vector<T>& tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_endofstorage, tmp._endofstorage);}//v1 = v3vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void resize(size_t n, T val = T()){if (n <= size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;_finish++;}}}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 = _start + oldSize;_endofstorage = _start + n;}}void push_back(const T& x){if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}bool empty(){return _start == _finish;}void pop_back(){assert(!empty());--_finish;}//迭代器失效：iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator i = _finish - 1;while (i >= pos){*(i + 1) = *(i);i--;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos <= _finish);iterator i = pos + 1;while (i < _finish){*(i - 1) = *i;i++;}--_finish;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};void test_vector1(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;vector<int>::iterator it1 = v1.begin();while (it1 != v1.end()){cout << *it1 << " ";it1++;}cout << endl;for (auto e : v1){cout << e << " ";}cout << endl;v1.pop_back();for (auto e : v1){cout << e << " ";}cout << endl;}void TestVectorExpand(){size_t sz;vector<int> v;cout << typeid(vector<int>::iterator).name() << endl;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';}}}void test_vector2(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);//v1.insert(v1.begin() + 2, 30);for (auto e : v1){cout << e << " ";}cout << endl;int x;cin >> x;auto it = find(v1.begin(), v1.end(), x);if (it != v1.end()){it = v1.insert(it, 10 * x);cout << *it << endl;}for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector3(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;int x;cin >> x;auto it = find(v1.begin(), v1.end(), x);if (it != v1.end()){//it 是否失效？失效，不能访问v1.erase(it);cout << *it << endl;}for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector4(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.resize(10);for (auto e : v1){cout << e << " ";}cout << endl;v1.resize(15,1);for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector5(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;vector<int> v2(v1);for (auto e : v2){cout << e << " ";}cout << endl;vector<int> v3 = { 10,20,30,40 };v1 = v3;for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector6(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);vector<int> v2(v1.begin(), v1.end());for (auto e : v2){cout << e << " ";}cout << endl;vector<int> v3(10, 1);for (auto e : v3){cout << e << " ";}cout << endl;}void test_vector7(){vector<string> v1;v1.push_back("1111111111111");v1.push_back("1111111111111");v1.push_back("1111111111111");v1.push_back("1111111111111");v1.push_back("1111111111111");v1.push_back("1111111111111");for (auto e : v1){cout << e << " ";}cout << endl;}
}

http://www.xdnf.cn/news/16095.html

相关文章：

  • 大模型就业方向
  • Log4j CVE-2021-44228 漏洞复现详细教程
  • 【lucene】实现knn
  • Git 完全手册：从入门到团队协作实战（4）
  • DP系列2【01背包】洛谷 P1049 [NOIP 2001 普及组] 装箱问题题解
  • 构建高性能推荐系统：MixerService架构解析与核心实现
  • K8s:离线部署Kubernetes1.26.12及采用外部Harbor
  • .net core接收对方传递的body体里的json并反序列化
  • P5535 【XR-3】小道消息
  • 【MyBatis-Plus】核心开发指南：高效CRUD与进阶实践
  • 83、设置有人DTU设备USR-M100采集传感器数据，然后上传阿里云服务
  • 【音视频学习】五、深入解析视频技术中的像素格式：颜色空间、位深度、存储布局
  • CodeBuddy IDE实战：用AI全栈能力快速搭建课程表网页
  • 借助Aspose.HTML控件，使用 Python 编程将网页转换为 PDF
  • Object Sense (OSE)：一款从编辑器脚本发展起来的编程语言
  • 优化：Toc小程序猜你喜欢功能
  • Java 堆（优先级队列）
  • AI 及开发领域动态与资源汇总(2025年7月23日)
  • 编程语言Java——核心技术篇（二）类的高级特性
  • 逆向入门（41）程序逆向篇-crackme
  • OceanBase数据库
  • 设备虚拟化技术
  • 从零开始学习Dify-Excel数据可视化(四)
  • Rocky9部署Zabbix7（小白的“升级打怪”成长之路）
  • 【bug】websocket协议不兼容导致的一个奇怪问题
  • （46）elasticsearch-华为云CCE无状态负载部署
  • #Linux内存管理# 在一个播放系统中同时打开几十个不同的高清视频文件，发现播放有些卡顿，打开视频文件是用mmap函数，请简单分析原因。
  • MCU芯片AS32S601在卫星光纤放大器（EDFA）中的应用探索
  • VPS海外部署Linux分布式计算任务调度-跨国资源整合方案
  • k8s:docker compose离线部署haborV2.13.1及采用外部的postgresql及redis数据库