vector

引入

我们都学习过数组和链表：

在使用数组时，我们可以利用下标快速访问数组中的元素，但是数组的长度固定。

在使用链表时，我们可以改变长度，但是不能便利地访问元素。

接下来，我们将学习一种新的容器，它兼具了数组和链表的特性。

定义

定义一个vector，你可以在里面放各种数据类型。

注意

需要添加vector头文件

vector<int> a;
vector<double> b;

struct T {};
vector<T> c;

上面的定义中，并没有设置容器的大小，我们可以通过以下几种方式来控制容器的大小

int n = 5;
vector<int> a(n, 1);  // 设置大小为 5 ，并初始化值为1，若不添加默认为0
vector<int> b = {2, 0, 0, 6, 0, 9, 1, 7};
// 可以用 size() 得到容器的大小
cout << a.size() << ' ' << b.size() << endl;
// 输出 5 8

// 可以用 resize() 改变容器大小
b.resize(2);
for (auto x : b) cout << x << ' ';
cout << endl;
// 输出 2 0

注意

区分vector<int> a(n)与vector<int> a[n]。一个vector容器就可以作为一个数组。 而vector<int> a[n]相当于是vector的数组，由多个vector组成。

用作数组

vector可以当作数组使用，我们可以进行下标访问。

vector<int> a(n);
for (int i = 0; i < n; i++) {
  cin >> a[i];
}

// 可以用这两种方法定义二维数组
auto b = vector(4, vector<int>(5));
vector<vector<int>> c(5, vector<int>(4));

用作链表

vector可以当作链表使用，我们可以在链表头和尾插入元素。

vector<int> a;
for (int i = 1; i <= 5; i++) a.push_back(i);
// 我们在此进行下标访问，说明其同时具有链表和数组的特性
for (int i = 0; i < 5; i++) cout << a[i] << ' ';
cout << endl;
// 输出 1 2 3 4 5

混合使用

vector<int> a = {1, 2, 3, 4};
// 在末尾追加元素
a.push_back(5);
for (auto x : a) cout << x << ' ';
cout << endl;
// 输出 1 2 3 4 5

总结

vector的基础用法大致为以上这些（当然它还有很多其他很好用的功能）。

queue & stack

注意

需要添加queue&stack头文件

stack

后进先出

stack<int> s;
for (int i = 1; i <= 5; i++) {
  s.push(i);
}
// 如果栈不为空，则循环继续
while (!s.empty()) {
  int x = s.top();
  s.pop();
  cout << x << ' ';
}
// 输出 5 4 3 2 1

queue

先进先出

queue<int> q;
for (int i = 1; i <= 5; i++) {
  q.push(i);
}
while (!q.empty()) {
  int x = q.front();
  q.pop();
  cout << x << ' ';
}
// 输出 1 2 3 4 5

priority_queue

队首元素总是最大的

priority_queue<int> q;
vector<int> a = {1, 5, 3, 2, 4, 7};
for (auto x : a) {
  q.push(x);
}
while (!q.empty()) {
  int x = q.top();
  cout << x << ' ';
  q.pop();
}
// 输出 7 5 4 3 2 1

队首元素总是最小的

priority_queue<int, vector<int>, greater<int>> q;

拓展：常用算法

注意

需要添加algorithm头文件

sort

基于快速排序的混合排序（堆排序，插入排序），性能相当出色。

vector<int> a = {1, 5, 3, 2, 4, 7};
sort(a.begin(), a.end());
for (auto x : a) cout << x << ' ';
// 输出 1 2 3 4 5 7

sort(a.begin(), a.end(), greater<int>());
for (auto x : a) cout << x << ' ';
// 输出 7 5 4 3 2 1