搜索

android类加载源码分析 - revercc - 博客园


发布时间: 2022-11-24 18:24:03    浏览次数:48 次

容器适配器是一个封装了序列容器的类模板它在一般序列容器的基础上,提供了一些不同的功能。之所以称作适配器类,是因为它可以通过适配容器现有的接口来提供不同的功能

本章将介绍 3 种容器适配器,分别是 stackqueuepriority_queue

  • stack<T>:是一个默认封装了 deque<T> 容器的适配器类模板,默认实现的是一个后入先出(Last-In-First-Out,LIFO)的压入栈。stack<T> 模板定义在头文件 stack 中
  • queue<T>:是一个默认封装了 deque<T> 容器的适配器类模板,默认实现的是一个先入先出(First-In-First-Out,LIFO)的队列。可以为它指定一个符合确定条件的基础容器。queue<T> 模板定义在头文件 queue 中
  • priority_queue<T>:是一个默认封装了 vector<T> 容器的适配器类模板,默认实现的是一个会对元素排序,从而保证最大元素总在队列最前面的队列。priority_queue<T> 模板定义在头文件 queue 中

什么是适配器,C++ STL容器适配器详解

其实,容器适配器中的“适配器”,和生活中常见的电源适配器中“适配器”的含义非常接近。我们知道,无论是电脑、手机还是其它电器,充电时都无法直接使用 220V 的交流电,为了方便用户使用,各个电器厂商都会提供一个适用于自己产品的电源线,它可以将 220V 的交流电转换成适合电器使用的低压直流电。  从用户的角度看,电源线扮演的角色就是将原本不适用的交流电变得适用,因此其又被称为电源适配器。 

再举一个例子,假设一个代码模块 A,它的构成如下所示:

class A{
public:
    void f1(){}
    void f2(){}
    void f3(){}
    void f4(){}
};

现在我们需要设计一个模板 B,但发现,其实只需要组合一下模块 A 中的 f1()、f2()、f3(),就可以实现模板 B 需要的功能。其中 f1() 单独使用即可,而 f2() 和 f3() 需要组合起来使用,如下所示:

class B{
private:
    A * a;
public:
    void g1(){
        a->f1();
    }
    void g2(){
        a->f2();
        a->f3();
    }
};

可以看到,就如同是电源适配器将不适用的交流电变得适用一样,模板 B 将不适合直接拿来用的模板 A 变得适用了,因此我们可以将模板 B 称为 B 适配器

容器适配器也是同样的道理,简单的理解容器适配器,其就是将不适用的序列式容器(包括 vector、deque 和 list)变得适用。容器适配器的底层实现和模板 A、B 的关系是完全相同的,即通过封装某个序列式容器,并重新组合该容器中包含的成员函数,使其满足某些特定场景的需要。  

容器适配器本质上还是容器,只不过此容器模板类的实现,利用了大量其它基础容器模板类中已经写好的成员函数。当然,如果必要的话,容器适配器中也可以自创新的成员函数。

需要注意的是, STL 中的容器适配器,其内部使用的基础容器并不是固定的,用户可以在满足特定条件的多个基础容器中自由选择。 STL 提供了 3 种容器适配器,分别为 stack 栈适配器queue 队列适配器以及 priority_queue 优先权队列适配器。其中, 各适配器所使用的默认基础容器以及可供用户选择的基础容器,如表 1 所示。
表 1 STL 容器适配器及其基础容器
容器适配器 基础容器筛选条件 默认使用的基础容器
stack  基础容器需包含以下成员函数:
  • empty()
  • size()
  • back()
  • push_back()
  • pop_back()
满足条件的基础容器有 vector、deque、list。
deque
queue 基础容器需包含以下成员函数:
  • empty()
  • size()
  • front()
  • back()
  • push_back()
  • pop_front()
满足条件的基础容器有 deque、list。
deque
priority_queue 基础容器需包含以下成员函数:
  • empty()
  • size()
  • front()
  • push_back()
  • pop_back()
满足条件的基础容器有vector、deque。
vector

不同场景下,由于不同的序列式容器其底层采用的数据结构不同,因此容器适配器的执行效率也不尽相同。但通常情况下,使用默认的基础容器即可。当然,我们也可以手动修改。 

C++ stack(STL stack)容器适配器详解

stack 栈适配器是一种单端开口的容器(如图 1 所示),实际上该容器模拟的就是栈存储结构,即无论是向里存数据还是从中取数据,都只能从这一个开口实现操作。

stack容器适配器的创建

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

#include <stack>
using namespace std;
  • 创建一个不包含任何元素的 stack 适配器,并采用默认的 deque 基础容器:
std::stack<int> values;
  • 定义一个使用 list 基础容器的 stack 适配器:
std::stack<int, std::list<int>> values;
  • 可以用一个基础容器来初始化 stack 适配器,只要该容器的类型和 stack 底层使用的基础容器类型相同即可。例如:
std::list<int> values {1, 2, 3};
std::stack<int,std::list<int>> my_stack (values);

注意,初始化后的 my_stack 适配器中,栈顶元素为 3,而不是 1。另外在第 2 行代码中,stack 第 2 个模板参数必须显式指定为 list<int>(必须为 int 类型,和存储类型保持一致),否则 stack 底层将默认使用 deque 容器,也就无法用 lsit 容器的内容来初始化 stack 适配器。  

  • 还可以用一个 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);

注意,第 3、4 种初始化方法中,my_stack 适配器的数据是经过拷贝得来的,也就是说,操作 my_stack 适配器,并不会对 values 容器以及 my_stack1 适配器有任何影响;反过来也是如此。  

stack容器适配器支持的成员函数:  

和其他序列容器相比,stack 是一类存储机制简单、提供成员函数较少的容器。表 1 列出了 stack 容器支持的全部成员函数。

表 1 stack容器适配器支持的成员函数
成员函数 功能
empty() 当 stack 栈中没有元素时,该成员函数返回 true;反之,返回 false。
size() 返回 stack 栈中存储元素的个数。
top() 返回一个栈顶元素的引用,类型为 T&。如果栈为空,程序会报错。
push(const T& val) 复制 val,再将 val 副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的
push(T&& obj) 以移动元素的方式将其压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的
pop() 弹出栈顶元素。
emplace(arg...) arg... 可以是一个参数,也可以是多个参数,但它们都只用于构造一个对象,并在栈顶直接生成该对象,作为新的栈顶元素
swap(stack<T> & other_stack) 将两个 stack 适配器中的元素进行互换,需要注意的是,进行互换的 2 个 stack 适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同
#include <iostream>
#include <stack>
#include <list>
using namespace std;
int main()
{
    //构建 stack 容器适配器
    list<int> values{ 1, 2, 3 };
    stack<int, list<int>> my_stack(values);
    //查看 my_stack 存储元素的个数
    cout << "size of my_stack: " << my_stack.size() << endl;
    //将 my_stack 中存储的元素依次弹栈,直到其为空
    while (!my_stack.empty())
    {
        cout << my_stack.top() << endl;
        //将栈顶元素弹栈
        my_stack.pop();
    }
    return 0;
}

 

C++ STL queue容器适配器详解

和 stack 栈容器适配器不同,queue 容器适配器有 2 个开口,其中一个开口专门用来输入数据,另一个专门用来输出数据,如图 1 所示。

queue容器适配器的创建

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

#include <queue>
using namespace std;
  • 创建一个空的 queue 容器适配器,其底层使用的基础容器选择默认的 deque 容器:  
std::queue<int> values;
  • 当然,也可以手动指定 queue 容器适配器底层采用的基础容器类型。例如,下面创建了一个使用 list 容器作为基础容器的空 queue 容器适配器:  
std::queue<int, std::list<int>> values;

注意,在手动指定基础容器的类型时,其存储的数据类型必须和 queue 容器适配器存储的元素类型保持一致。  

  • 可以用基础容器来初始化 queue 容器适配器,只要该容器类型和 queue 底层使用的基础容器类型相同即可。例如:  
std::deque<int> values{1,2,3};
std::queue<int> my_queue(values);

由于 my_queue 底层采用的是 deque 容器,和 values 类型一致,且存储的也都是 int 类型元素,因此可以用 values 对 my_queue 进行初始化。  

  • 还可以直接通过 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;

值得一提的是,第 3、4 种初始化方法中 my_queue 容器适配器的数据是经过拷贝得来的,也就是说,操作 my_queue 容器适配器中的数据,并不会对 values 容器以及 my_queue1 容器适配器有任何影响;反过来也是如此。  

queue容器适配器支持的成员函数:  

queue 容器适配器和 stack 有一些成员函数相似,但在一些情况下,工作方式有些不同。表 2 罗列了 queue 容器支持的全部成员函数。

表 2 queue容器适配器支持的成员函数
成员函数 功能
empty() 如果 queue 中没有元素的话,返回 true。
size() 返回 queue 中元素的个数。
front() 返回 queue 中第一个元素的引用如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。
back() 返回 queue 中最后一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。
push(const T& obj) 在 queue 的尾部添加一个元素的副本这是通过调用底层容器的成员函数 push_back() 来完成的
emplace() 在 queue 的尾部直接添加一个元素。
push(T&& obj) 以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的
pop() 删除 queue 中的第一个元素。
swap(queue<T> &other_queue) 将两个 queue 容器适配器中的元素进行互换,需要注意的是,进行互换的 2 个 queue 容器适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同

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

#include <iostream>
#include <queue>
#include <deque>
using namespace std;
int main()
{
    //构建 queue 容器适配器
    deque<int> values{ 1,2,3 };
    queue<int> my_queue(values);//{1,2,3}
    //查看 my_queue 存储元素的个数
    cout << "size of my_queue: " << my_queue.size() << endl;
    //访问 my_queue 中的元素
    while (!my_queue.empty())
    {
        cout << my_queue.front() << endl;
        //访问过的元素出队列
        my_queue.pop();
    }
    return 0;
}

 

C++ STL priority_queue容器适配器详解

priority_queue 容器适配器模拟的也是队列这种存储结构,即使用此容器适配器存储元素只能“从一端进(称为队尾),从另一端出(称为队头)”,且每次只能访问 priority_queue 中位于队头的元素。 但是,priority_queue 容器适配器中元素的存和取,遵循的并不是 “First in,First out”(先入先出)原则,先进队列的元素并不一定先出队列,而是优先级最大的元素最先出队列

那么,priority_queue 容器适配器中存储的元素,优先级是如何评定的呢?很简单,每个 priority_queue 容器适配器在创建时,都制定了一种排序规则。根据此规则,该容器适配器中存储的元素就有了优先级高低之分

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

基于 priority_queue 的这种特性,因此该容器适配器又被称为优先级队列

priority_queue 容器适配器“First in,Largest out”的特性,和它底层采用堆结构存储数据是分不开的

STL 中,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 容器
  • typename Compare:指定容器中评定元素优先级所遵循的排序规则,默认使用std::less<T>按照元素值从大到小进行排序,还可以使用std::greater<T>按照元素值从小到大排序,但更多情况下是使用自定义的排序规则。其中,std::less<T> 和 std::greater<T> 都是以函数对象的方式定义在 <functional> 头文件中

创建priority_queue的几种方式

由于 priority_queue 容器适配器模板位于<queue>头文件中,并定义在 std 命名空间里,因此在试图创建该类型容器之前,程序中需包含以下 2 行代码:

#include <queue>
using namespace std;
  • 创建一个空的 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}

注意,以上 2 种方式必须保证数组或容器中存储的元素类型和 priority_queue 指定的存储类型相同。另外,用来初始化的数组或容器中的数据不需要有序,priority_queue 会自动对它们进行排序。  

  • 还可以手动指定 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}

事实上,std::less<T> 和 std::greater<T> 适用的场景是有限的,更多场景中我们会使用自定义的排序规则。  

priority_queue提供的成员函数: 

表 2 priority_queue 提供的成员函数
成员函数 功能
empty() 如果 priority_queue 为空的话,返回 true;反之,返回 false。
size() 返回 priority_queue 中存储元素的个数。
top() 返回 priority_queue 中第一个元素的引用形式
push(const T& obj) 根据既定的排序规则,将元素 obj 的副本存储到 priority_queue 中适当的位置。
push(T&& obj) 根据既定的排序规则,将元素 obj 移动存储到 priority_queue 中适当的位置。
emplace(Args&&... args) Args&&... args 表示构造一个存储类型的元素所需要的数据(对于类对象来说,可能需要多个数据构造出一个对象)。此函数的功能是根据既定的排序规则,在容器适配器适当的位置直接生成该新元素。
pop() 移除 priority_queue 容器适配器中第一个元素
swap(priority_queue<T>& other) 将两个 priority_queue 容器适配器中的元素进行互换,需要注意的是,进行互换的 2 个 priority_queue 容器适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同

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

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

int main() {
    //创建一个空的priority_queue容器适配器
    std::priority_queue<int> values;
    //使用 push() 成员函数向适配器中添加元素
    values.push(3);//{3}
    values.push(1);//{3,1}
    values.push(4);//{4,1,3}
    values.push(2);//{4,2,3,1}
    //遍历整个容器适配器
    while (!values.empty()) {
        //输出第一个元素并移除。
        std::cout << values.top() << " ";
        values.pop();//移除队头元素的同时,将剩余元素中优先级最大的移至队头
    }
    return 0;
}

priority_queue容器适配器实现自定义排序: 

<functional> 头文件提供的排序方式(std::less<T> 和 std::greater<T>)不再适用时,我们可以自定义一个满足需求的排序规则

首先,无论 priority_queue 中存储的是基础数据类型(int、double 等),还是 string 类对象或者自定义的类对象,都可以使用函数对象的方式自定义排序规则。例如:  

#include<iostream>
#include<queue>
using namespace std;
//函数对象类
template <typename T>
class cmp
{
public:
    //重载 () 运算符
    bool operator()(T a, T b)
    {
        return a > b;
    }
};

int main()
{
    int a[] = { 4,2,3,5,6 };
    priority_queue<int,vector<int>,cmp<int> > pq(a,a+5);
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

注意,C++ 中的 struct 和 class 非常类似,前者也可以包含成员变量和成员函数,因此上面程序中,函数对象类 cmp 也可以使用 struct 关键字创建:

struct cmp
{
    //重载 () 运算符
    bool operator()(T a, T b)
    {
        return a > b;
    }
};

除此之外,当 priority_queue 容器适配器中存储的数据类型为结构体或者类对象(包括 string 类对象)时,还可以通过重载其 > 或者 < 运算符,间接实现自定义排序规则的目的。  注意,此方式仅适用于 priority_queue 容器中存储的为类对象或者结构体变量,也就是说,当存储类型为类的指针对象或者结构体指针变量时,此方式将不再适用,而只能使用函数对象的方式。  

要想彻底理解这种方式的实现原理,首先要搞清楚 std::less<T> 和 std::greater<T> 各自的底层实现。实际上,<functional> 头文件中的 std::less<T> 和 std::greater<T> ,各自底层实现采用的都是函数对象的方式。比如,

  • std::less<T> 的底层实现代码为:
template <typename T>
struct less {
    //定义新的排序规则
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs < _rhs;
    }
};
  • std::greater<T> 的底层实现代码为:
template <typename T>
struct greater {
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs > _rhs;
    }
};

可以看到,std::less<T> 和 std::greater<T> 底层实现的唯一不同在于,前者使用 < 号实现从大到小排序,后者使用 > 号实现从小到大排序。由于std::less<T> 和 std::greater<T>里的实际操作主要用到了类型T的>或者>运算符,所以我们可以通过重载 < 或者 > 运算符修改 std::less<T> 和 std::greater<T> 的排序规则,从而间接实现自定义排序,举个例子:  

#include<queue>
#include<iostream>

using namespace std;

class node {
public:
    node(int x = 0, int y = 0) :x(x), y(y) {}
    int x, y;
};
//新的排序规则为:先按照 x 值排序,如果 x 相等,则按 y 的值排序
bool operator < (const node &a, const node &b) {
    if (a.x > b.x) return 1;
    else if (a.x == b.x)
        if (a.y >= b.y) return 1;
    return 0;
}

int main() {
    //创建一个 priority_queue 容器适配器,其使用默认的 vector 基础容器以及 less 排序规则。
    priority_queue<node> pq;
    pq.push(node(1, 2));
    pq.push(node(2, 2));
    pq.push(node(3, 4));
    pq.push(node(3, 3));
    pq.push(node(2, 3));
    cout << "x y" << endl;
    while (!pq.empty()) {
        cout << pq.top().x << " " << pq.top().y << endl;
        pq.pop();
    }
    return 0;
}

 要达到同样的结果,我们也可以通过重载 > 运算符,赋予 std::greater<T> 和之前不同的排序方式。

当然,也可以以友元函数或者成员函数的方式重载 > 或者 < 运算符。需要注意的是,以成员函数的方式重载 > 或者 < 运算符时,该成员函数必须声明为 const 类型,且参数也必须为 const 类型,至于参数的传值方式是采用按引用传递还是按值传递,都可以(建议采用按引用传递,效率更高)

  • 例如,将上面程序改为以成员函数的方式重载 < 运算符:
class node {
public:
    node(int x = 0, int y = 0) :x(x), y(y) {}
    int x, y;
    bool operator < (const node &b) const{
        if ((*this).x > b.x) return 1;
        else if ((*this).x == b.x)
            if ((*this).y >= b.y) return 1;
        return 0;
    }
};
  • 同样,在以友元函数的方式重载 < 或者 > 运算符时,要求参数必须使用 const 修饰。例如,将上面程序改为以友元函数的方式重载 < 运算符。例如:  
class node {
public:
    node(int x = 0, int y = 0) :x(x), y(y) {}
    int x, y;
    friend bool operator < (const node &a, const node &b);
};
//新的排序规则为:先按照 x 值排序,如果 x 相等,则按 y 的值排序
bool operator < (const node &a, const node &b){
    if (a.x > b.x) return 1;
    else if (a.x == b.x)
        if (a.y >= b.y) return 1;
    return 0;
}

总的来说,

  • 以函数对象的方式自定义 priority_queue 的排序规则,适用于任何情况
  • 以重载 > 或者 < 运算符间接实现 priority_queue 自定义排序的方式,仅适用于 priority_queue 中存储的是结构体变量或者类对象(包括 string 类对象)。  

深度剖析priority_queue容器的底层实现:  

priority_queue 优先级队列之所以总能保证优先级最高的元素位于队头,最重要的原因是其底层采用堆数据结构存储结构。有读者可能会问,priority_queue 底层不是采用 vector 或 deque 容器存储数据吗,这里又说使用堆结构存储数据,它们之间不冲突吗?显然,它们之间是不冲突的。 

  • 首先,vector 和 deque 是用来存储元素的容器,而堆是一种数据结构,其本身无法存储数据,只能依附于某个存储介质,辅助其组织数据存储的先后次序
  • 其次,priority_queue 底层采用 vector 或者 deque 作为基础容器,这毋庸置疑。但由于 vector 或 deque 容器并没有提供实现 priority_queue 容器适配器 “First in,Largest out” 特性的功能,因此 STL 选择使用堆来重新组织 vector 或 deque 容器中存储的数据,从而实现该特性。 

注意,虽然不使用堆结构,通过编写算法调整 vector 或者 deque 容器中存储元素的次序,也能使其具备 “First in,Largest out” 的特性,但执行效率通常没有使用堆结构高。  

为了验证 priority_queue 底层确实采用堆存储结构实现的,我们可以尝试用堆结合基础容器 vector 或 deque 实现 priority_queue。值得庆幸的是,STL 已经为我们封装好了可以使用堆存储结构的方法,它们都位于 <algorithm> 头文件中。表 2 中列出了常用的几个和堆存储结构相关的方法。

表 2 STL对堆存储结构的支持
函数 功能
make_heap(first,last,comp) 选择位于 [first,last) 区域内的数据,并根据 comp 排序规则建立堆其中 fist 和 last 可以是指针或者迭代器默认是建立大顶堆
push_heap(first,last,comp) 当向数组或容器中添加数据之后,此数据可能会破坏堆结构,该函数的功能是重建堆
pop_heap(first,last,comp) 将位于序列头部的元素(优先级最高)移动序列尾部,并使[first,last-1] 区域内的元素满足堆存储结构
sort_heap(first,last,comp) 对 [first,last) 区域内的元素进行堆排序,将其变成一个有序序列
is_heap_until(first,last,comp) 发现[first,last)区域内的最大堆
is_heap(first,last,comp) 检查 [first,last) 区域内的元素,是否为堆结构

下面例子中,使用了表 2 中的部分函数,并结合 vector 容器提供的成员函数,模拟了 priority_queue 容器适配器部分成员函数的底层实现:

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
void display(vector<int>& val) {
    for (auto v : val) {
        cout << v << " ";
    }
    cout << endl;
}
int main()
{
    vector<int>values{ 2,1,3,4 };
    //建立堆
    make_heap(values.begin(), values.end());//{4,2,3,1}
    display(values);
    //添加元素
    cout << "添加元素:\n";
    values.push_back(5);
    display(values);
    push_heap(values.begin(), values.end());//{5,4,3,1,2}
    display(values);
    //移除元素
    cout << "移除元素:\n";
    pop_heap(values.begin(), values.end());//{4,2,3,1,5}
    display(values);
    values.pop_back();
    display(values);
    return 0;
}

上面程序可以用 priority_queue 容器适配器等效替代:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main()
{
    //创建优先级队列
    std::vector<int>values{ 2,1,3,4 };
    std::priority_queue<int>copy_values(values.begin(), values.end());
    //添加元素
    copy_values.push(5);
    //移除元素
    copy_values.pop();
    return 0;
} 

如果调试此程序,查看各个阶段 priority_queue 中存储的元素,可以发现,它和上面程序的输出结果是一致。也就是说,此程序在创建 priority_queue 之后,其存储的元素依次为 {4,2,3,1},同样当添加元素 5 之后,其存储的元素依次为 {5,4,3,1,2},移除一个元素之后存储的元素依次为 {4,2,3,1}。  

 

免责声明 android类加载源码分析 - revercc - 博客园,资源类别:文本, 浏览次数:48 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 06:24:03。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/revercc/p/16808386.html