C with STL 总结

STL(Standard Template Library) 意为标准模板库,其中封装了很多实用的容器。虽然没写过大一点儿的C++项目,但知道这玩意儿拿来刷OJ特别的好用。此帖总结一下STL的用法。

vector

vector使用为“变长数组“,免去了C中数组超内存的弊端。

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
35
36
37
#include<vector>
using namespace std;
vector<typename> name;

//typename 可以是任何基本类型:int、double、char、structure..
//也可以是stl容器,但要>>要加上空格否则会被认为是移位符号
vector<vector<int> > name;

//访问方法
//1.通过下标访问 2.通过迭代器访问
vector<int> vi;
int x = vi[1];

vector<int>::iterator it = vi.begin();
for(int i=0;i<5;i++)
printf("%d ",*(it+i));
//迭代器不支持<vi.end()操作,但可以用!=vi.end()
//vi.end()并不是vi最后一个元素的地址,而是最后一个元素的下一个地址。
for(vector<int>::iterator it=vi.begin();it!=vi.end();it++)
printf("%d",*it);
//在迭代器中只有vector和string才支持vi.begin()+3 的写法

//常用函数
//push_back() 后端新增一个元素 O(1)
//pop_back() 弹出一个元素 O(1)
//size() 获取元素个数 O(1)
//clear() 清除所有元素 O(N)
//insert() 任意迭代器位置插入元素 O(N)
//erase() 删除单个元素或一个区间类的元素 O(N)

vi.push_back(number);
vi.pop_back();
vi.size();
vi.clear();
vi.insert(vi.begin()+2,number);
vi.erase(vi.begin()+2);
vi.erase(vi.begin(),vi.begin()+5);//前开后闭区间

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
#include<set>
using namespace std;
set<typename> name;

set<int> st;
//访问:只能通过迭代器
for(set<int>::iterator it=st.begin();it!=st.end();it++)
printf("%d",*it);

//常用函数
//inster() O(logN)
//find() O(logN) 返回对应值的迭代器
//erase() 迭代器:O(1) 值:O(logN) 区间:O(last-first)
//size() O(1)
//clear() O(N)

st.insert(number);
st.find(number);
st.erase(it);
st.erase(st.find(number));
st.erase(number);
st.erase(it,st.end());
st.size();
st.clear();

string

改进了C语言的字符串。

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
35
36
37
38
39
40
41
42
43
#include<string>
using namespace std;

string str;
string str = "abcddd";
//访问: 1.通过下标 2.通过迭代器
//若要读入和输出字符串需要用cin、cout
str[i];
for(string::iterator it=str.begin();it!=str.end();it++)
printf("%c",*it);
//c_str(): string转换为字符数组
printf("%s",str.c_str());

//常用函数
//+ 拼接
//==、!=、<、<=、>、>= 字典序比较
//length()/size() 大小 O(1)
//insert(pos,string) insert(it,it2,it3) 插入 O(N)
//erase(it) erase(first,last) erase(pos,length) O(N)
//clear() O(N)
//substr(pos,len) 返回长度len的子串 O(len)
//find() 查找子串
//replace() 子串替换

str3=str1+str2;
str1+=str2;

str1.insert(3,str2);//在str[3]开始插入str2
str1.insert(str1.begin()+3,str2.begin(),str2.end());//在str1的it位置插入[it2,it3)的内容

str1.erase(str1.begin()+1);
str1.erase(str1.begin()+1,str1.end()-1);
str1.erase(3,2);//从三号位置开始删除2个字符

str1.clear();

str1.substr(5,6);//返回位置5开始的长度为6的子串

str1.find(str2);//寻找str2在str1第一次出现的位置,如果str2不是str1的子串,返回string::npos(实际上就是-1)
str1.find(str2,pos);//从pos位置开始寻找str2

str1.replace(10,4,str2);//从str1的10号位开始,长度为4的子串替换为str2
str1.repalce(str1.begin(),str1.begin()+5,str2);

map

map翻译为映射。传统的数组只支持int->任何类型的映射,而map能支持任何类型->任何类型的映射。除此之外,若使用哈希表时索引间距很大,例如第一个元素是0 下一个是10000 中间的就浪费了,这种情况下map的优势就显现出来了。

映射前类型称为键key,映射后类型为值value。

map内部是红黑树实现,也拥有从大到小排序的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<map>
using namespace std;
map<typename1,typename2> name;
map<string,int> mp;

//访问:1.下标 2.迭代器
//迭代器可以同时访问key和value,分别为it->first,it->second
map<char,int> mp;
mp['c']=100;
for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++)
printf("%c,%d\n",it->first,it->second);

//常用函数
//find(key) 返回迭代器 O(logN)
//erase()
//size() O(1)
//clear() O(N)
mp<char,int>::iterator it = mp.find('b');
mp.erase(it);
mp.erase('b');
mp.erase(mp.begin(),mp.end());

queue

队列 first in first out

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<queue>
using namespace std;
queue<typename> name;
queue<int> q;
//访问:只能访问队首元素和队尾元素
q.front();
q.back();
//常用函数
//push() 入队 O(1)
//front() back() O(1)
//pop() 出队 O(1)
//empty() 检测是否为空 true/false O(1)
q.push(123);
//使用front/back之前要判断是否为空,防止出错
if(q.empty()==false)
q.pop();

priority_queue

优先队列,依据优先级,队首一定是优先级最高的那一个。底层用堆来实现。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<queue>
using namespace std;
priority_queue<typename> name;
priority_queue<int> q;

//访问:只能访问堆顶元素
q.top();
//常用函数
//push() O(logN)
//top() O(1)
//pop() O(logN)
//empty() O(1)
//size() O(1)

//优先级
//基本数据类型(int\double\char):默认越大优先级越高
priority_queue<int,vector<int>,less<int>> q;
//vector<int> 用来承载底层数据结构堆 heap
//less<int> 数字越大优先级越大 greater<int> 数字越小优先级越大

//结构体 重载
//对 > 重载会导致编译错误,重载 < 即可
struct fruit{
string name;
int price;
friend bool operator < (fruit a, fruit b){
return a.price < b.price;
}
};
//此时< 还是小于的作用
priotity_queue<fruit> q; //价格高在top

//结构体外的写法

struct cmp{
bool operator() (fruit a, fruit b){
return a.price > b.price;
}
};
prority_queue<fruit,vector<fruit>,cmp> q; //此时top为最低价格

//结构体庞大 使用引用提高效率
friend bool operator < (const fruit &a, const fruit &b){
return a.price < b.price;
}

bool operator () (const fruit &a, const fruit &b){
return a.price < b.price;
}

stack

栈 first in last out

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stack>
using namespace std;
stack<typename> name;
stack<int> st;
//访问:只能通过top访问栈顶
st.top();

//常用函数
//push() O(1)
//top() O(1)
//pop() 弹出栈顶 O(1)
//empty()
//size()

pair

如果一个结构体内只有两个元素,pair是很好很方便的替代品。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<utility>
using namespace std;
pair<typename1,typename2> name;

pair<string,int> p;
//初始化
pair<string,int> p("string",10);
//访问 first 和 second
p.first = "string";
p.second = 10;
//临时构建pair
pair<string,int>("string",10);
make_pair("string",5);

//比较: 先比较first 若first相等 再比较second

//pair可以作为map键值对进行插入

map<string,int> mp;
mp.insert(make_pair("hello",5));

algorithm

algorithm 中有很多常用的函数,可以缩短编码时间,提高效率

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<algorithm>
using namespace std;
max(x,y);
abs(x);//必须为整型
fabs(f);//浮点型 需要<math>
swap(x,y);//交换xy的值

int a[10]={1,2,3,4,5,6,7,8,9,10};
reverse(a,a+4);//将a[0]~a[3]反转

next_permutation();//给出全排列中的下一个序列,当到达最后一个时返回false
do{
printf("%d%d%d\n",a[0],a[1],a2]);
}while(next_permutation(a,a+3));
/*
123
132
213
231
312
321 */

fill();//为数组或容器某个区间赋相同值
//memset 只能赋01 fill为任意值
fill(a,a+10,123);



sort(a,a+4);//sort(首元素地址,尾元素的下一地址,可选比较函数),默认从小到大

//例如int 从大到小排序

bool cmp(int a, int b)
{
return a>b;
}
sort(a,a+4,cmp);

//对结构体

struct node{
int x,y;
}ssd[10];

bool cmp(node a,node b){
if(a.x!=b.x) return a.x > b.x;
else return a.y < b.y;
}
//先按照x从大到小排序,再按照y从小打大排序
sort(ssd,ssd+10,cmp);

//容器排序
vector<int> vi;
bool cmp(int a, int b){
return a>b;
}
sort(vi.begin(),vi.end(),cmp);


lower_bound(first,last,val);//用于寻找[first,last)中第一个值>=val元素的位置,数组返回指针,容器返回迭代器
upper_bound(first,last,val);//寻找[first,last)中第一个值>val元素的位置
//若找不到该值,则返回 “应该” 插入该元素的位置

int a[10]={1,2,2,3,3,3,5,5,5,5};
lower_bound(a,a+10,-1); // 0
lower_bound(a,a+10,1); // 0
upper_bound(a,a+10,1); // 1
upper_bound(a,a+10,6); // 10

参考: 《算法笔记》

Copyright © 2011 - 2018 活在梦里 All Rights Reserved.

myth 保留所有权利