STL

初步介绍

STL(Standard Template Library)，C++标准库的一部分，可以帮助我们处理常见的数据结构和算法。容器是STL的重要组成部分，用于存储和组织数据的对象。

vertor

概念

动态数据容器：相比于数组在一开始就申明了大小，vector无需再申明时确定大小，可以做到动态调整容量，所以称之为动态数组

使用

  • 首先引入头文件#include <vector>
  • 定义方法为vector <类型> 变量名,例如vector<int> vi;
  • 如果申明类似二维数组可写作vector<vertor<int>> vvi; 含义时外层容器的元素是vector<int>,内层容器的元素是int。比二维数组更灵活

取值/索引

支持下标操作符,形如vi[0];同时,vector支持了通过at来访问元素.==区别at在访问时会检查下标是否越界,若越界在进行时会直接报错==

输入和输出

由于vector在申明时内部没有任何数据,所以需要读取数据到某个变量,然后通过push_back将这个变量扔进容器中

1
2
3
4
5
for (int i = 0; i < n; i ++){
    int x;
    cin >> x;
    vi.push_back(x);
}

或使用范围循环for (auto& x: arr) cin >> x;

输出时可以通过size获取容器的大小,然后用for循环进行输出;

1
2
3
for(int i = 0; i < vi.size(); i ++){
    cout << vi[i] << endl;
}

或利用范围循环来遍历整个容器内的元素for (auto& x: vi) cout << x << endl;

初始化

普通vector容器初始化

  • 可以像普通数组一样定义大小vector<int> v0(5);,使得容器内被5个0填充;
  • 如果想填充指定值,就在第二个参数上填上初始值vector<int> v1(5, 1);
  • 或者用花括号像数组一样定义初始值vector<int> v2{1, 2, 3}
  • 还可以用另一个vector进行初始化vector<int> v3(v1);

==如果初始化申明了vector的大小,就不用每次都用push_back挨个将数据丢入容器内,可以使用范围循环,和数组一样方便的进行数据输入==

利用C++的auto自动类型推导,可以更方便的进行多维vector的初始化

1
2
3
4
vector<int> v0(5);
for (auto& x: v0){
    cin >> x;
}

多维vector

引用sunny—ll的文章

https://xas-sunny.blog.csdn.net/

总结

vector<vector<int>> table(size1, vector<int>(size2, 0));

代码说明：声明一个名为 table 的容器，其元素为 vector的容器。简单来说类似一个int型的二维数组

img

具体可理解如下

img

图中，我将外围容器table的初始化参数分成了两部分 A、B

  • A: table外围容器的大小
  • B: table外围容器的内容，即 size1个vector型的元素。
  • B1：内部容器的大小
  • B2：内部容器的内容

vector 二维数组的 初始化

直接初始化

首先，要先知道：二维 vector如何获得行数和列数。

1
2
3
4
5
6
7
8
9
10
vector<vector<int>> a(r, vector<int>(c))；
int row = a.size();          //获取行数
int column = a[0].size();    //获取列数
// （1）下面定义的是行为r，列为c的二维数组
vector<vector<int>> ans(r, vector<int>(c));
// （2）下面定义的是行为r，列为c的二维数组，初始值为0
vector< vector<int> > a(r, vector<int>(c, 0)); 
//	对每行的列进行操作
vector<vector<int>>mat(r);//每行的定义
mat[i].push_back(1);//这就是该第i-1行的插入一个元素，值为1

用resize来提前构建

1
2
3
4
5
vector<vector<int>> new_mat(r);//注意这个r是不可缺少的，规定其有多少行
for(int i=0 ;i<r; i++) //二维vector的初始化时有要求的
{
   new_mat[i].resize(c);
}

vector 二维数组的 添加与删除

添加一行

1
2
3
//插入一行数组：将in_row数组插入到第2行！ 
vector<int> in_row(5,6);//初始化一个数组，包含5个元素并且全为6
a.insert(a.begin()+2,in_row);

添加一列

1
2
3
4
for(int i=0;i<a.size();i++)
{
	a[i].insert(a[i].begin()+2,9);
}

删除一行

1
a.erase(a.begin() + 2, a.begin() + 3);

删除一列

1
2
3
4
5
//删除a的第二列
	for (int i = 0; i < a.size(); i++)
	{
		a[i].erase(a[i].begin() + 2, a[i].begin() + 3);
	}

二维数组的 输入

例如vector<vector<int>> urls(n);为有n层的二维数据,使用范围循环输入数据

1
2
3
4
5
6
for (auto& url: urls) {
	int m;
    cin >> m;//表示这一行vector的数量
    url.resize(m);//定义这一行vector的大小
    for (auto& x: url) cin >> x; //输入数据
}

二维数组的 输出

引用符号 &

例如定义一个二维容器players(2)

用int CurrentPlayer = 0,并后续用取模操作实现每次切换玩家,存储数据在数组的不同行,使用引用符使得代码更简洁易读 auto &player = players[CurrentPlayer],随后对其进行操作

输出

使用范围循环对数组每一行进行求和计算代码ru’xai

1
2
3
4
5
for (auto& player: players) {
    long long sum = 0;
    for (auto& x: player) sum += x;
    cout << sum << ' ';
  }

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
#include <vector>
int main() {
  int n;
  cin >> n;
  vector<vector<int>> tri;
  tri.push_back({1});
  if (n > 1) {
    tri.push_back({1, 1});
  }
  for (int i = 2; i < n; i++) {
    vector<int> row(i + 1, 0); // 初始化当前行，所有元素为0
    row[0] = row[i] = 1; // 每行的开始和结束元素为1
    for (int j = 1; j < i; j++) {
      row[j] = tri[i - 1][j - 1] + tri[i - 1][j]; // 计算中间元素
    }
    tri.push_back(row);
  }
  for (auto& line : tri) {
    for (auto& x : line) {
      cout << x << ' ';
    }
    cout << endl;
  }
}

vector高级能力

赋值运算&比较运算

可以将一个vector直接赋值给另一个vector

1
2
3
4
5
vector<int> v0{1, 2, 3};
vector<int> v1;
v1 = v0;
vector<int> v2{1, 2, 4};
v0 < v2;

两个数组比较大小的方法(==字典序比较法==):挨个比较数组的元素,一旦不同,那么拥有较小元素的vector就是更小的,如果全部相同,则说明两个vector相同

vector常用成员函数

front—获取vector的第一个元素

1
2
vector<int> v{1, 2, 3};
cout << v.front() << endl

back—获取vector的最后一个元素

1
2
vector<int> v{1, 2, 3};
cout << v.back() << endl

size—获取当前的元素个数

1
2
vector<int> v{1, 2, 3};
cout << v.size() << endl

empty—判断当前vector是否为空

1
2
vector<int> v{1, 2, 3};
cout << v.empty() << endl

clear—清空vector数据

1
2
vector<int> v{1, 2, 3};
v.clear();

push_back—将数据塞入vector末尾

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

pop_back—将最后一个数据从vector中移除

1
2
vector<int> v{1, 2, 3};
v.pop_back();

resize—重新定义vector的大小

1
2
vector<int> v{1, 2, 3};
v.resize(3);

如果比原先小则删除末尾的元素;如果比原先大则用0来填充新增的元素,如果有第二个参数,v.resize(5,1);则改用第二个参数来填充

begin&end

v.begin()&v.end(),返回的是vector起始,末尾迭代器

迭代器分别指向的分别是容器始末,通过迭代器可以访问数组的始末

1
2
3
4
for (vector<int>::iterator iter = v.begin(); iter ++){
} //vector<int>::iterator是迭代器的类型,也可以用auto来代替
for(auto iter= v.begin();iter != v.end(); iter++){
} //迭代器支持加法,但这并非算术运算,而是让迭代器指向下个元素

image-20241019142429502

因此这个for循环的含义是:初始化迭代器指向第一个元素,然后不断指向下个元素,直到等于末尾迭代器,循环结束

迭代器并非元素本身,而是指向元素,所以想要获取迭代器所指向元素的值,需要用*iter

1
2
3
for(auto iter= v.begin();iter != v.end(); iter++){
    *iter;
}

迭代器另一作用,定位位置;例如删除或增加某一个元素需要用迭代器指定位置

erase—删除元素

通过v.begin()+下标来定位

1
2
3
4
vector<int> v{1,2,3,4,5};
v.erase(v.begin());//只有一个参数代表输出指定位置的元素
vector<int> v{1,2,3,4,5};
v.erase(v.begin() + 1, v.beign() + 3);//若两个参数则表示删除某段连续的元素

insert—插入元素

1
2
3
4
5
vector<int> v{1,2,3};
v.insert(v.begin(), 4); //第一个参数值代表插入的位置,后面的参数代表插入的内容
v.insert(v.begin() + 1, {4,5,6});// 可以是普通的值也可以是一段花括号表示的数据
//还可以是另一个容器的范围 例如v1{1,2,3};v2{4,5,6}
v1.insert(v1.end(),v2.begin,v2.end());//将容器放到另一个容器的尾部,得到新容器v1{1,2,3,4,5,6}

reverse&emplace_back

后续再做阐述