适配器

基本概念

适配器就是Interface(接口)，对容器、迭代器和算法进行包装，但其实质还是容器、迭代器和算法，只是不依赖于具体的标准容器、迭代器和算法类型，容器适配器可以理解为容器的模板，迭代器适配器可理解为迭代器的模板，算法适配器可理解为算法的模板。

本质

适配器是使一事物的行为类似于另一事物的行为的一种机制。

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

分类

• 容器适配器：stack、queue、priority_queue
• 迭代器适配器：reverse_iterator、insert_iterator、front_insert_iterator、back_insert_iterator
• 算法适配器：bind1st、bind2nd、not1、not2、mem_fun、mem_fun_ref

函数适配器也是算法适配器。

容器适配器

容器适配器是一种封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。

怎么理解容器适配器？

1. 适配器底层没有自己的数据结构，它是另外一个容器的封装，它的方法底层全都依赖另一个容器的方法；
2. 没有自己的迭代器

容器适配器也是标准容器的一部分。

容器适配器包含：

• stack：栈容器。依赖deque容器，是对deque容器的封装。
• queue：队列容器。依赖deque容器，是对deque容器的封装。
• priority_queue：优先级队列容器。依赖vector容器，是对vector容器的封装。

为什么stack和queue底层依赖的是deque容器，而priority_queue底层依赖的却是vector容器？

容器底层依赖什么数据结构还是跟容器自身的特性有关。

• stack是一种栈容器，首先来说栈是一种FILO先进后出的数据结构，需要频繁的对尾部进行操作。
• queue是一种队列容器，队列是一种FIFO先进先出的数据结构，需要频繁的对头部和尾部进行操作。

基于以上分析，栈容器底层也可以依赖vector容器。但是，vector容器在创建容器对象后不分配空间而随着元素的插入一点点的进行2倍扩容，扩容过程又涉及旧数据的拷贝工作，是比较耗费资源的，如果插入时需要扩容那么本次插入的时间复杂度就是O(n)，不如deque容器插入删除操作时间复杂度都是O(1)；并且vector容器在内存需求上需要的是连续的内存空间，不如deque容器的链式结构可以有效的利用内存空间。vector的优势在随机访问上，但是stack和queue容器的特性导致这两种容器都不允许进行随机访问。综合分析vector并没有什么优势，在stack和queue容器的底层封装的选择上，deque确实比较适合。

而priority_queue底层依赖vector容器是因为其底层默认是大根堆，而要实现大根堆需要依赖内存连续的数据结构，所以其底层才会封装vector容器。

栈

stack是一种先进后出(First In Last Out, FILO)的数据结构，它只有一个出口，形式如图所示。stack容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。

有元素推入栈的操作称为push；将元素推出stack的操作称为pop。

stack没有迭代器

stack所有元素的进出都必须符合”先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。stack不提供遍历功能，也不提供迭代器。

队列

Queue是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口，queue容器允许从一端新增元素，从另一端移除元素。

queue没有迭代器

Queue所有元素的进出都必须符合”先进先出”的条件，只有queue的顶端元素，才有机会被外界取用。Queue不提供遍历功能，也不提供迭代器。

优先级队列

优先级队列容器，插入容器中的队列默认会从大到小进行排列。优先队列底层使用的堆排序，默认使用的是大根堆。

思考题：可以回顾大根堆的创建、调整过程？

priority_queue没有迭代器

因为其是容器适配器的一种，所以并不提供迭代器，队列的特性导致其不能够被遍历，要想遍历就依次打印元素并出队直到队列为空。

类模板声明

#include <stack>
template<
    class T,
    class Container = std::deque<T>
> class stack;

#include <queue>
template<
    class T,
    class Container = std::deque<T>
> class queue;

#include <queue>
template <class T,
          class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type>>
class priority_queue;

容器对象的初始化

查看优先级队列priority_queue的构造函数，主要给我们三种方式：创建无参对象、拷贝构造或者移动构造、迭代器范围。

// 1、创建无参对象
priority_queue<int> number;

// 2、拷贝构造或者移动构造
priority_queue<int> number2(number);
priority_queue<int> number3(std::move(number));

// 3、迭代器范围
vector<int> vec{1, 4, 8, 3};
priority_queue<int> number4(vec.begin(), vec.end());

遍历

注意

优先级队列是没有迭代器与下标操作的，所以是不能使用传统的方式进行遍历，但是可以通过判断优先级队列是不是为空进行遍历。

// 容器是否为空
bool empty() const;

// 查看元素个数
size_type size() const;

插入与删除

// 将给定的元素value插入到容器中（传递左值或者右值都可以）
void push(const value_type &value);
void push(value_type &&value);

// 获取顶部元素（也就是优先级最高的元素）
const_reference top() const;

// 删除顶部元素(删除优先级最高的元素)
void pop();

其他操作

// 交换两个优先级队列中的元素内容
void swap(priority_queue &other);

// 向优先级队列中存入元素
template <class... Args>
void emplace(Args &&...args);

针对于内置类型

void test() {
    vector<int> number{2, 3, 6, 8, 9, 1, 4, 7, 5};
    priority_queue<int, vector<int>, std::greater<int>> pque;
    for (size_t idx = 0; idx != number.size(); ++idx) {
        pque.push(number[idx]);
        cout << "当前优先级队列中，优先级最高的元素是: " << pque.top() << endl;
    }
    while (!pque.empty()) {
        cout << pque.top() << " ";
        pque.pop();
    }
    cout << endl;
}

针对于自定义类型

优先级队列的第三个模板参数是Compare，需要针对容器的值类型进行比较， std::less<typename Container::value_type> ，这种写法与关联式容器中的Compare完全一样。也可以进行三种改写方式：模板的特化、函数对象的形式、运算符重载。

class Point {
public:
    Point(int ix = 0, int iy = 0)
        : _ix(ix), _iy(iy) {
    }
    ~Point() {
    }
    double getDistance() const {
        return hypot(_ix, _iy);
    }
    int getX() const {
        return _ix;
    }
    int getY() const {
        return _iy;
    }
    friend std::ostream &operator<<(std::ostream &os, const Point &rhs);
    friend bool operator==(const Point &lhs, const Point
                                                 &rhs); // std::equal_to
    friend class ComparePoint;

private:
    int _ix;
    int _iy;
};

std::ostream &operator<<(std::ostream &os, const Point &rhs) {
    os << "(" << rhs._ix
       << ", " << rhs._iy
       << ")";
    return os;
}

// 1、模板的特化
namespace std {
    template <>
    struct less<Point> {
        bool operator()(const Point &lhs, const Point &rhs) {
            // 具体的实现方式可以参考关联式容器中的写法
        }
    };

    // 2、函数对象
    struct ComparePoint {
        bool operator()(const Point &lhs, const Point &rhs) {
            // 具体的实现方式可以参考关联式容器中的写法
        }
    };
    // 3、运算符重载
    bool operator<(const Point &lhs, const Point &rhs) {
        // 具体的实现方式可以参考关联式容器中的写法
    }
    void test() {
        vector<Point> number = {
            Point(1, 2),
            Point(3, 4),
            Point(-1, 2),
            Point(5, 6),
            Point(0, 2),
            Point(-3, 2),
            Point(7, 8),
        };
        priority_queue<Point, vector<Point>, std::less<Point>> pque;
        for (size_t idx = 0; idx != numbers.size(); ++idx) {
            pque.push(numbers[idx]);
            cout << "当前优先级队列中，优先级最高的元素 : " << pque.top() << endl;
        }
        while (!pque.empty()) {
            cout << pque.top() << " ";
            pque.pop();
        }
        cout << endl;
    }
}

参考资料

• cppreference-容器库