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);