容器适配器

• 可以用某种顺序容器来实现(让已有的顺序容器以栈/队列的方式工作)

1) stack: 头文件 < stack >
栈 — 后进先出
2) queue: 头文件 < queue >
队列 — 先进先出
3) priority_queue: 头文件 < queue >
优先级队列 — 最高优先级元素总是第一个出列

都有3个成员函数:

• push: 添加一个元素;
• top: 返回栈顶部或队头元素的引用
• pop: 删除一个元素

容器适配器上没有迭代器——STL中各种排序, 查找, 变序等算法都不适合容器适配器

stack

1. stack 是后进先出的数据结构
2. 只能插入, 删除, 访问栈顶的元素

3. 可用 vector, list, deque来实现

   • 缺省情况下, 用deque实现
   • 用 vector和deque实现, 比用list实现性能好

template
class stack {
…
};

stack 中主要的三个成员函数:

void push(const T & x);
将x压入栈顶
void pop();
弹出(即删除)栈顶元素
T & top();
返回栈顶元素的引用. 通过该函数, 可以读取栈顶
元素的值, 也可以修改栈顶元素

queue

• 和stack 基本类似, 可以用 list和deque实现
• 缺省情况下用deque实现

template
class queue {
……
};

• 同样也有push, pop, top函数

  • push发生在队尾
  • pop, top发生在队头, 先进先出

priority_queue

• 和 queue类似, 可以用vector和deque实现
• 缺省情况下用vector实现

• priority_queue 通常用堆排序技术实现, 保证最大的元
  素总是在最前面

  • 执行pop操作时, 删除的是最大的元素
  • 执行top操作时, 返回的是最大元素的引用
    默认的元素比较器是 less

STL中的函数对象类模板
以下模板可以用来生成函数对象。
equal_to
greater
less
…….
头文件：

greater 函数对象类模板

template
struct greater : public binary_function {
bool operator()(const T& x, const T& y) const 
    {
    return x > y;
    }
};

greater 的应用

list 有两个sort成员函数

 void sort();

multimap

template
class multimap {
….
typedef pair value_type;
…….
}; //Key 代表关键字的类型

• multimap中的元素由 组成，每个元素是一个pair对象，关键字
  就是first成员变量,其类型是Key
• multimap 中允许多个元素的关键字相同。元素按照first成员变量从小到大排列，缺省情况下用 less 定义关键字的“小于”关系。

#include 
#include 
using namespace std;

int main()
{
    typedef multimap mmid;
    mmid pairs;
    cout score;
            MAP_STD::iterator p=mp.lower_bound(score);
            //查找一个最大的位置it，是的[begin(),it)中所有元素的first都比value小。
            if(p!=mp.begin())
            {
                --p;
                score=p->first;
                //比要查询分数低的最高分
                MAP_STD::iterator maxp=p;
                int maxId=p->second.id;
                for(; p!=mp.begin()&&p->first==score; --p)
                {
                    //遍历所有成绩和score相等的学生
                    if(p->second.id>maxId)
                    {
                        maxp=p;
                        maxId=p->second.id;
                    }
                }
                if(p->first==score)
                {
                    //如果上面循环是因为p==mp.begin()
                    //而终止，则p指向的元素还要处理
                    if(p->second.id>maxId)
                    {
                        maxp=p;
                        maxId=p->second.id;
                    }
                }

set和multiset

 内部元素有序排列，新元素插入的位置取决于它的值，查找速度快。

 除了各容器都有的函数外，还支持以下成员函数：

• find: 查找等于某个值 的元素(x小于y和y小于x同时不成立即为相等)
• lower_bound : 查找某个下界
• upper_bound : 查找某个上界
• equal_range : 同时查找上界和下界
• count :计算等于某个值的元素个数(x小于y和y小于x同时不成立即为相等)
• insert: 用以插入一个元素或一个区间

multiset

template
class multiset { …… };

• Pred类型的变量决定了multiset 中的元素，“一个比另一个小”是怎么定义的。multiset运行过程中，比较两个元素x,y的大小的做法，就是生成一个 Pred类型的变量，假定为 op,若表达式op(x,y) 返回值为true,则 x比y小。
  Pred的缺省类型是 less。
• less 模板的定义：

template
struct less : public binary_function
{ bool operator()(const T& x, const T& y) { return x < y ; } const; };
//less模板是靠 < 来比较大小的

multiset 的成员函数

iterator find(const T & val);
// 在容器中查找值为val的元素，返回其迭代器。如果找不到，返回end()。

iterator insert(const T & val);
// 将val插入到容器中并返回其迭代器。

void insert( iterator first,iterator last); 
// 将区间[first,last)插入容器。

int count(const T & val);
//  统计有多少个元素的值和val相等。

iterator lower_bound(const T & val);
// 查找一个最大的位置 it,使得[begin(),it) 中所有的元素都比 val 小。

iterator upper_bound(const T & val);
// 查找一个最小的位置 it,使得[it,end()) 中所有的元素都比 val 大。

pair equal_range(const T & val);
// 同时求得lower_bound和upper_bound。

iterator erase(iterator it);
//删除it指向的元素，返回其后面的元素的迭代器(Visual studio 2010上如此，但是在C++标准和Dev C++中，返回值不是这样)。

multiset 的用法

#include 
#include 
#include 
using namespace std;

template
void Print(T first, T last)
{
    for(; first != last; first++)

List容器

双向链表#include < list >

• 在任何位置插入和删除都是常数时间
• 不支持根据下标随机存取元素
• 具有所有顺序容器都有的成员函数

List容器还支持的8个成员函数：

1. Push_front() :在链表最前面插入
2. Pop_front():删除链表最前面的元素
3. Sort()：排序（list不支持STL算法sort,因为不支持随机访问迭代器）
4. Remove()：删除和指定值相等的所有元素
5. Unique()：删除所有和前一个元素相同的元素
6. Merge()：合并两个链表，并清空被合并的链表
7. Reverse()：颠倒链表，逆序
8. Splice()：在指定位置前面插入另一链表中的一个或多个元素，并在另一链表中删除被插入的元素

List容器的sort函数

• List容器的迭代器不支持完全随机访问,不能用标准库中的sort函数对它进行排序,List自己的sort成员函数:

List classname
Classname.sort(compare); //compare函数可以自己定义
Classname.sort(); //无参数版本，按照 0)
    {
        typename list::const_iterator it;
        //" typename "是一个C++程序设计语言中的关键字。 当用于泛型编程时是另一术语" class "的同义词。
        //这个关键字用于指出模板声明（或定义）中的非独立名称（dependent names）是类型名，而非变量名。
        for( it = lst.begin(); it != lst.end(); it++)
        {

• 可变长的动态数组
• 必须包含头文件 #include < vector >
• 所有STL算法 都能对vector操作

支持随机访问迭代器

* 根据下标随机访问某个元素时间为常数
* 在尾部添加速度很快
* 在中间插入慢

vector的成员函数

• 构造函数初始化

• 其他常用函数

#include 
#include 
#include 
using namespace std;

int main()
{
    int a[5] = {1, 2, 3, 4, 5};
    vector v(5);//每个初始化为0