C++适配器的使用总结

原 作者 冯鑫 | 发表于 | 分类于 2015级

C++标准库定义了三个顺序容器的适配器：stack、queue和priority_queue。它们分别是栈适配器、队列适配器和优先队列适配器。适配器是标准库中的一个通用概念。容器、迭代器和函数都有适配器。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。
在我看来，这三个容器适配器其实就是把指定的顺序容器包装成我们想用到的数据结构类型，我们只需要把它当成我们想要的数据结构进行操作就行，并不需要关心内部的实现细节，因为这些适配器都帮我们做好了。

所有适配器都支持的操作：

操作 解释
A a; 创建一个名为a的空适配器
A a(c); 创建一个名为a的适配器，带有容器c的一个拷贝
关系运算符 每个适配器都支持所有关系运算符，这些运算符返回底层容器的比较结果
a.empty() 若a包含任何元素，返回false,否则返回true
a.size() 返回a中的元素数目
swap(a,b) 交换a和b的内容，a和b必须有相同的类型，包括底层容器类型也必须相同


定义一个适配器

每个适配器都定义两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。例如，假定deq是一个deque<int>,我们可以用deq来初始化一个新的stack，如下所示：

stack<int> stk(deq);   //从deq拷贝元素到stk

默认情况下，stack和queue是基于deque实现的，priority_queue是在vector之上来实现的。我们可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。

//在vector上实现的空栈
stack<string,vector<string> > str_stk;
//str_str2在vector上实现，初始化时保存svec的拷贝
stack<string,vector<string> > str_stk2(svec);

PS：对于一个给定的适配器，可以使用哪些容器是有限制的。所有适配器都要求容器具有添加和删除元素的能力。因此，适配器不能构造在array之上。类似的，我们也不能用forward_list来构造适配器，因为所有适配器都要求容器具有添加、删除以及访问尾元素的能力。
stack可以使用除array和forward_list之外的任何容器类型来构造stack。
queue适配器可以构造于list或deque之上，但不能基于vector构造。
priority_queue可以构造于vector或deque之上，但不能基于list构造。
其实，每个适配器的默认构造容器性能什么的都已经不错了，我们没有必要自己去重载默认容器类型，使用默认的就可以了。


每个容器适配器都基于底层容器类型的操作定义了自己的特殊操作。我们只可以使用适配器操作，而不能使用底层容器类型的操作。

栈适配器

通用操作中未列出的栈操作：

操作 解释
s.pop() 删除栈顶元素，但不返回该元素值
s.push(item) 创建一个新元素压入栈顶，该元素通过拷贝或移动item而来，或者由args构造
s.emplace(args)
s.top() 返回栈顶元素，但不将元素弹出栈


stack类型定义在stack头文件中。代码示例如下：

stack<int> intStack;  //空栈

for(size_t ix=0;ix!=10;ix++)
    intStack.push(ix);   //intStack保存0-9十个数
while(!intStack.empty()) { //intStack中有值就继续循环
    int value = intStack.top();
    intStack.pop();
    }


queue队列适配器

queue类型定义在queue头文件中。

未列出的queue操作：

操作 解释
q.pop() 出队，弹出首元素
q.front() 返回首元素，但不删除此元素
q.back() 返回尾元素
q.push(item) 在queue队列末尾插入一个元素，其值为item
q.emplace(args) 在queue队列末尾插入一个元素，由args构造

queue就是我们数据结构中常说的队列，是一种先进先出的存储和访问策略。
简单的代码示例：

int main()  
{  

    int e,n,m;  

    queue<int> intQueue;  

    for(int i=0;i<10;i++)  

       intQueue.push(i);  

     while(!intQueue.empty()) {
        int value=intQueue.front();
        intQueue.pop();
        cout<<value<<endl;
        }
    return 0;
}


优先队列

前面介绍过,queue队列是先进先出的存储和访问策略的数据结构。比如我们排队买饭，先到的先买到饭先走。
但有时候我们需要定义一个优先级，优先级高的先出队，而不是按照先来的顺序。这就是优先队列。
比如饭店按照客人预订时间而不是来到的时间的早晚来为他们安排座位，先预订的优先级高，先被安排。

priority_queue就是标准库为我们提供的优先队列适配器。
priority_queue操作：

操作 解释
a.pop 弹出优先队列中最高优先级的元素
q.top() 返回最高优先级元素，但不删除元素，只适用于优先队列
q.push(item) 在priority_queue的恰当位置创建一个元素，值为item
q.emplace(args) 在恰当位置构造一个元素，由args构造

优先队列也是定义在queue头文件中。
priority_queue<int>pq 默认是按照值从大到小的优先级排列的，代码如下：

#include<iostream>
#include<queue>
using namespace std;


int main()
{
    priority_queue<int> pq;

    for(int i=0;i<10;i++)
        pq.push(i);
    while(!pq.empty())
    {
        int value = pq.top();
        pq.pop();
        cout<<value<<" ";
    }
    return 0;
}

运行结果：
9 8 7 6 5 4 3 2 1 0

如果我们想按照int值从小到大的优先级排列怎么办？其实，qriority_queue跟sort函数类似，我们可以向函数中传入可调用对象，这样函数就可以按照我们想要的顺序进行排列。qriority_queue初始化时，第三个参数就是我们要传的可调用对象。
对于一些常见的优先队列，STL提供了更为简单的定义方法。“越小的整数优先级越大的优先队列”我们可以写成priority_queue<int,vector<int>,greater<int> > pq来定义，代码如下：

#include<iostream>
#include<queue>
using namespace std;


int main()
{
    priority_queue<int,vector<int>,greater<int> > pq;

    for(int i=0;i<10;i++)
        pq.push(i);
    while(!pq.empty())
    {
        int value = pq.top();
        pq.pop();
        cout<<value<<" ";
    }
    return 0;
}

运行结果：
0 1 2 3 4 5 6 7 8 9

其实，第一个列子中priority_queue<int> pq默认是按照值从大到小的优先级排列的，等同于priority_queue<int,vector<int>,less<int> > pq。

同样，我们可以用自定义的可调用对象传入第三个参数，来实现我们“越小的整数优先级越大的优先队列”。
代码如下：

#include<iostream>
#include<queue>
using namespace std;

struct cmp{

    bool operator () (const int a,const int b)
    {
       return a>b;
    }
};

int main()
{
    priority_queue<int,vector<int>,cmp> pq;

    for(int i=0;i<10;i++)
        pq.push(i);
    while(!pq.empty())
    {
        int value = pq.top();
        pq.pop();
        cout<<value<<" ";
    }
    return 0;
}

运行结果：
0 1 2 3 4 5 6 7 8 9

自定义类型也可以组成优先队列，但必须为每个元素定义一个优先级。这个优先级并不需要一个确定的数字，只需要能比较大小就可以。所以，我们需要为我们自定义的类型重载比较运算符。

代码示例如下：

按照z的值从大到小输出：

#include <iostream>
#include <queue> 
using namespace std;

class T {
public:
    int x, y, z; 
    T(int a, int b, int c):x(a), y(b), z(c) {}
};

bool operator < (const T &t1, const T &t2) 
{
    return t1.z < t2.z; // 按照z的顺序来决定t1和t2的顺序
}

int main()
{ 
     priority_queue<T> q; 
     q.push(T(4,4,3)); 
     q.push(T(2,2,5)); 
     q.push(T(1,5,4)); 
     q.push(T(3,3,6)); 
     while (!q.empty()) 
     { 
         T t = q.top(); 
         q.pop(); 
         cout << t.x << " " << t.y << " " << t.z << endl; 
     } 
     return 0; 
}

运行结果：
//按照z的值从大到小输出
3 3 6
2 2 5
1 5 4
4 4 3

按照z的值从小到大输出：

#include <iostream>
#include <queue> 
using namespace std;

class T {
public:
    int x, y, z; 
    T(int a, int b, int c):x(a), y(b), z(c) {}
};

bool operator > (const T &t1, const T &t2) 
{
    return t1.z > t2.z; // 按照z的顺序来决定t1和t2的顺序
}

int main()
{ 
     priority_queue<T,vector<T>,greater<T> > q; 
     q.push(T(4,4,3)); 
     q.push(T(2,2,5)); 
     q.push(T(1,5,4)); 
     q.push(T(3,3,6)); 
     while (!q.empty()) 
     { 
         T t = q.top(); 
         q.pop(); 
         cout << t.x << " " << t.y << " " << t.z << endl; 
     } 
     return 0; 
}

运行结果：
4 4 3
1 5 4
2 2 5
3 3 6