C++ STL priority_queue容器适配器剖析
发布时间：2022-10-20 12:48:02 所属栏目：语言 来源：
导读： priority_queue 容器适配器模拟的也是队列这种存储结构，即使用此容器适配器存储元素只能“从一端进（称为队尾），从另一端出（称为队头）”，且每次只能访问 priority_queue 中位于队头的元素。
|
priority_queue 容器适配器模拟的也是队列这种存储结构，即使用此容器适配器存储元素只能“从一端进（称为队尾），从另一端出（称为队头）”，且每次只能访问 priority_queue 中位于队头的元素。 但是，priority_queue 容器适配器中元素的存和取，遵循的并不是 “First in,First out”（先入先出）原则，而是“First in，Largest out”原则。直白的翻译，指的就是先进队列的元素并不一定先出队列，而是优先级最大的元素最先出队列。 注意，“First in，Largest out”原则是笔者为了总结 priority_queue 存取元素的特性自创的一种称谓，仅为了方便读者理解。 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 容器。 作为 priority_queue 容器适配器的底层容器，其必须包含 empty()、size()、front()、push_back()、pop_back() 这几个成员函数，STL 序列式容器中只有 vector 和 deque 容器符合条件。 创建 priority_queue 容器适配器的方法，大致有以下几种。 1) 创建一个空的 priority_queue 容器适配器，第底层采用默认的 vector 容器，排序方式也采用默认的 std::less<T> 方法： std::priority_queue<int> values; 2) 可以使用普通数组或其它容器中指定范围内的数据，对 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 会自动对它们进行排序。 3) 还可以手动指定 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提供的成员函数 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 也没有迭代器，因此访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素。 （编辑：财气旺网 - 财气网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐