暑期笔记 | STL中的简单数据结构 (线性表等)
随便写点笔记，内容比较简单。忘了什么写法就看一遍。
链表
数组的点查复杂度为$O(1)$，插入或删除复杂度为$O(n)$。
链表的点查复杂度为$O(n)$，插入或删除复杂度为$O(1)$。
除了储存数据以外，单项链表还储存$next$，双向链表储存$pre$和$next$。
用结构体定义链表
struct node{
int data, next;
};
int head;//头节点
找到头节点的方法：遍历链表时，标记其中被指向过的下标。没有被指向过的下标即为头节点的下标。
链表的遍历
for(int i=head;;i=a[i].next){
cout << a[i].data;
if(!a[i].next) break;//前提：a[i].next未被赋值时被初始化为0
}
链表的插入和删除只需将有关的$next$进行修改即可；链表的点查需要在遍历的基础上加以判断。
数组与链表的使用是辩证 的。
vector
可以将$vector$当成不定长数组来使用。
常用函数
vector <int> c //定义
c.clear() //移除容器中所有数据
c.empty() //判断容器是否为空
c.erase(pos) //删除pos位置的数据
c.erase(beg,end) //删除[beg,end)区间的数据
c.front() //传回第一个数据。
c.insert(pos,elem) //在pos位置插入一个elem
c.pop_back() //删除最后一个数据。
c.push_back(elem) //在尾部加入一个数据。
c.resize(num) //重新设置该容器的大小
c.size() //返回容器中实际数据的个数。
c.begin() //返回指向容器第一个元素的迭代器
c.end() //返回指向容器最后一个元素的迭代器
注意到，pos需要传入一个迭代器。所以如果要抹去下标为 i的元素，需要使用 c.erase(c.begin()+i);。
遍历时，使用 for(int i=0; i<c.size(); i++)。
二维vector
vector <vector <int>> c(3);
vector <int> c[3];
//这两种写法都使得(vector)c中能储存3个vector
vector排序
vector <int> c;
sort(c.begin(), c.end(), cmp);//也可以不传cmp，默认从小到大排序
小明的数字表(vector习题)
输入格式
第一行输入一个 n (n<=100000)，表示数列的长度； 第二行 n 个正整数 ai (0<=ai<=100000000)； 第三行一个数字 q (q<=100000)表示询问的次数； 下面 q 行，每行给出三个数字 u,v,w, 表示查找第 u 位为数字 v 的所有数字中，第 w 小的数。
输出格式
每个询问输出一个数字，查询不到输出“-1”。
输入样例
4
1 21 22 3
3
2 2 2
1 1 2
2 2 3
输出样例
22
21
-1
参考程序(空间换时间)
#include <bits/stdc++.h>
using namespace std;
vector <int> arr[10][10];//arr中可以储存10*10个vector
int main() {
int n,num,tnum,q,u,v,w,t=1;
cin >> n;
for(int i=0;i<n;i++){
t=1;//第t位数
cin >> num;
tnum = num;
while(tnum){
arr[t][tnum%10].push_back(num);//arr[u][v]中储存了所有第u位为数字v的数
tnum/=10;t++;
}
}
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
sort(arr[i][j].begin(),arr[i][j].end());//对所有的arr[u][v]从小到大排序
}
}
cin >> q;
for(int i=0;i<q;i++){
cin >> u >> v >> w;
if(arr[u][v].size()>=w) cout << arr[u][v][w-1] << endl;//如果存在第w小的数就输出
else cout << -1 << endl;
}
return 0;
}
栈
栈是后进先出的数据结构。
可以用数组实现一个栈：
int t[10001];
int head=0;//元素个数（栈顶下标）
int size(){
return head;
}//获得栈的大小
int top(){
return t[head-1];
}//获得栈顶元素
void push(int x){
t[head++]=x;
}
void pop(){
head--;
}
也可以使用 C++的 stack模板：
#include <stack>
stack <int> t;
它具备上方实现的四个功能，而且有一个 t.empty()函数，返回栈是否为空。
利用栈的思想，容易解决合法括号匹配等问题。这些问题表面上不一定与栈直接有关。
队列
队列是先进先出的数据结构。
可以用数组实现一个队列：
int q[100001];
int head=1;
int tail=0;
void push(int x){
q[++tail]=x;
}
void pop(){
head++;
}
int size(){
return tail-head+1;
}
int front(){
return q[head];
}
也可以使用 C++的 queue模板：
#include <queue>
queue <int> q;
它具备上方实现的四个功能，并有以下函数：
q.back(); //返回队尾元素
q.empty(); //返回队列是否为空
队列的基本用途是模拟有关排队、抽牌等问题。
map
类似于$python$中的 dict。
- $map$中的操作是$O(\log n)$的。
- $map$中的元素是有序的。
以下代码返回一个$key$是否在$map$中。
map <int, string> a;
map <int, string> ::iterator it;
bool isIn(int key){
it = a.find(key);
if(it==a.end()) return false;
else return true;
}
bool isIn(int key){
return a.count(key);
}
//两种写法是等价的
以下代码遍历$map$中所有的键和值。
map <int, string> a;
map <int, string> ::iterator it;
for(it=a.begin(); it!=a.end(); it++){
cout << "key:" << it -> first << " "
<< "value:" << it -> second << endl;
//first : key; second : value
}
注意：若要在多组询问中使用$map$，一定需要在每组执行前使用 map_a.clear();。
和为k的连续区间(map习题)
有一整数数列$a[1], a[2], … , a[n]$（有正有负），以及另一个整数$k$，求一个区间$[i, j]$，$(1 \le i \le j \le n)$，使得$a[i] + … + a[j] = k$。
输入格式
第$1$行输入$n$, $k$；之后$n$行输入$a[i]$。
输出格式
若没有这样的区间，输出$No\ Solution$，否则输出$i$和$j$。
输入样例
6 10
1
2
3
4
5
6
输出样例
1 4
思路
使用前缀和来计算区间加和，用$map$来标记前缀和是否存在($mp[sum[i]]=1\ or\ 0$)。如果我们找到一个$sum[i]$，使得$(sum[i]+k)$也被$map$映射过，则存在合法的解。只需再遍历一下找到这个解即可。
参考代码
#include <bits/stdc++.h>
using namespace std;
int a[10005];
int sum[10005]; //前缀和
map <int, int> mp; // 用于反查某个数值是否是一个前缀和
int main(){
int n,k,flag=0;
cin >> n >> k;
for(int i=1;i<=n;i++){
cin >> a[i];
sum[i]+=sum[i-1]+a[i];
mp[sum[i]]++;//标记
}
for(int i=0;i<=n&&!flag;i++){//遍历前缀和
if(mp.find(sum[i]+k)!=mp.end()){//检验sum[i]+k是否被映射过
for(int j=i+1;j<=n;j++){//如果存在解，从i+1开始遍历，找到它所在的确切位置
if(sum[j]-sum[i]==k){
cout << i+1 << " " << j;
flag=1;
}
}
}
}
if(!flag) cout <<"No Solution";
return 0;
}
set
$set$中的操作是$O(\log n)$的。
$set$的正向遍历和$map$写法相同，且可以通过以下代码反向遍历：
set <int> st;
set <int> ::reverse_iterator it;
for(it=st.rbegin(); it!=st.rend(); it++) cout<<*it<<endl;
重要函数：
set <int> st;
set <int> ::iterator it_1 = st.lower_bound(n); // 返回st中大于或等于n的第一个元素位置的迭代器，如果找不到，迭代器则为set.end()
set <int> ::iterator it_2 = st.upper_bound(n); // 返回st中大于n的第一个元素位置的迭代器
因为 $set$ 中的元素本身是有序的，因此 $begin()$ 会直接返回集合中最小的元素的位置，而 $end()$ 返回的是集合中最大元素的位置。
如果我们想使用自定义的数据类型构成$set$，需要重载操作符来为它排序：
struct stu{
...;
bool operator < (const stu &tmp) const{
return ...;
}
};
set <stu> st;
♥