大纲
一、基础STL
二、STL的迭代器遍历
三、for(auto it:S)遍历STL
四、STL函数
一、基础STL
目录:
array 普通数组
vector 边长数组
string 字符串
sort 快速排序
auto 任意类型
queue 队列
deque 双端队列
set 集合
stack 栈
map 哈希,映射
priority_queue 优先队列
pair 整合类型
lower_bound 二分下界
upper_bound 二分上界
-------------------------
0.科普知识&无用知识:STL的数组
萌新学的数组就是一个:
type a[MAX_LEN] ;
但其实除了这种数组,STL还有一种数组(但是跟这个没啥区别,耗时还大...):
定义方式:
array < type , MAX_LEN > a ;
但是它有一些功能函数,这是比较香的,不过都可以用数组模拟,所以如果数组能轻松解决的东西还是尽量不要用STL的数组。
说了这么多全是废话...
1.边长数组:vector
vector和普通数组的区别是vector不需要定义数组长度,数组需要提前定义数组长度,相比vector更浪费空间。
vector的定义方式:
vector < type > 名字 ;
vector的基本操作:
vector < int > v ; 定义类型为int的vector数组
v[index] v的第index个元素
v.size () v的长度
v.push_back (val) ; 将值val加入数组v
v.erase (v.begin () + index - 1) ;
删除第index个元素
v.insert (v.begin () + index , val) ;
在index的位置插入值val
unique (v.begin () , v.end ()) ;
将v去重。
遍历:
for (it = v.begin (); it != v.end (); it ++)
int x = * it ;
vector代码实现:
vector < int > v ;
for (int i = 1; i <= 10; i ++)
v.push_back (i) ;
for (int i = 0; i < v.size (); i ++)
cout << v[i] << ' ' ;
v.erase (v.begin ()) ;
for (int i = 0; i < v.size (); i ++)
cout << v[i] << ' ' ;
v.insert (i , 1) ;
for (int i = 0; i < v.size (); i ++)
cout << v[i] << ' ' ;
2.字符串:string
string和字符数组的区别与vector类似,也是不需要定义数组的长度。
string的定义方式:
string 名字 ;
string的基本操作:
string str ;
cin >> str ; 读入字符串str
int len = str.size () ; 获取字符串的长度
cout << str ; 输出字符串
str[index] 字符串的第index个字符
str.erase (index , len) ; 从第index个字符开始,删除它以及后面的len个字符
str.insert (index , insert_str) ; 在index的位置插入字符串insert_str
str.pop_back () 删除末尾字符
str.back () 末尾字符
str += st 末尾加上字符串st
string实现代码:
string str = "Minecraft_Dream" ;
str.erase (9 , 1) ;
cout << str << endl ;
str.pop_back () ;
cout << str << endl ;
str += "m" ;
cout << str ;
3.排序:sort
sort是STL内置的排序,是快速排序的函数,时间复杂度:O(nlogn) 。
sort (a + 1 , a + 1 + n) ;
排序a数组。
sort (a + l , a + 1 + r) ;
排序区间[l, r]
快排没有稳定性,stable_sort是稳定的快排,用法同sort。
stable_sort (a + 1 , a + 1 + n) ;
stable_sort (a + l , a + 1 + r) ;
sort实现代码:
int a[N] , n ;
int main () {
cin >> n ;
for (int i = 1; i <= n; i ++)
cin >> a[i] ;
sort (a + 1 , a + n + 1) ;
for (int i = 1; i <= n; i ++)
cout << a[i] << ' ' ;
}
4.任意类型定义:auto
auto支持任意类型的信息,一半用来简化代码,用法:
就比如定义了一个结构体:
struct Edge {
int a , b , w ;
} edges ;
接下来要存储edges,可以:
方法1:
Edge e = edges ;
方法2:
auto e = edges ;
auto还可以是迭代器类型的:
遍历map:
方法1:
map < int ,
文章评论