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

vector(2)

news 2025/1/15 12:52:25

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;//当遇到扩容的时候，加上这样的距离}

在这里插入图片描述