PAT知识点整理之STL
参考网站:Norway, 芹菜猪肉饺贼棒, Foreordination
参考书籍:《算法笔记》
STL相关
-
Vector
-
概述:变长数组
- 用法:可以用来以邻接表的方式储存图(需要复习)
- 例子:
vector<node> name; //node是结构体的类型 vector<vector<int> > name; //>>之间加空格
vector<node> name; //node是结构体的类型 vector<vector<int> > name; //>>之间加空格
-
访问:
- 下标
vector<typename>::iterator it; //vi[i]和*(vi.begin()+i)是等价的 for(vector<int>::iterator it = vi.begin(); it != vi.end(); it++){ printf("%d ", *it); }
- vi.size()
-
操作:
- push_back(x) 就是在vector后面添加一个元素x, 时间复杂度为O(1)
- pop_back() 用以删除vector的尾元素, 时间复杂度为O(1)
- size() 获取vector中元素的个数,时间复杂度为O(1) 返回的是unsigned类型
- clear() 用来清空vector中的所有元素, 时间复杂度为O(N), 其中N为vector中元素的个数
- insert() insert(it, x)用来向vector的任意迭代器it处插入一个元素x, 时间复杂度O(N)
-
-
Set
- 概述:自动排序的唯一数组
- 用途:set重要的作用:自动去重,升序排序。
- 例子:
set<typename> name; set<int> name; // 定义和写法和vector基本一样,同样typename可以是任何基本类型,结构体,STL容器类型。 //同样,typename是容器的时候,>>后要加空格,避免编译器当成位运算出错。
- 访问:
- set只能通过迭代器iterator访问,因为除了vector和string之外的STL的容器都不支持以下标的方式访问。
set<int> st; for(set<int>::iterator it=st.begin();it!=st.end();it++) { printf("%d ",*it); }
- set只能通过迭代器iterator访问,因为除了vector和string之外的STL的容器都不支持以下标的方式访问。
- 操作:
- insert()函数,insert(x):将x插入set容器中,并且自动递增排序和去重。时间复杂度为O(logN),N为元素个数
- find()函数,find(value):查找值为value的元素,返回它的迭代器。时间复杂度为O(logN),N为元素个数
- erase()函数,erase(x):删除单个元素,时间复杂度为O(logN);erase(a,b);删除左闭右开区间内[a,b)的元素,时间复杂度为O(b-a);
- size()函数,size():用来获得set内元素的个数,时间复杂度为O(1)
- clear()函数,clear():用来清空set所有元素,时间复杂度为O(N)
- earse() : 两个用法 :删除单个元素 erase(it)即删除迭代器为it处的元素 vi.erase(vi.begin() + 3) 删除vi中第4个元素;删除一个区间内的所有元素 erase(first, last) 删除[first, last) 左闭右开
-
String
- 概述:用来代替char[]
- 用途:当作字符。。。
- 例子:
string str; string str="abcd";
-
访问:
- 可以如同字符数组一样去访问string
-
string的迭代器不需要参数,直接定义string::iterator it;
string str="abcd"; for(int i=0;i<str.length;i++) { printf("%c ",str[i]);//a b c d } //通过迭代器访问string内容 for(string::iterator it=str.begin();it!=str.end();it++) { pritnf("%c ",*it); }
- 操作:
- operator+=这是string的加法, 可以将两个string直接拼接起来
- compare operator 两个string类型可以直接使用 == != < <= > >= 比较大小,比较规则是字典序
- length()/size() length()返回string的长度
- insert(pos, string), 在pos号位置插入字符串string
string str1 = "abcxyz", str2 = "opq"; str.insert(3, str2); //abcopqxyz str.insert(str1.begin() + 3, str2.begin(), str2.end); //abcopqxyz
- erase()
string str = "abcdefg"; str.erase(str.begin()+4); // -> abcdfg str.erase(str.begin()+2, str.end()-1); // -> abg str.erase(3, 2); // -> abcfg
- clear() 用以清空string中的数据
- substr(pos, len) 返回从pos号位置开始、长度为len的子串
- string::npos
- find();str1.find(str2),当str2是str1的子串时,返回其在str中第一次出现的位置;如果不是其子串,那么返回string::npos; str1.find(str2, pos) 从str1的pos号位置开始匹配str2, 返回值同上
- replace();
str.replace(pos, len, str2),把str从pos号位置开始、长度为len的子串替换为str2;
str.replace(it1, it2, str2),把str的迭代器[it1, it2)范围的子串替换为str2
-
Map
-
概述:map 可以将任何基本类型(包括STL容器) 映射到任何基本类型(包括STL容器)
-
用途:
- 建立字符和整数映射的题目
- 判断大整数或者其他类型数据是否存在的题目,可以把map当bool数组用
- 字符串和字符串的映射可能遇到
如果一个键需要对应多个值,就只能用multimap
unordered_map 以散列代替map内部的红黑树实现,处理无排序功能 - C++11多了unordered_map,说是速度快很多,有时间关注
-
例子:
map<typename1, typename2> mp;
-
访问:
- 通过下标访问 m[‘a’]
- 通过迭代器
for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++) { printf("%c %d\n",it->first,it->second);//it->first:当前映射的键,it->second:当前映射的值 }
-
操作:
- find(),find(key):返回键为key的映射,时间复杂度为O(logN)
-
erase()
删除单个元素:
mp.erase(it):it为需要删除的元素的迭代器。时间复杂度为O(1)
mp.erase(key):key为删除元素的键,时间复杂度为O(logN);删除区间内的元素,左闭右开[start,end)
- size()获得map中映射的对数
- clear() 用来清空map中的所有元素
-
-
Queue
- 概述:实现先进先出的容器
- 用途:
- 实现广度优先搜索时,可以不用自己动手实现一个队列,而是用queue代替
- 例子:
queue<typename> name; queue<int> q;
- 访问:
queue是一种先进先出的限制性数据结构。通过front()访问队首元素,通过back()来访问队尾元素。queue<int> q; for(int i=1;i<=5;i++) { q.push(i);//依次将i入队,1,2,3,4,5 } printf("%d %d\n",q.front(),q.back());//输出结果1,5
- 操作:
- front(),back()。获取队首,队尾元素,时间复杂度为O(1)
- pop()。队首元素出队,时间复杂度为O(1)
- empty()。检测queue是否为空,返回bool类型,true为空。
- size()。返回queue内元素个数
- 其他:此外还有个priority_queue(优先队列,自定义优先级)
-
Stack
- 概述:实现后进先出的容器
- 用途:
- 模拟递归
- 例子:
stack<typename> sk;
- 访问:
只能通过top()来访问栈顶元素。stack<int> sk; for(int i=1;i<=5;i++) { sk.push(i);//push(i)用来把i压入栈,入栈顺序1,2,3,4,5 } printf("%d\n",sk.top()); // -> 5
- 操作:
- push() :将x入栈,时间复杂度为O(1)
- top() :获取栈顶元素,时间复杂度为O(1)
- pop() :出栈顶元素。
- empty() : 判断栈是否为空
- size() :获得栈元素个数
-
Pair
Algorithm相关
-
交换———— swap();
-
反转———— reverse();
int a[10] = {10, 11, 12, 13, 14, 15}; reverse(a, a+4); //数组 string str= "12345678" reverse(str.begin()+2, str.begin()+6); 注意左闭右开// ->12543678
-
全排列———— next_permutation()
int a[10] = {1, 2, 3}; do{ // etc... }while(next_permutation(a, a+3));
July 31, 2020 @ 4:56 pm
You do have a fabulous blog thanks. Martica William Cusick
August 30, 2020 @ 11:18 pm
Your mode of explaining all in this post is truly nice, all be able to effortlessly know it, Thanks a lot. Marla Horton Obie