第九章 STL标准库（二）

目录

• set,multiset,map,multimap

• 容器适配器

• STL算法

set,multiset,map,multimap

1. 常用函数

   find //查找等于某个值的元素（x<y和y<x同时不成立）lower_bound //查找某个下界upper_bound //查找某个上界equal_range //查找等于某个元素的上界和下界，返回pair对象，[lower,upper)count //计算等于某个值的元素个数insert //插入元素或区间，set和map返回值为pair<迭代器,bool>,bool指示原来是否存在该元素erase //删除某个元素

2. 模板声明

   template<class Key,class Pred=less<Key>,class A=allocator<Key> >class multiset{...}template<class Key,class Value,class Pred=less<Key>,class A=allocator<Key> >class multimap{    ... typedef pair<const Key,T> value_type;    ...}mp.insert(multimap<int,double>::value_type(1,3,3));map还具有[]成员函数，返回key对应值的引用；若无该key，则自动插入无参构造函数初始化的元素

容器适配器

1. stack栈：push、pop、top（返回栈顶元素引用）

   //可用vector, deque（默认）, list实现，前两者效果较好template<class T,class Cont=deque<T> >    class stack{...}

2. queue队列：push（队尾）、pop（队头）、top（队头）、back（队尾）

   //可用vector, deque（默认）实现template<class T,class Cont=deque<T> >    class queue{...}

3. priority_queue优先队列：push（进堆）、pop（弹出堆顶）、top（堆顶常引用）

   //可用vector（默认）, deque实现template<class T,class Cont=deque<T>,class Compare=less<T> >    class priority_queue{...}//默认less<T>，堆顶为最大元素

4. stack、queue、priority_queue共同点

• empty() 判断适配器是否为空

• size() 获取适配器元素个数

STL算法

多数重载算法有两个版本

• 通过<或==判断大小

• 通过多出来的类型参数Pred及函数形参Pred op，通过op(x,y)判断

>>详细内容参见北大郭炜课件(课件链接)