容器适配器，其就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用。

STL 提供了 3 种容器适配器，分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。

1. stack容器

1.1 stack容器的创建

由于 stack 适配器以模板类 stack<T,Container=deque<T>>（其中 T 为存储元素的类型，Container 表示底层容器的类型）的形式位于<stack>头文件中，并定义在 std 命名空间里。因此，在创建该容器之前，程序中应包含以下 2 行代码：

#include <stack>
using namespace std;

创建 stack 适配器，大致分为如下几种方式：

• 创建一个不包含任何元素的 stack 适配器，并采用默认的 deque 基础容器：

std::stack<int> values;

• 定义一个使用 list 基础容器的 stack 适配器：

std::stack<std::string, std::list<int>> values;

• 用一个 stack 适配器来初始化另一个 stack 适配器，只要它们存储的元素类型以及底层采用的基础容器类型相同即可：

std::list<int> values {1, 2, 3};
std::stack<int,std::list<int>> my_stack (values);

• 还可以用一个 stack 适配器来初始化另一个 stack 适配器，只要它们存储的元素类型以及底层采用的基础容器类型相同即可：

std::list<int> values{ 1, 2, 3 };
std::stack<int, std::list<int>> my_stack1(values);
std::stack<int, std::list<int>> my_stack=my_stack1;
//std::stack<int, std::list<int>> my_stack(my_stack1);

1.2 stack容器支持的成员函数

2. queue容器

2.1 queue容器的创建

queue 容器适配器以模板类 queue<T,Container=deque<T>>（其中 T 为存储元素的类型，Container 表示底层容器的类型）的形式位于<queue>头文件中，并定义在 std 命名空间里。因此，在创建该容器之前，程序中应包含以下 2 行代码：

#include <queue>
using namespace std;

创建queue 适配器，大致分为如下几种方式：

• 创建一个空的 queue 容器适配器，其底层使用的基础容器选择默认的 deque 容器：

std::queue<int> values;

• 也可以手动指定 queue 容器适配器底层采用的基础容器类型：作为 queue 容器适配器的基础容器，其必须提供 front()、back()、push_back()、pop_front()、empty() 和 size() 这几个成员函数，符合条件的序列式容器仅有 deque 和 list。

std::queue<int, std::list<int>> values;

• 可以用基础容器来初始化 queue 容器适配器，只要该容器类型和 queue 底层使用的基础容器类型相同即可。例如：

std::deque<int> values{1,2,3};
std::queue<int> my_queue(values);

• 还可以直接通过 queue 容器适配器来初始化另一个 queue 容器适配器，只要它们存储的元素类型以及底层采用的基础容器类型相同即可。例如：

std::deque<int> values{1,2,3};
std::queue<int> my_queue1(values);
std::queue<int> my_queue(my_queue1);
// 或者使用
// std::queue<int> my_queue = my_queue1;

2.2 queue容器支持的成员函数

和 stack 一样，queue 也没有迭代器，因此访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素。

3. priority_queue容器

priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素，每当有新元素进入，它都会根据既定的排序规则找到优先级最高的元素，并将其移动到队列的队头。同样，当 priority_queue 从队头移除出一个元素之后，它也会再找到当前优先级最高的元素，并将其移动到队头。

3.1 queue容器的创建

priority_queue 容器适配器的定义如下：

template <typename T,
        typename Container=std::vector<T>,
        typename Compare=std::less<T> >
class priority_queue{
    //......
}

priority_queue 容器适配器模板类最多可以传入 3 个参数，它们各自的含义如下：

• typename T：指定存储元素的具体类型；

• typename Container：指定 priority_queue 底层使用的基础容器，默认使用 vector 容器。

作为 priority_queue 容器适配器的底层容器，其必须包含 empty()、size()、front()、push_back()、pop_back() 这几个成员函数，STL序列式容器中只有 vector 和 deque 容器符合条件；

• typename Compare：指定容器中评定元素优先级所遵循的排序规则，默认使用std::less<T>，按照元素值从大到小进行排序，还可以使用std::greater<T>。

创建 priority_queue 容器适配器的方法，大致有以下几种。

• 创建一个空的 priority_queue 容器适配器，第底层采用默认的 vector 容器，排序方式也采用默认的 std::less<T> 方法：

std::priority_queue<int> values;

可以使用普通数组或其它容器中指定范围内的数据，对 priority_queue 容器适配器进行初始化：

// 使用普通数组
int values[]{4,1,3,2};
std::priority_queue<int>copy_values(values,values+4);//{4,2,3,1}
// 使用序列式容器
std::array<int,4>values{ 4,1,3,2 };
std::priority_queue<int>copy_values(values.begin(),values.end());//{4,2,3,1}

还可以手动指定 priority_queue 使用的底层容器以及排序规则，比如：

int values[]{ 4,1,2,3 };
std::priority_queue<int, std::deque<int>, std::greater<int> >copy_values(values, values+4); // {1,3,2,4}

2.2 priority_queue容器支持的成员函数

和 queue 一样，priority_queue 也没有迭代器，因此访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素。

4. STL distance()函数

4.1 distance概述

distance() 函数用于计算两个迭代器表示的范围内包含元素的个数，其语法格式如下：

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type distance (InputIterator first, InputIterator last);

其中，first 和 last 都为迭代器，其类型可以是输入迭代器、前向迭代器、双向迭代器以及随机访问迭代器；该函数会返回[first, last)范围内包含的元素的个数。

注意，first 和 last 的迭代器类型，直接决定了 distance() 函数底层的实现机制：

• 当 first 和 last 为随机访问迭代器时，distance() 底层直接采用 last - first 求得 [first, last) 范围内包含元素的个数，其时间复杂度为O(1)常数阶；

• 当 first 和 last 为非随机访问迭代器时，distance() 底层通过不断执行 ++first（或者 first++）直到 first==last，由此来获取 [first, last) 范围内包含元素的个数，其时间复杂度为O(n)线性阶。

distance() 函数定义在<iterator>头文件，并位于 std 命名空间中。因此在使用此函数前，程序中应包含如下代码：

#include <iterator>
using namespace std;

另外，distance() 函数定义在<iterator>头文件，并位于 std 命名空间中。因此在使用此函数前，程序中应包含如下代码：

#include <iostream>     // std::cout
#include <iterator>     // std::distance
#include <list>         // std::list
using namespace std;
int main() {
    // 创建一个空 list 容器
    list<int> mylist;
    // 向空 list 容器中添加元素 0~9
    for (int i = 0; i < 10; i++) {
        mylist.push_back(i);
    }
    // 指定 2 个双向迭代器，用于执行某个区间
    list<int>::iterator first = mylist.begin();//指向元素 0
    list<int>::iterator last = mylist.end();//指向元素 9 之后的位置
    // 获取 [first,last) 范围内包含元素的个数
    cout << "distance() = " << distance(first, last);
    return 0;
}

4.1 distance成员函数