STL常用容器用法

-1.

本文章中所有函数原型均为C++98的标准。

通用的操作

//遍历容器——以vector,map为例

vector<int> vt;

map<int,int> mp;

for(vector<int>::iterator it=vt.begin();it!=vt.end();it++)printf("%d ",*it);

printf("\n");

for(map<int,int>::iterator it2=mp.begin();it2!=mp.end();it2++)printf("%d %d\n",it2->first,it2->second);

//empty(),size()和clear()函数通用——以queue为例

queue<int> q;

while(!q.empty){//do sth}

printf("%d\n",q.size());

q.clear();

list

list<int> ls;

//一些简单的功能

ls.push_front(3);//3

ls.push_front(4);//4 3

ls.push_back(5);//4 3 5

ls.pop_front();//3 5

printf("%d %d\n",ls.front(),ls.back());//3 5

ls.pop_back();//3

//最为重要的功能——O(1)插入（给定位置和数值）和删除（给定位置）

list<int>:iterator it=ls.begin();

ls.insert(it,2);//2 3

//注意：新的数插入到迭代器之前的位置；但迭代器依旧指向3

ls.erase(it);//2

//迭代器会指向被删除数的后面

//这里it==ls.end()

queue&stack&vector

十分常用且过于简单，略。

注意在执行pop等操作时要判空。

vector不能访问超出范围的下标，会直接报错。

priority_queue

看这里

注意priority_queue是一个堆，因此要用top()；而queue就是front()和back()。

deque

写单调队列的时候要用……其他的就没什么用处了吧

函数名基本同list中“简单的功能”

(multi)set

unordered_开头的东西似乎csp/noip都不太能用，而且有被卡的风险（悲

(multi)set和之后的(multi)map内部都是用红黑树实现，故基本都是log级别的

set和multiset使用起来比较简单，它们支持的函数也都相同（只不过有些在set里没用）

注意有重复元素的时候要用multiset，别被set的自动去重坑了=_=

set和multiset的insert和erase都能直接指定值，不需要给定迭代器（即位置）。

但是multiset的erase会直接把所有是指定值的都删掉。这可能不是我们所期望的。

解决这个问题的方法就是用find()（下面会说）找到一个值并且直接单独给定迭代器删除即可。

但是，(multi)set的最为有用的操作还是下列五个函数：

iterator find (const value_type& val) const;

size_type count (const value_type& val) const;

iterator lower_bound (const value_type& val) const;

iterator upper_bound (const value_type& val) const;

pair<iterator,iterator> equal_range (const value_type& val) const;

接下来一个一个予以剖析。

首先是find()、equal_range()和count()函数。

find()只会找到一个值所对应的迭代器（这就是为什么上面的操作成立的理由）；

而equal_range()会直接将所有对应的值的迭代器都找出来，并返回首和尾方便迭代。

至于count()显然就是统计数量了。

显然，set中只有count()（或find()，看个人习惯）判定元素是否在set中有用，而multiset中三个都有用处。

另外需要注意，equal_range()返回的pair的second实际上会比对应的值往后一格，这样方便迭代。具体代码如下：

multiset<int> st;

st.insert(10);st.insert(10);st.insert(20);st.insert(20);

st.insert(30);st.insert(30);st.insert(30);st.insert(30);

pair<multiset<int>::iterator,multiset<int>::iterator> qwq;

qwq=st.equal_range(30);

for(multiset<int>::iterator it=qwq.first;it!=qwq.second;it++)printf("%d ",*it);//30 30 30 30

接下来是lower_bound()和upper_bound()。

这两个函数都已经熟知了，一个返回第一个不小于，一个返回第一个大于。

另外注意返回的是迭代器而不是值。

(multi)map

所拥有的函数和(multi)set基本相同。

但是要注意(multi)map中的一个值是包含了key和value两部分，因此操作会复杂一点。

同时，由于一个value可能会对应多个key，故不支持通过value快速找key。

遇到这种情况，通常需要建立一正一反两个(multi)map。

另外要注意，通过迭代器访问元素时，要使用：

it->first

it->second

map的常用函数：

mapped_type& operator[] (const key_type& k);//用map[key]=value的形式插入元素

pair<iterator,bool> insert (const value_type& val);//不常用，插入元素用上面的[]运算符就行。

//但是注意这个函数的返回值，insert函数会返回是否已经有了对应的key，和已经对应的迭代器

void erase (iterator position);//通过迭代器删除

size_type erase (const key_type& k);//通过key删除

size_type count (const key_type& k) const;//用来判定map中是否有key

multimap的常用函数：

iterator insert (const value_type& val);//multimap中不支持[]运算符，故只能通过insert插入。

map.insert(make_pair(key,value));//具体方法

void erase (iterator position);//通过迭代器删除（删一个）

size_type erase (const key_type& k);//通过key删除（所有key对应的value全删）

iterator find (const key_type& k);//返回一个key对应的iterator

size_type count (const key_type& k) const;//同(multi)set

iterator lower_bound (const key_type& k);//都是通过key来找的

iterator upper_bound (const key_type& k);

pair<iterator,iterator> equal_range (const key_type& k);//好东西。给出了key所对应的全部value所在的区间。

巴特西

STL常用容器用法

最新文章

热门文章