0%

浅谈STL

发表于 更新于 Valine：
本文字数： 4.8k 阅读时长 ≈ 8 分钟

今天浅谈一下下STL。
STL是指C++的标准模板库(Standard Template Library)。一个既好用又复杂的library。

不定长数组：vector

需要添加头文件 #include
vector是一个模板类，需要用vectora或者vectorb这样的方式来声明一个vector。
我个人觉得vector就像一个数组，但却比数组方便。

vector的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
数组有的基本操作，vector都有...
 vector<int> a;
 a.back();//返回a的最后一个元素
 a.front();//返回a的第一个元素
 a.clear();//清空a中的元素
 a.empty();//判断a是否为空，空则返回ture,不空则返回false
 a.pop_back();//删除a向量的最后一个元素
 a.erase(index)//删除下标index的元素
 a.erase(a.begin()+1,a.begin()+3);
 //删除区间 [a.begin()+1,a.begin()+3) 的数，STL里面大多数都是采用左闭右开的形式.
 a.push_back(n);//在a的最后一个向量后插入一个元素，其值为n
 vector也有insert函数，跟string差不多在此不再赘述了，详情请翻看[Some tips for String](https://ihopezero.github.io/2019/04/17/Some-tips-for-String/).
 a.size();//返回a中元素的个数
 a.capacity();//返回a的空间大小
 a.resize();//重新设置a的大小
 a.find(n);//返回n出现的下标，类似string的find()

集合：set

需要添加头文件 “set “,set中的元素已从小到大排好序了，set是用二叉搜索树维护的集合容器，效率很高O（log(n)）

set的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//声明
set<int> s;
//插入元素
s.insert(1);
s.insert(3);
s.insert(5);
//查找元素
set<int>::iterator ite;//iterator的意思是迭代器，是STL中的重要概念，类似指针.
ite=s.find(1);
if(ite==s.end())puts("not found");
else puts("found"); //输出 found
//其他的查找元素方法
//删除元素
s.erase(3);
if(s.count(3)!=0)puts("found");
else puts("not found"); //输出not found
//判断集合是否为空
s.empty();
//清空集合的元素
s.clear();
//遍历所有元素
for(ite=s.begin();ite!=s.end();ite++){
  cout<<*ite;
}

映射：map

需要添加头文件 “map”，map也是用二叉搜索树维护的集合容器，效率很高O（log(n)）
map就是从key到value的映射，因为重载了[ ]运算符,map像是数组的”高级版”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//声明（int为key，const char*为value）
map<int,const char*>m;
//插入元素
m.insert(make_pair(1,"ONE"));
m.insert(make_pair(10,"TEN"));
m[100]="HUNDRED";
//查找元素
map<int,const char*>::iterator ite;
ite=m.find(1);
puts(ite->second); //(输出)ONE
ite=m.find(2);
if(ite==m.end())puts("not found");
else puts(ite->second);
puts(m[10]);
//删除元素
m.erase(10);
//遍历一遍所有元素
for(ite=m.begin();ite!=m.end();ite++){
 printf("%d: %s\n",ite->first,ite->second);
}

栈

需要添加头文件 “stack”, 一种“后进先出”的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//声明
stack<int> S;
//入栈
S.push(1);
S.push(3);
S.push(5);
cout << S.size() <<endl;//输出栈元素的数量
cout << S.top() << endl;//输出栈顶元素（不删除）
S.pop();//删除栈顶元素
cout << S.top() <<endl;
S.pop();
cout << S.top() <<endl;
S.push(5);
cout << S.top() << endl;
S.pop();
cout << S.top() << endl;

队列

需要添加头文件 “queue”, 一种“先进先出”的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//声明
   queue<int> Q;
   //入队
   Q.push(1);
   Q.push(3);
   Q.push(5);
   cout << Q.size() <<endl;//输出队列元素的数量
   cout << Q.front() << endl;//输出对首元素（不删除）
   Q.pop();//删除队首元素
   cout << Q.front() <<endl;
   Q.pop();
   cout << Q.front() <<endl;
   Q.push(5);
   cout << Q.front() << endl;
   Q.pop();
   cout << Q.front() << endl;

优先队列

STL的优先队列也在“queue”头文件里，是一个“越小的整数优先级越低的优先队列”
出队的方法由front()变为top()，且出队元素不是最先进队的元素
优先队列是可以理解为实现了堆的数据结构，O（logn）

1
2
 //声明
priority_queue<int> pq;

STL也提供了“越小的整数优先级越大的优先队列”

1
2
3
4
5
6
7
8
9
10
11
12
13
 //声明
 priority_queue<int,vector<int>,greater<int> > pq;
 pq.push(3);
 pq.push(5);
 pq.push(1);
 while(!pq.empty()){
     printf("%d\n",pq.top());
     pq.pop();
 }
 //输出
1
3
5

二分查找

在“algorithm”里头文件

1
2
3
4
//lower_bound返回值一般是>= 给定value的iterator
int a[MAX];
int t=lower_bound(a.begin(),a.end(),x)-a//返回的是x的下标，如果没有找到就返回比x小的最大的数的下标，这里查找的范围为[a.begin(),a.end()），又是左闭右开的区间....
//upper_bound返回值则是 > 给定value的iterator，语法跟lower_bound类似

sort排序

sort可以对任意对象排序，即使是自己定义的struct，不过要加判断方法,在“algorithm”头文件里
时间复杂度是O（logn）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int a[MAX];
sort(a,a+n);//对前n个元素进行升序排序

sort（start，end，排序方法)
#include<bits/stdc++.h>
using namespace std;
bool complare(int a,int b)
{
 return a>b;
}
int main()
{
     int a[10]={9,6,3,8,5,2,7,4,1,0};
     for(int i=0;i<10;i++)
     cout<<a[i]<<" ";
     cout<<endl;
     sort(a,a+10,complare);//在这里就不需要对complare函数传入参数了。这是规则
     for(int i=0;i<10;i++)
     cout<<a[i]<<" ";
     return 0;
}
//输出
9 6 3 8 5 2 7 4 1 0
9 8 7 6 5 4 3 2 1 0

unique函数

一个可以删除有序数组中的重复元素,在“algorithm”头文件里
unique的作用是“去掉”容器中相邻元素的重复元素（不一定要求数组有序），它会把重复的元素添加到容器末尾（所以数组大小并没有改变），而返回值是去重之后的尾地址，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
iterator unique(iterator it_1,iterator it_2);
iterator unique(iterator it_1,iterator it_2,bool MyFunc);
//第三个参数是指自定义两个元素相等的规则，类似sort函数
如果想真实删除重复元素可以在调用完unique函数之后，调用erase(it_2,a.end());进行删除

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> a;
    a.push_back(1);
    a.push_back(1);
    a.push_back(13);
    a.push_back(13);
    a.push_back(5);
    a.push_back(6);
    vector<int>::iterator it_1 = a.begin();
    vector<int>::iterator it_2 = a.end();
    vector<int>::iterator new_end;
    sort(it_1,it_2);
    for(int i = 0 ; i < a.size(); i++)
        cout<<a[i]<<" ";
    new_end = unique(it_1,it_2); //注意unique的返回值
    cout<<endl;
    cout<<"调用unique()的 a : ";
    for(int i = 0 ; i < a.size(); i++)
        cout<<a[i]<<" ";
    a.erase(new_end,it_2);
    cout<<endl;
    cout<<"删除重复元素后的 a : ";
    for(int i = 0 ; i < a.size(); i++)
        cout<<a[i]<<" ";
    cout<<endl;
}

reverse

逆转元素

1
2
reverse(start,end)
reverse_copy(start,end,b)//将逆转后的元素存入b数组中

-------------本文结束感谢您的阅读-------------