STL基本操作

STL全称Standard Template Library,是C++中的标准模板库;

容器

序列式容器

容器 vector deque list
头文件 <vector> <deque> <list>
begin
end
size
empty
front
back
operator[] ×
insert
erase
push_back
pop_back
push_front ×
pop_front ×
clear
swap
remove × ×
unique × ×
merge × ×
sort × ×
reverse × ×

介绍

vector:动态数组;
deque:双向队列;
list:链表;

定义

(std::)容器类型<数据类型> 容器名称;(适用于vector,deque,list)

1
2
3
4
5
6
7
8
9
10
11
12
#include <vector>
#include <deque>
#include <list>

using namespace std;

int main()
{
vector<int> vct;
deque<float> dq;
list<char> lst;
}

迭代器函数

begin/end

begin:容器内首元素的迭代器;(适用于vector,deque,list)
end:容器内尾元素的迭代器+1;(适用于vector,deque,list)

1
2
3
4
5
vector<int>::iterator it;   //定义一个vector的迭代器;
for(it=vct.begin(); it!=vct.end(); it++)
{
cout<<*it<<" "; //通过迭代器顺序输出vct中元素;
}

容量函数

size

容器的大小(容器中元素的个数);(适用于vector,deque,list)

1
vct.size(); //得到vct的大小;

empty

容器是否为空;(适用于vector,deque,list)

1
bool flag=vct.empty();  //用flag存储vct是否为空;

元素访问

front/back

front:首元素;(适用于vector,deque,list)
back:尾元素;(适用于vector,deque,list)

1
int a=vct.front(),b=vct.back(); //把vct的首,尾元素赋值给a,b;

中括号[]

下标;(适用于vector,deque)

1
2
3
4
for(int i=0; i<vct.size(); i++)
{
cout<<vct[i]<<" "; //像数组一样以下标访问元素;
}

调节器

insert/erase

insert:插入元素;(适用于vector,deque,list)
erase:删除元素;(适用于vector,deque,list)

1
2
3
vct.insert(it,10);  //在vct中迭代器it的位置插入元素10;

vct.erase(it); //删除迭代器it处的元素;

push_back/pop_back/push_front/pop_front

push_back:容器最后加入元素;(适用于vector,deque,list)
pop_back:容器最后删除元素;(适用于vector,deque,list)
push_front:容器最前加入元素;(适用于deque,list)
pop_front:容器最前删除元素;(适用于deque,list)

1
2
3
4
5
vct.push_back(10);  //在vct尾部加一个元素10;
vct.pop_back(); //删除vct的最后一个元素;

dq.push_front(10); //在dq的头部加一个元素10;
dq.pop_front(); //删除dq的第一个元素;

clear

清空容器;(适用于vector,deque,list)

1
vct.clear();    //删除掉vct中所有元素;

swap

交换两个容器中的元素;(适用于vector,deque,list)

1
vct1.swap(vct2);    //交换vct1与vct2;

链表操作

remove

删除链表中某个值的元素;(适用于list)

1
lst.remove(10); //删除链表中所有值为10的元素;

unique

对排序好的链表进行去重;(适用于list)

1
lst.unique();   //去重;

merge

合并两个排序好的链表,合并后的链表排序方式与原链表相同;(适用于list)

1
lst1.merge(lst2);   //合并后放入lst1,lst2为空;

sort

对链表进行排序;(适用于list)

1
lst.sort(); //链表内元素从小到大排序;

reverse

把链表中元素反转;(适用于list)

1
lst.reverse();  //反转lst中的元素;


适配器容器

容器 stack queue priority_queue
头文件 <stack> <queue> <queue>
empty
size
top ×
front × ×
back × ×
push
pop

介绍

stack:栈,先入后出的数据结构;
queue:队列,先入先出的数据结构;
priority_queue:优先队列,把满足条件的元素(默认最大值)作为队首的队列;

定义

规则基本同序列容器

1
2
3
4
5
6
7
8
9
10
11
12
#include <stack>
#include <queue>

using namespace std;

int main()
{
stack<int> stk;
queue<float> q;
priority_queue<char> pq;
return 0;
}

函数

1
2
3
4
5
6
7
stk.empty();
stk.size();
stk.top();
q.front();
q.back();
stk.push();
stk.pop();

关联式容器

容器 set multiset map multimap
头文件 <set> <set> <map> <map>
begin
end
size
empty
operator[] × × ×
insert
erase
clear
swap
count
find

介绍

set:集合,自动对容器中的元素进行排序与去重;
multiset:多重集合,自动对容器中的元素进行排序;
map:映射,使两组元素产生一一对应的关系,并对前一组元素进行排序与去重;
multimap:多重映射,使两组元素产生一一对应的关系,并对前一组元素进行排序;

定义

set系规则同之前两类,而map系因其有两组元素而特殊;
map<数据类型1(key),数据类型2(value)> 容器名称;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <set>
#include <map>
#include <string>

using namespace std;

int main()
{
set<int> st;
multiset<float> mst;
map<char,double> mp;
multimap<string,long long> mmp;
return 0;
}

迭代器

begin/end

调用方法与之前序列容器时所说一致;
值得注意的是,map系的元素值不能通过*it(迭代器)来访问,而需要it->first和it->second来分别访问key与value;

1
2
3
map<int,int>::iterator it;
it=mp.begin();
cout<<it->first<<"=>"<<it->second;

容量函数

size,empty

使用方法如前所述;

1
2
st.size();
st.empty();

元素访问

中括号[]

仅map可用,可以mp[key]的形式访问value;

1
2
3
4
map<char,int> mp;
mp['a']=1;
mp['b']=2;
cout<<map['a'];

调节器

insert/erase

1
2
3
4
5
6
st.insert(10);  //插入一个值为10的元素;
mp.insert(pair<char,int>('a',1)); //插入一对值为('a',1)的元素;

st.erase(it1); //删去迭代器it1位置的元素;
st.erase(10); //删去值为10的元素;
mp.erase('a'); //删去key值为'a'的元素;

clear,swap

使用方法如前所述;

1
2
st.clear();
st1.swap(st2);

操作

count

计算容器中某元素出现的次数;

1
2
st.count(10);   //得到st中10的个数;
mp.count('a'); //得到mp中key为'a'的元素个数;

find

查找容器中是否含有某个元素,若有,返回其迭代器,没有,则返回end;

1
2
3
4
5
6
7
8
9
10
11
12
set<int>::iterator it1;
map<char,int>::iterator it2;
it1=st.find(10); //查找st中是否有10;
it2=mp.find('a'); //查找mp中是否有key为'a'的元素;
if(it2!=mp.end())
{
cout<<it2->second; //如果找到,输出其value;
}
else
{
cout<<"NO"; //找不到,输出"NO";
}


算法

非修改序列操作

find

1
it=find(it1,it2,x);

count

1
n=count(it1,it2,x);

修改序列操作

swap

1
swap(a,b);

unique

1
unique(it1,it2);

reverse

1
reverse(it1,it2);

排序

sort

1
sort(it1,it2);

二分查找

lower_bound/upper_bound

1
2
it3=lower_bound(it1,it2,a);
it4=upper_bound(it1,it2,b);

最值

min/max

1
2
min(a,b);
max(a,b);