【C++】vector使用 & 经典题型讲解

🌈欢迎来到C++专栏~~vector


  • (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort🎓
  • 🌍博客主页:张小姐的猫~江湖背景
  • 快上车🚘,握好方向盘跟我有一起打天下嘞!
  • 送给自己的一句鸡汤🤔:
  • 🔥真正的大师永远怀着一颗学徒的心
  • 作者水平很有限,如果发现错误,可在评论区指正,感谢🙏
  • 🎉🎉欢迎持续关注!
    请添加图片描述

请添加图片描述

iOS Unlocker

WebRTC

vector使用 & 经典题型讲解

cglib静态代理

请添加图片描述

Lambda表达式

由于前面重点讲解了string类,所以vector的学习成本很低,本文只对重点作出讲解,必要的话还得是查文档

cpu

Vector是表示可以改变大小的数组的序列容器
在这里插入图片描述

游戏开发

一. 构造和析构

💦构造函数

构造函数声明 接口说明
vector() 重点 无参构造
vector(const vector& x) 重点 拷贝构造
vector (size_type n, const value_type& val = value_type()) 构造并初始化n个val(value_type即T)
vector (InputIterator first, InputIterator last) 用迭代器区间初始化

胡不多说,测试:

fpga开发

vector<int> v1;//无参构造
vector<int> v2(10, 1);//构造10个val,初始化为1
vector<int> v3(v2);//拷贝构造
vector<int> v3(++v2.begin(), --v2.end()); //迭代器区间初始化

那vector可以代替string吗?不可以!因为有'\0',在操作上+=find<<>>,因为vector是针对T 泛型,一般针对其他类型(int、double),所以vector无法替代string

数模学习

💦析构函数

还是老规矩,不用管,系统自己会调用

操作系统

二. 遍历

⚡operator[]

在这里插入图片描述

jenkins

//下标+[]      可读可写
for (size_t i = 0; i < v1.size(); ++i)
{
	v1[i]++;
	cout << v1[i] << endl;
}

在这里插入图片描述

EIP

⚡迭代器 & 范围for

✨ iterator 内嵌类型

yolov5 deepsort

iterator的使用 接口说明
begin + end(重点) 获取第一个数据位置的, 获取最后一个数据下一个位置
rbegin + rend 获取最后一个数据位置,获取第一个数据前一个位置

在这里插入图片描述

IC验证

    // 遍历 - 可读可写
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		(*it) --;
		cout << *it << " ";
		it++;
	}
	cout << endl;

在这里插入图片描述

IaaS

支持迭代器就支持范围for🍬(底层就是迭代器)

apk

		//范围for
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

三.增删查改

🌈reserve & resize

容量空间 说明
reserve 改变vector的capacity
resize 扩容+初始化 / 删除数据(capacity不变动,改变size)
  • resize初始化可以自己指定值

测试vector的默认扩容机制

python ipidea

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	size_t sz;
	vector<int> foo;
	sz = foo.capacity();
	cout << "making foo grow:\n";
	for (int i = 0; i<100; ++i) 
	{
		foo.push_back(i);
		if (sz != foo.capacity()) 
		{
			sz = foo.capacity();
			std::cout << "capacity changed: " << sz << '\n';
		}
	}
}

vs:运行结果:vs下使用的STL基本是按照1.5倍方式扩容
在这里插入图片描述

开发环境

g++以标准的2倍增长 ——

精通Linux系列

在这里插入图片描述

AlexNet

🌈push_back & pop_back

尾插尾删,不多赘述了

jdk

	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

🌈find

vector类中并没有find,这是因为算法库中就提供了一个模板函数,在迭代器区间中查找(左闭右开),若查找到了,就返回迭代器;没找到就返回s.end()

layui

在这里插入图片描述

分组

	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);

	vector<int>::iterator pos = find(v1.begin(), v1.end(), 3);
	if (pos != v1.end())
	{
     	cout << "找到了!" << *pos << endl;
	}

🌈insert & erase

可头插头删

优化

修改 说明
insert 在position(迭代器)之前插入val
erase 删除position(迭代器)位置的数据

insert & erase 可以搭配 find 使用。string类的insert和erase通常支持下标,因为它find也刚好返回下标

vue3.0

	    // 头插
	    v.insert(v.begin(), 0);

		vector<int>::iterator pos = find(v1.begin(), v1.end(), 3);
		if (pos != v1.end())
		{
			v1.insert(pos, 30);
		}
		
		pos = find(v1.begin(), v1.end(), 3);
		if (pos != v1.end())
		{
			v1.erase(pos);
		}

注意vector没有重载流提取和流插入<<>>,遍历有迭代器[],所以就不需要了

Spring中的bean使用

四. 排序

函数模板排序,对迭代器区间进行排序,默认是升序

协议

在这里插入图片描述

压力测试

		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(10);
		v1.push_back(4);

		sort(v1.begin(), v1.end());

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

那我们想实现降序这么办呢? 仿函数(后面栈细细分说),现在先会用

在线聊天

		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(10);
		v1.push_back(4);

		sort(v1.begin(), v1.end());

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		less<int> ls;//升序
		greater<int> gt;//降序

		sort(v1.begin(), v1.end(), greater<int>());//匿名对象~ 传参

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

在这里插入图片描述
不仅仅可以排vector,string也能排(按照ascll码排序

android版本适配

在这里插入图片描述

MDK编译过程

五. 小细节

在这里插入图片描述

举例:

vcctor<string> strV;

string str1("张三");
strV.push_back(str1);
strV.push_back(string("李四"));
strV.push_back("王五");//这个为什么能实现呢??
答:会构造一个临时对象,然后被引用

因为构造函数是一个单参数,支持隐式类型转换

string(const char* str)//构造函数
{}

如果要使用范围for的时候,要谨慎小心 再小心

for(const auto& str:: strV)
{
    cout<<str<<endl;
}

此处会被替换成迭代器,迭代器会依次取数据去赋值,如果不加引用就是就会调用拷贝构造,此时还是深拷贝,如果多次赋值就会浪费很多空间,所以要加&引用,拷贝别名,更加高效

经典题型讲解

0️⃣易错课后题

下面这个代码输出的是( C )

#include <iostream>       
#include <vector>
using namespace std;
int main(void)
{
	vector<int>array;
	array.push_back(100);
	array.push_back(300);
	array.push_back(300);
	array.push_back(300);
	array.push_back(300);
	array.push_back(500);
	vector<int>::iterator itor;
	for(itor=array.begin();itor!=array.end();itor++)
	{
		if(*itor==300)
		{
			itor=array.erase(itor);
		}
	}
	for(itor=array.begin();itor!=array.end();itor++)
	{
			cout<<*itor<<"";
	}
  return 0;
}

A.100 300 300 300 300 500
B.100 3OO 300 300 500
C.100 300 300 500
D.100 300 500
E.100 500
F.程序错误

解析:

vector::erase():从指定容器删除指定位置的元素或某段范围内的元素 vector::erase()方法有两种重载形式 如下:
iterator erase( iterator _Where); iterator erase( iterator _First,iterator _Last);
如果是删除指定位置的元素时: 返回值是一个迭代器,指向删除元素下一个元素;
如果是删除某范围内的元素时:返回值也表示一个迭代器,指向最后一个删除元素的下一个元素;
在本题中,当 itor==300成立时,删除第一个值为300的元素,同时itor指向下一个元素(即是第二个值为300的元素);在for(;;itor++)执行itor,itor指向第三个值为300的元素,进入下一个循环。
所以整个过程中,只删除了2个值为300的元素

💛T是一个数据类型,关于std::vector::at 和 std::vector::operator[] 描述正确的是( C )

A.at总是做边界检查, operator[] 不做边界检查.
B.at 不做边界检查, operator[] 做边界检查.
C.at和operator[] 都是会做边界检查的
D.以上都不对

at() 函数和 [] 运算符的重载,两者都可以得到相应下标的值,并且两者都会去做边界检查。当发生越界行为时,at抛异常operator[]报出 assert 错误

1️⃣只出现一次的数字(单身狗)

题目链接:136. 只出现一次的数字

著名的单身狗问题,异或解法最经典:相同为0, 不同为1

在这里插入图片描述

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

2️⃣只出现一次的数字ii(进阶)

题目链接:137. 只出现一次的数字 II

巧妙的思路:如下图所示,考虑数字的二进制形式,对于出现三次的数字,各 二进制位 出现的次数都是 3 的倍数
因此,统计所有数字的各二进制位中 1 的出现次数,并对 3 求余,结果则为只出现一次的数字

在这里插入图片描述

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret =0;
        size_t sum =0;//统计个数
        for(size_t i = 0; i< 32 ;++i)
        {
            sum = 0;
            for(auto& ch : nums)
            {
                sum += (ch>>i)&1;
            }
            sum %=3;
            ret += (sum<<i);
        }
        return ret;
    }
};

3️⃣只出现一次的数字iii(两只单身狗)

题目链接:260. 只出现一次的数字 III

著名的两只单身狗的故事

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        //全员异或
        int ret =0;
        for(auto e: nums)
        {
            ret ^= e;
        }

        //找到两个单身狗数字不同的一位(二进制)
        size_t pos = 0;
        while(pos < 32)
        {
            if((ret >> pos)&1 == 1 )
                break;
            pos++;
        }

        //分组异或
        vector<int> retArr(2);
        for(size_t i=0;i<nums.size();++i)
        {
            if((nums[i] >> pos)&1 == 1)
            {
                retArr[0] ^= nums[i];
            }
            else
            {
                retArr[1] ^= nums[i];
            }
        }
        return retArr;
    }
};

4️⃣删除有序数组中的重复项

题目链接:26. 删除有序数组中的重复项

解题思路:双指针移动,fast指针遍历,fast!=slow时候,fast赋值给++slow,不断遍历,最后返回长度。

在这里插入图片描述

ps:返回是要求长度,slow+1,不加就漏了最开始的那个数据

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //慢指针、快指针
        int slow = 0, fast =0;
        while(fast < nums.size())
        {
            if(nums[slow] == nums[fast])
            {
                ++fast;
            }  
            else
            {
                nums[++slow] = nums[fast++];
            }
        }
      return slow + 1;
    }
};

5️⃣杨辉三角OJ

题目链接:118. 杨辉三角
用c语言做相当的麻烦,要动态开辟二维数组,所以我们学了vector之后就简单多了

在这里插入图片描述
vv[i][j]本质上是两次的[]函数调用~

💗核心思想:找出杨辉三角的规律,发现每一行头尾都是1,中间第[j]个数等于上一行[j-1]+[j]

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);
        //初始化
        for(size_t i = 0; i < vv.size() ; ++i)
        {
            vv[i].resize(i + 1, 0);
            vv[i].front() = vv[i].back() = 1;
        }
        //遍历
        for(size_t i =0; i< vv.size() ; ++i)
        {
            for(size_t j = 0; j <vv[i].size(); ++j)
            {
                if(vv[i][j] == 0)
                {
                    vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
                }
            }
        }
        return vv;
    }
};

6️⃣电话号码组合(中等)

题目链接:17. 电话号码的字母组合

本题是一道多路递归的深度遍历,简单的映射&回溯 ,递归深度取决于数字串长度,数字串映射多长就是,几路递归!!

在这里插入图片描述

class Solution {
    //单参数构造
    char* numTok[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    void Combine(string digits, int di, vector<string>& retV, string combineStr)
    {
        if(di == digits.size())
        {
            retV.push_back(combineStr);
            return ;
        }
             
        //先取数字字符映射的字符串
        int num = digits[di] - '0';
        string str = numTok[num];
        for(auto ch: str)
        {
            Combine(digits, di+1, retV, combineStr + ch);
        }
    }

    vector<string> letterCombinations(string digits) {
        vector<string> v;
        if(digits.empty())
            return v;
        string str;
        Combine(digits, 0, v , str);

        return v;
    }
};

ps:

  • 建立映射的时候,不需要用vector,因为是固定长度,并且可以想string("abc")那样初始化,因为支持隐式类型转化

思路不清晰的可以自己画画递归展开图:

在这里插入图片描述

📢写在最后

慢慢要开始笔试强化了,每天坚持写完并且博客输出易错知识点

在这里插入图片描述

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注