STL的用法 方便自己回看
1. vector(变长数组)
头文件
初始化
1
2
3
4
| vector<int>ss;
vector<int>ss(n+1,0)
vector<vector<int>>ss;
vector<vector<int>>ss[5]
|
拷贝初始化
1
2
3
| vector<int> a(n + 1, 0);
vector<int> b(a);
vector<int> c = a;
|
vector v[5]可以这样理解：长度为5的v数组，数组中存储的是vector 数据类型，而该类型就是数组形式，故v为二维数组。其中每个数组元素均为空，因为没有指定长度，所以第二维可变长。可以进行下述操作：
1
2
| v[1].push_back(2);
v[2].push_back(3);
|
1.2 函数方法
STL的函数方法一般分为删除、添加、查找。
以数组ss举例
1
2
3
4
5
6
7
8
9
10
11
12
| ss.front()
ss.front()
ss.push_back(element)
ss.size() 返回实际数据个数（unsigned类型）
ss.clear() 清除元素个数O ( N ) O(N)O(N)，N为元素个数
ss.resize(n, v) 改变数组大小为n,n个空间数值赋为v，如果没有默认赋值为0
ss.insert(it, x) 向任意迭代器it插入一个元素x
例：ss.insert(ss.begin() + 2,-1) 将-1插入ss[2]的位置
ss.erase(first,last) 删除[first,last)的所有元素
ss.begin() 返回首元素的迭代器（通俗来说就是地址）
ss.end() 返回最后一个元素后一个位置的迭代器（地址）
ss.empty() 判断是否为空，为空返回真，反之返回假
|
1.3数组的访问
1.3.1 下标访问
和正常数组一样
1
2
3
| for(int i = 0; i < ss.size(); i++){
cout<<ss[i];
}
|
1.3.2 迭代器访问
不细说了
1.3.3 智能指针访问
1
2
3
| for(auto val : v) {
cout << val << " ";
}
|
2. stack
-这是分割线
1.1 stack
栈为数据结构的一种，是STL中实现的一个先进后出，后进先出的容器
头文件
初始化
1
2
3
| stack<int>ss;
stack<char>ss;
stack<listnode*>ss;
|
1.2 方法函数
1
2
3
4
5
| ss.push(element);
ss.pop();
ss.top();
ss.empty();
ss.size();
|
1.3 函数访问
3. queue
1.1
queue即队列，是一种基本数据结构类型，在一些算法中有妙用，比如著名的bfs广度优先算法，嗯嗯 先进先出
1.2 方法函数
假设ss是一个队列
1
2
3
4
5
6
| ss.push(ele);
ss.pop();
ss.front();
ss.back();
ss.size();
ss.empty();
|
1.3 优先队列
这个确实需要单独来提一下
1
2
| priority_queue<int,vector<int>,greater<int> >ss;
priority_queue<int,vector<int>,less<int> >ss;
|
sla在实现哈夫曼树算法时有妙用，感觉应该也有其他用处sla
4 string字符串
$\vec{a}$
字符串string是一个字符串类，和char型字符串类似。
可以把string理解为一个字符串类型，像int一样可以定义
1.1 初始化及定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include<string>
string str1;
string str2("123456789");
string str3("12345", 0, 3);
string str4("123456", 5);
string str5(5, '2');
string str6(str2, 2);
|
1.2 函数方法
插入
1
2
3
| ss.push_back(ele);
ss.insert(pos,ele);
ss.append(str)
|
长度
1
2
| ss.size() ss.length()
ss.max_size()
|
1.3 stirng的读入
这里让我想到机考的时候字符串没处理换行符导致的bug
1
2
3
4
5
6
7
8
9
10
| #include<string>
int main()
{
int n;
string ss;
cin>>n;
getchar();
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
}
|
5 map映射
5.1 介绍
map类似映射，在做leetcode题时用unordered_map表示哈希表？
定义
1
2
3
4
| #include<map>
map<string,int>ss;
map<int,int>ss;
map<string,node>ss;
|
map特性：map会按照键的顺序从小到大自动排序，键的类型必须可以比较大小
好像map可以用来表示二维数组
5.2 方法
6 pair
6.1
好像记错pair和map了
只有两个元素 可以代替二元结构体
作为map键值对进行插入
1
2
3
4
5
6
7
8
9
10
11
| #include<utility>
pair<string, int> p("wan",1);
pair<string, int> p;
pair<string,int>ss;
p = {"wang", 18};
p = make_pair("wang", 18);
ss=("sss",11);
p = pair<string, int>("wang", 18);
|
6.2 访问
1
2
3
4
| pair<int,int>ss[20];
for(int i=0; i < 20; i++ ){
cout<<p[i].first<<" "<<p[i].second;
}
|
7 set集合
7.1定义
set容器中的元素不会重复，当插入集合中已有的元素时，并不会插入进去，而且set容器里的元素自动从小到大排序。
即：set里面的元素不重复 且有序
1
2
| #include<set>
set<int>ss;
|
7.2函数方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| s.begin() 返回set容器的第一个元素的地址（迭代器）O ( 1 ) O(1)O(1)
s.end() 返回set容器的最后一个元素的下一个地址（迭代器）O ( 1 ) O(1)O(1)
s.rbegin() 返回逆序迭代器，指向容器元素最后一个位置O ( 1 ) O(1)O(1)
s.rend() 返回逆序迭代器，指向容器第一个元素前面的位置O ( 1 ) O(1)O(1)
s.clear() 删除set容器中的所有的元素,返回unsigned int类型O ( N ) O(N)O(N)
s.empty() 判断set容器是否为空O ( 1 ) O(1)O(1)
s.insert() 插入一个元素
s.size() 返回当前set容器中的元素个数O ( 1 ) O(1)O(1)
s.erase(iterator) 删除定位器iterator指向的值
s.erase(first,second） 删除定位器first和second之间的值
s.erase(key_value) 删除键值key_value的值
查找
s.find(element) 查找set中的某一元素，有则返回该元素对应的迭代器，无则返回结束迭代器
s.count(element) 查找set中的元素出现的个数，由于set中元素唯一，此函数相当于查询element是否出现
s.lower_bound(k) 返回大于等于k的第一个元素的迭代器O ( l o g N ) O(logN)O(logN)
s.upper_bound(k) 返回大于k的第一个元素的迭代器O ( l o g N ) O(logN)O(logN)
|
7.3 访问
智能指针访问
1
2
3
4
5
| for(auto it:s){
cout<<it<<endl;
}
cout<<*s.rbegin();
|
7.4 其他的一些set
插眼
8 tuple(元组)
8.1
tuple模板是pair的泛化，可以封装不同类型任意数量的对象。
可以把tuple理解为pair的扩展，tuple可以声明二元组，也可以声明三元组。
tuple可以等价为结构体使用