作者简介: 一个在后端领域学习、渴望学习一些东西的追梦者。
个人主页:不好
系列专栏:C++ Linux
学习格言:海纳百川,厚积薄发
欢迎朋友们,如果您在学习过程中发现需要纠正的地方,请指正,希望与您共同成长!
文章目录
知道
它是一个类模板,可以根据不同的模板参数实例化存储不同数据的类。 类可用于管理数组。 与类不同的是,它们只能管理char类型的数组,但可以管理任何类型的数组。 类相当于一个动态增长的序列表。
类模板中有两个参数:第一个是数据类型,第二个是空间配置器。
1. 是表示可变大小数组的序列容器。
2、就像数组一样,也是使用连续的存储空间来存储元素,也就是说可以使用下标对的元素来访问,与数组一样高效。
3.与普通数组不同的是,数组的大小是可以动态改变的,它的大小会由容器自动处理。
4、空间分配策略:会分配一些额外的空间来容纳可能的增长,因此存储空间大于实际需要的存储空间。不同的库使用不同的
该策略权衡空间使用和重新分配。 但无论如何,重新分配后,必须保证在末尾插入一个元素时,是在常数时间复杂度内完成的。因为
因此,会占用更多的存储空间,以高效的方式动态增长,以获得管理存储空间的能力。
5、与其他动态序列容器(deque、list和)相比,访问元素时效率更高,末尾添加和删除元素效率相对较高。
对于其他不在末尾的删除和插入操作效率较低。
常用接口的构造函数()构造函数声明接口描述
()
无参数构造
( n、常量 & val = ())
构造并初始化 n 个 val
(常量 & x)
复制构造
(第一个,最后一个)
使用迭代器初始化构造
(第一个、最后一个)构造函数使用迭代器间隔进行初始化。 这里调用的是迭代器。 根据性质,迭代器可分为单向迭代器、双向迭代器和随机迭代器; 其中的迭代器是随机迭代器。 设备。
单向迭代器相当于单向链表,只能读取下一个节点而不能读取上一个节点; 双向迭代器相当于双向链表,既可以读取下一个节点,也可以读取上一个节点; 随机迭代器和双向迭代器具有相同的性质。
这里我们只需要知道任何类型的迭代器都可以传递,因为这是一个模板,只要类型匹配就可以传递,类的迭代器也可以传递,其他类也可以传递。
构造函数的用法:
//构造一个int类型的空容器
vector<int> v1;//调用无参构造函数
for (auto e : v1)
{
cout << e;
}
//空
cout << endl;
//构造一个含有n个val的int容器
vector<int> v2(10, 2);
for (auto e : v2)
{
cout << e;
}
//输出2222222222
cout << endl;
//拷贝构造
vector<int> v3(v2);
for (auto e : v3)
{
cout << e;
}
//输出2222222222
cout << endl;
//使用迭代器进行拷贝构造
vector<int> v4(v2.begin(), v2.end());
for (auto e : v4)
{
cout << e;
}
//输出2222222222
cout << endl;
//也可以使用迭代器区间构造函数将string类对象中内容初始化构造
string s1("hello");
vector<char> v5(s1.begin(), s1.end());
for (auto e : v5)
{
cout << e;
}
//输出hello
cout << endl;
扩大:
可以更换吗?
不,差别还是蛮大的。
迭代器函数函数接口说明
开始+结束
获取第一个数据位置的 /,获取最后一个数据的下一个位置的 /
+撕裂
获取最后一个数据位置,获取第一个数据的前一个位置
中的迭代器和类中的迭代器最初指向相同的位置和遍历方向:
开始()+结束()函数
我们可以使用迭代器迭代数组元素:
begin() + end()函数遍历:
#include
#include
using namespace std;
int main()
{
vector<int> v1(10,6);
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << (*it);
it++;
}
//输出6666666666
cout << endl;
return 0;
}
()+rend() 函数
() + rend() 函数遍历:
#include
#include
using namespace std;
int main()
{
vector<int> v1(10,6);
vector<int>::reverse_iterator rit = v1.rbegin();
while (rit != v1.end())
{
cout << (*rit);
rit++;
}
//输出6666666666
cout << endl;
return 0;
}
容量与空间增长功能界面说明
尺寸
获取有效数据条数
获得容量
空的
判断是否为空
改变尺寸
改变了
尺寸函数
#include
#include
using namespace std;
int main()
{
vector<int> v1(10,6);
cout << v1.size() << endl;//10
}
功能
#include
#include
using namespace std;
int main()
{
vector<int> v1(10,6);
cout << v1.capacity() << endl;//10
}
空函数
#include
#include
using namespace std;
int main()
{
vector<int> v1(10,6);
cout << v1.empty() << endl;//0
}
功能
规则:
1.当给定的值大于容器当前的大小时,大小将扩展到该值。 如果不指定第二个参数,则扩展后的数据元素的值默认为0,也默认扩展为当前值。
2.当给定的值小于容器当前的大小时,大小将减小到该值,而不影响该值。
#include
#include
using namespace std;
int main()
{
vector<int> v1(10,6);
cout << v1.size() << endl;//未改变size大小之前的size值为10
cout << v1.capacity() << endl;//capacity值为10
v1.resize(20);//将size扩大到20
cout << v1.size() << endl;//改变size大小之后的size值为20
cout << v1.capacity() << endl;//capacity值为20
v1.resize(15);//比之前size小
cout << v1.size() << endl;//改变size大小之后的size值为15
cout << v1.capacity() << endl;//capacity值为20
}
功能
规则:
1.当给定的值大于容器当前的值时,就会扩展到该值。
2. 当给定值小于容器的当前值时,不执行任何操作。
#include
#include
using namespace std;
int main()
{
vector<int> v1(10,6);
cout << v1.size() << endl;//size值为10
cout << v1.capacity() << endl;//capacity值为10
v1.reserve(20);//将capacity扩大到20
cout << v1.size() << endl;//size值为10
cout << v1.capacity() << endl;//改变之后的capacity值为20
v1.reserve(15);//比之前capacity小不改变capacity大小
cout << v1.size() << endl;//size值为10
cout << v1.capacity() << endl;//改变之后的capacity值不变
}
分别在vs和g++下运行代码,会发现vs下增加了1.5倍,g++下增加了2倍。 无论如何都不能认为容量增加一倍,具体增加多少要根据具体需求来确定。 vs是PJ版本STL,g++是SGI版本STL。
它只负责开辟空间,并且在开辟空间的同时也会进行初始化。
增删改查功能接口说明
尾塞
尾部删除
在指定迭代器位置插入一个或多个元素
擦除
删除指定迭代器位置或范围的元素
交换
交换两个容器的数据空间
[] 运算符重载
通过下标访问数组元素
功能
#include
#include
using namespace std;
int main()
{
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;
}
//输出1234
cout << endl;
}
功能
#include
#include
using namespace std;
int main()
{
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;
}
//输出1234
cout << endl;
v1.pop_back();//尾删
v1.pop_back();//尾删
for (auto e : v1)
{
cout << e;
}
//输出12
cout << endl;
}
功能
//在指定的迭代器位置插入val,并且返回指定的迭代器位置
iterator insert (iterator position, const value_type& val);
//在指定的迭代器位置后插入n个val值
void insert (iterator position, size_type n, const value_type& val);
例子:
#include
#include
using namespace std;
int main()
{
vector<int> v1(2,3);
vector<int>::iterator it = v1.insert(v1.begin(), 100);
for (auto e : v1)
{
cout << e << " ";
}
//输出100 3 3
cout << endl;
v1.insert(it, 3, 200);
for (auto e : v1)
{
cout << e << " ";
}
//输出200 200 200 100 3 3
cout << endl;
}
擦除功能
//删除指定迭代器位置的元素
iterator erase (iterator position);
//删除指定迭代器区间的元素,左闭右开
iterator erase (iterator first, iterator last);
例子:
#include
#include
using namespace std;
int main()
{
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 << " ";
}
//输出1 2 3 4
cout << endl;
v1.erase(v1.begin() + 1);//删除下标为1的元素
for (auto e : v1)
{
cout << e << " ";
}
//输出1 3 4
cout << endl;
v1.erase(v1.begin(),v1.begin() + 2);//删除下标为[0,2)之间的元素
for (auto e : v1)
{
cout << e << " ";
}
//输出 4
cout << endl;
}
当我们要删除和插入的时候,可以使用erase和erase,但是不建议使用和erase来移动数据。
交换功能
void swap (vector& x);
例子:
#include
#include
using namespace std;
int main()
{
vector<int> v1(3, 2);
vector<int> v2(3, 6);
v1.swap(v2);//交换v1,v2的数据空间
}
[] 运算符重载
[]运算符被重载,可以通过[]+下标来访问容器中的元素。
#include
#include
using namespace std;
int main()
{
vector<int> v1(3, 2);
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
}
除了使用[]+下标来访问容器中的元素之外,我们还可以通过迭代器和range for来访问,只要容器支持迭代器,就支持range for。
#include
#include
using namespace std;
int main()
{
vector<int> v1(3, 2);
//范围for
//迭代器访问
vector<int>::iterator it = v1.begin();
while(it != v1.end())
{
cout << *it;
it++;
}
}
我们也可以使用at ,不同的是下标[]断言,而at 会抛出异常。
迭代器失效问题
迭代器的主要作用是让算法不关心底层的数据结构。 在类中,底层其实就是一个指针,或者说它封装了指针。 迭代器失败是指迭代器底部相应指针指向的空间被破坏,使用了一块已经释放的空间。 如果继续使用无效的迭代器,程序可能会崩溃。
会引起底层空间变化的操作可能会导致迭代器失败,如:、、、、等。
以下代码中存在迭代器失效问题:
#include
#include
using namespace std;
int main()
{
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 << " ";
}
//输出1 2 3 4
cout << endl;
vector<int>::iterator pos = v1.begin() + 2;//获取下标为2的位置的迭代器
v1.insert(pos, 10);//在下标为2的地方插入10
for (auto e : v1)
{
cout << e << " ";
}
//输出1 2 10 3 4
cout << endl;
//插入之后我们想删除元素2
v1.erase(pos);//error,此时迭代器就已经失效了
}
此时运行结果:
意味着迭代器使用一次后就过期了。 代码的本意是在下标为2的位置插入10,然后删除2。但是迭代器用过一次就过期了,所以删除不能成功。
解决方案:每次使用迭代器之前必须重新分配迭代器。
所以上面代码的解决办法就是插入后再次接收返回值,重新赋值pos。
#include
#include
using namespace std;
int main()
{
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 << " ";
}
//输出1 2 3 4
cout << endl;
vector<int>::iterator pos = v1.begin() + 2;//获取下标为2的位置的迭代器
pos = v1.insert(pos, 10);//在下标为2的地方插入10,返回pos还是下标为2的位置
for (auto e : v1)
{
cout << e << " ";
}
//输出1 2 10 3 4
cout << endl;
//插入之后删除下标为2的位置即删除10
v1.erase(pos);
for (auto e : v1)
{
cout << e << " ";
}
//输出1 2 3 4
cout << endl;
}
看一下下面代码中的迭代器失效问题:
#include
#include
using namespace std;
int main()
{
vector<int> v1;
for (size_t i = 0; i <= 6; i++)
{
v1.push_back(i); //插入数据
}
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0) //删除容器当中的全部偶数
{
v1.erase(it);
}
it++;
}
}
流程如下:
当它指向2时,*it % 2 == 0成立。 删除这个位置后,它指向3,然后it++。 此时,它直接指向4。需要注意的是,v.end()的位置也会发生相应的变化:
当它指向4的时候,满足*it % 2 == 0,删除这个位置后,它指向5,然后it++,此时它指向6:
当它指向6时,满足*it % 2 == 0成立。 删除6后,v.end()和它指向同一个位置,然后就是++了。 此时已经超出了数组的范围,迭代器访问了它不属于容器的内存空间,因此程序崩溃。 而且,迭代器遍历容器中的元素进行判断时,并不对元素1、3、5进行判断。
解决方案:可以接收erase函数的返回值(erase函数返回前要删除的迭代器位置),该位置的元素已经被更新,当元素被删除时,使用返回的迭代器继续判断该位置的元素是否需要删除。
#include
#include
using namespace std;
int main()
{
vector<int> v1;
for (size_t i = 1; i <= 6; i++)
{
v1.push_back(i);
}
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0) //删除容器当中的全部偶数
{
it = v1.erase(it);//删除后更新迭代器
}
else
{
it++;//是奇数++
}
}
}
在共同主题中仅出现一次的数字
题目:一个只出现一次的数字
给定一个非空整数数组 nums,除了某个元素只出现一次之外,每个元素都出现两次。 找到只出现一次的元素。
您必须设计并实现一个线性时间复杂度的算法来解决这个仅使用恒定额外空间的问题。
示例1:
输入:nums = [2,2,1]
输出:1
示例2:
输入:nums = [4,1,2,1,2]
输出:4
示例3:
输入:nums = [1]
输出:1
暗示:
想法:
当两个相同的数进行异或时,异或结果为0,当两个不同的数进行异或时,结果不为0; 问题中只有一个数字出现一次,其他数字出现两次。 我们可以把所有的数字进行异或,这样最终的异或结果就是只出现一次的数字。
我们可以通过range for进行遍历,或者迭代器遍历等。
代码:
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ref = 0;
for(auto e : nums)
{
ref ^= e;
}
return ref;
}
};
时间复杂度:O(N)
空间复杂度:O(1)
杨惠三角
作品名称:杨辉三角
给定一个非负整数*,*生成“阳惠三角”的前一行。
在阳惠三角中,每个数字都是其左上方和右上方的数字之和。
示例1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例2:
输入: numRows = 1
输出: [[1]]
暗示:
想法:
首先定义一个二维数组并设置数组的大小为 ,然后将数组中的每一行设置为指定的大小并初始化为0;
将每一行的首末置为1,然后遍历二维中其他等于0的vv[i][j] = vv[i-1][j-1] + vv[i-1]数组][j]; 用于处理(方法1)。
我们还可以使用方法2来排除for循环中不等于0的那些。
代码:
class Solution {
public:
//vector>是二维数组
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;//先定义一个二维数组
//vv.resize(numRows);//将二维数组的大小设置为numRows
vv.resize(numRows,vector<int>());//使用匿名对象来初始化,将二维数组的大小设置为numRows
//设置二维数组中每行有多少个
for(size_t i = 0; i < numRows; i++)
{
vv[i].resize(i+1,0);//生成并且将初始值都设置为0
//每行的第一个和最后一个都是1
vv[i][0] = vv[i][vv[i].size() - 1] = 1;
}
//再将其他值为0的进行处理
//方法一:
//遍历,将数组中等于0的处理掉
for(size_t i = 0; i < numRows; i++)
{
for(size_t j = 0; j < vv[i].size(); j++)
{
if(vv[i][j] == 0)
{
vv[i][j] = vv[i-1][j-1] + vv[i-1][j];
}
}
}
//方法2:
//直接从第2行开始处理
return vv;
}
};
时间复杂度:O(N * N)
空间复杂度:O(1)
如果用C语言来解决这个问题,那就比较麻烦了:
使用C语言解决方案开辟一个二维数组,首先创建一个指针数组,然后通过for循环控制每个指针开辟的空间。
界面:
int** generate(int numRows, int* returnSize, int** returnColumnSizes)
int*外面的实际参数是整数,int**外面是一级指针,所以分别用一级指针和二级指针作为参数来改变接口外的内容。
代码:
int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
int** ret = malloc(sizeof(int*) * numRows);//开辟一个指针数组,每个元素为指针,指向一个int类型的数组
*returnSize = numRows;//将二维数组的行数赋值,不可缺少的一步
*returnColumnSizes = malloc(sizeof(int) * numRows); //是一个整形数组,开辟一个具有numRows个元素的空间,用来存储每行有多少个元素
for (int i = 0; i < numRows; ++i)
{
//开始一行一行的遍历
ret[i] = malloc(sizeof(int) * (i + 1)); //指针数组中每个指针指向的数组元素中的个数为i+1个
(*returnColumnSizes)[i] = i + 1;// 表示第i行中数据元素个数
ret[i][0] = ret[i][i] = 1; //两边的都是1
for (int j = 1; j < i; ++j) {
ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];//计算中间的。
}
}
return ret;
}
为二维数组的行数,必须在接口函数中赋值; 并且二维数组中每一行的个数可以是随机的,辅助指针int**用于存储返回数组中的元素个数。 要创建一维数组并存储每层中的元素数量,一维数组需要自身。 如果传递一个一级指针并赋值给接口中的一级指针,形参的改变不会影响实参,所以为了返回外部定义的指针,参数需要使用二级指针类型,解引用二级指针得到外部定义的指针的地址,赋值可以通过参数传递接口中一维数组的地址。
在C++中,可以直接使用>来完成:
对象的数据并不是存储在里面,而是存储在堆上开辟的空间中,对象存储的内容也是堆上开辟的空间。