vector(2)

🕗 发布于 2024-10-10 18:52 java 开发语言 数据结构 c语言 算法

vector(2)

在这里插入图片描述

vector的使用

构造

代码如下：

vector<int> v1 = { 1,2,3,4,5,6 };//隐式类型转换
vector<int> v2({ 1,2,3,4,5,6 });//直接构造

依据如下：

在这里插入图片描述

类似于C语言中初始化数组：

int a[]={1,2,3,4,5,6};

对于a这个数组来说，空间大小是未知的，但是我们这里是拿后面的内容拷贝赋值到a这个数组里面

vector 空间增长问题

像动态开辟的空间，如果不满，不会从中间砍掉，举个例子：

在这里插入图片描述

这里面空间大小(capacity)为20,有效个数(size)为10，剩下的空间不会被砍掉，而是会重新开一块空间进行拷贝，也就是要进行缩容操作并不是本地缩容，而是异地缩容。

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2 倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本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倍方式扩容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
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';
}
}
}

vector 增删查改

insert:在position之前插入val

for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
//插入
v1.insert(v1.begin(), 9);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;

虽然vector不支持下标访问，但是可以间接访问：

v1.insert(v1.begin() + 2, 200);
for(auto e:v1)
{
cout << e << " ";
}
cout << endl;

同理，erase也是差不多的

//删除
v1.erase(v1.begin() + 2);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;

insert和erase不推荐多用，因为对程序的效率影响很大

operator[]:像数组一样访问

**at()**作用也是差不多，但是在处理异常的方式上不同，operator[]遇到越界是直接断言处理，at()会选择抛异常

稍微提一嘴，assign也就是赋值操作：
代码如下：

v1.assign=({10,20,30});

一道OJ题–只出现一次的数字

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

提示：

1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
除了某个元素只出现一次以外，其余每个元素均出现两次。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int value=0;
        for(auto e:nums)
        {
            value ^=e;
        }
        return value;
    }
};

一道OJ题–杨辉三角

给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

1 <= numRows <= 30

代码如下：

// 涉及resize / operator[]
// 核心思想：找出杨辉三角的规律，发现每一行头尾都是1，中间第[j]个数等于上一行[j-1]+[j]
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv(numRows,vector<int>());
        for(size_t i=0;i<numRows;++i)//开辟空间
        {
            vv[i].resize(i+1,1);
        }
        for(size_t i=0;i<vv.size();++i)
        {
            for(size_t j=1;j<vv[i].size()-1;++j)
            {
                vv[i][j]=vv[i-1][j]+vv[i-1][j-1];
            }
        }
        return vv;
    }
};

这里有一个重点核心：vector<vector < int> >

结论是这里相当于二维数组

二维数组的本质是一维数组

动态开辟空间的过程如下：

在这里插入图片描述

动态二维数组理解

// 以杨慧三角的前n行为例：假设n为5
void test2vector(size_t n)
{
// 使用vector定义二维数组vv，vv中的每个元素都是vector<int>
soobin::vector<soobin::vector<int>> vv(n);
// 将二维数组每一行中的vecotr<int>中的元素全部设置为1
for (size_t i = 0; i < n; ++i)
vv[i].resize(i + 1, 1);
// 给杨慧三角出第一列和对角线的所有元素赋值
for (int i = 2; i < n; ++i)
{
for (int j = 1; j < i; ++j)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
}

soobin: :vector<soobin: : vector< int >> vv(n); 构造一个vv动态二维数组，vv中总共有n个元素，每个元素都是vector类型的，每行没有包含任何元素

vector的模拟实现：

vector.h

#pragma once
#include <assert.h>
#include <string.h>
namespace soobin
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
vector(initializer_list<T> i1)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(il.size());
for (auto& e : i1)
{
push_back(e);
}
}
//private:
//iterator _start;
//iterator _finish;
//iterator _endofstorage;

iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
~vector()
{
if (_start)
{
delect[]_start;
_start = _finish = _endofstorage = nullptr;
}
}

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

size_t capacity() const
{
return _endofstorage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
size_t oldSize = size();//这里需要注意记录原先的size,因为被const修饰了不可以被修改，这样拿到的不是最新的
memcpy(tmp, _start, sizeof(T) * oldSize);
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 == _empty;
}
void pop_back()
{
assert(!empty());
--_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 : capacity() * 2);
pos = _start + len;
}
iterator i = _finish - 1;//这里是下标
while (i >= pos)
{
*(i + 1) = *i;
--i;
}
*pos = x;
++_finish;
}
void erase(iterator pos);
};
void test_vector1()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(4);
v1.push_back(4);

for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;

for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
vector<int>::iterator it1 = v1.begin();
while (it1 != v1.end())
{
cout << *it1 << " ";
}
cout << endl;
}

}

Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include "vector.h"
using namespace std;
void test_vector1()
{
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(), 9);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
v1.insert(v1.begin() + 2, 200);
for(auto e:v1)
{
cout << e << " ";
}
cout << endl;
//删除
v1.erase(v1.begin() + 2);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
soobin::test_vector1();
return 0;
}

这里需要来浅浅讨论一个迭代器失效的问题：
当我们用迭代器在指定位置插入数据的时候，可能会进行扩容操作，但是扩容操作可能pos指向的位置还是原先的位置，这样子在尾插的时候，会发生越界的情况

if (_finish == _endofstorage)
{
size_t len = pos - _start;//len用来记录pos和_start的距离
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//当遇到扩容的时候，加上这样的距离
}

在这里插入图片描述

原文地址：https://blog.csdn.net/Mr_Xuhhh/article/details/142825132

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【深度学习 | 基础部分】深度学习导论
下一篇：6. PH47 代码框架硬件开发环境搭建

Java入门：10.Java中的包
类似于OS中的文件夹。用来存放一组含义类似或相同的java类（接口），方便分类和管理。对应关系：java程序中的类 --- os中的.java文件java程序中的包 --- os中的文件夹如何指定包：
阅读更多2024-10-11
QD1-P14 HTML常用标签：input输入标签
本节学习 HTML 常用标签：input 输入标签
阅读更多2024-10-11
设计一个OAuth2认证系统：支持第三方登录的实用指南
OAuth2是一种授权框架，允许第三方应用在不暴露用户凭据的情况下访问用户的资源。资源拥有者（Resource Owner）：通常是用户，拥有受保护的资源。客户端（Client）：需要访问资源的应用程
阅读更多2024-10-11
脚本增加选项，解决问题
为了防止原始文件小于指定文件块大小，分割数量是0，默认数量+1, 导致分割文件数量不是最优，修改为通过可以判断指定大小和文件大小，执行分割。原因是拼接的输出文件后缀为(1)，文件系统会默认在文件名外层
阅读更多2024-10-11
【idea】切换多个仓库到一个分支
打开个一个Project 里面包含多个子项目，每一个子项目都有一个自己的git仓库。在idea 中有没有一次性把多个项目切换到同一个分支上面。OK 涉及到的项目已经全部切换到master 分支。
阅读更多2024-10-11
vscode插件
浏览器插件。
阅读更多2024-10-11
华为Eth-trunk链路聚合加入到E-trunk实现跨设备的链路聚合
你知道e-trunk与eth-trunk的区别吗？1、企业中有重要的server服务器业务不能中断的情况下，链路故障后，仍有可用的冗余链路，确保业务的延续性。2、企业中的重要业务，可通过将eth-tr
阅读更多2024-10-11
jenkins中的allure和email问题梳理
1.Allure Jenkins Plugin 只是一个集成插件，它要求你在 Jenkins 服务器上安装 Allure 命令行工具（Allure Commandline）来实际生成报告。需要需要邮箱
阅读更多2024-10-11
[红队apt]CHM电子书攻击/电子教程攻击
CHM文档攻击思路整理
阅读更多2024-10-11
推荐一个物联网平台，支持源代码交付
ThingsKit物联网平台以其强大的功能、简单的操作和高度的可定制性，为用户提供了一个快速实现物联网项目开发的平台。如果您正在寻找一个能够快速实现物联网项目开发的平台，那么ThingsKit将是您的
阅读更多2024-10-11

vector(2)

vector(2)

vector的使用

构造

vector 空间增长问题

vector 增删查改

一道OJ题–只出现一次的数字

一道OJ题–杨辉三角

vector的模拟实现：

相关文章