当前位置：首页 > news >正文

c++ STL 容器相关

news 来源：原创 2024/9/19 9:51:06

容器库：容器库 - cppreference.com

一、std::priority_queue

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

优先级队列是一种容器适配器，它提供常数时间的（默认）最大元素查找，对数代价的插入与提取。可以通过用户提供的 Compare 更改顺序，例如，用 std::greater<T> 将导致最小元素作为 top() 出现。priority_queue 的作用类似于管理某些随机访问容器中的堆，其优势是不可能意外使堆失效。

1.模板形参

T - 存储元素的类型。T 与 Container::value_type 不是同一类型时非良构。

Container

用于存储元素的底层容器类型。容器必须满足序列容器 (SequenceContainer) 的要求，并且它的迭代器必须满足老式随机访问迭代器 (LegacyRandomAccessIterator) 的要求。另外，它必须提供拥有通常语义的下列函数：

back()，例如 std::vector::back()，
push_back()，例如 std::deque::push_back()，
pop_back()，例如 std::vector::pop_back()。

标准容器 std::vector（包括 std::vector<bool>）和 std::deque 满足这些要求。

Compare

提供严格弱序的比较 (Compare) 类型。

注意比较 (Compare) 形参的定义，使得它的第一实参在弱序中先于它的第二实参时返回 true。但因为优先级队列首先输出最大元素，所以“先来”的元素实际上会在最后输出。即队列头含有按照比较 (Compare) 所施加弱序的“最后”元素。

成员类型
类型               定义
container_type    Container
value_compare     Compare
value_type        Container::value_type
size_type         Container::size_type
reference         Container::reference
const_reference   Container::const_reference

成员对象
名字	          定义
Containerc        底层容器(受保护成员对象)
Compare comp      比较函数对象(受保护成员对象)

#include <functional>
#include <iostream>
#include <queue>
#include <string_view>
#include <vector>template<typename T>
void pop_println(std::string_view rem, T& pq)
{std::cout << rem << ": ";for (; !pq.empty(); pq.pop())std::cout << pq.top() << ' ';std::cout << '\n';
}template<typename T>
void println(std::string_view rem, const T& v)
{std::cout << rem << ": ";for (const auto& e : v)std::cout << e << ' ';std::cout << '\n';
}int main()
{const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};println("data", data);std::priority_queue<int> max_priority_queue;// 填充优先级队列。for (int n : data)max_priority_queue.push(n);pop_println("max_priority_queue", max_priority_queue);// std::greater<int> 使得最大优先队列表现为最小优先队列。std::priority_queue<int, std::vector<int>, std::greater<int>>min_priority_queue1(data.begin(), data.end());pop_println("min_priority_queue1", min_priority_queue1);// 定义最小优先队列的另一种方法std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>());pop_println("min_priority_queue2", min_priority_queue2);// 使用自定义的函数对象来比较元素。struct{bool operator()(const int l, const int r) const { return l > r; }} customLess;std::priority_queue custom_priority_queue(data.begin(), data.end(), customLess);pop_println("custom_priority_queue", custom_priority_queue);// 使用 lambda 来比较元素。auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };std::priority_queue<int, std::vector<int>, decltype(cmp)> lambda_priority_queue(cmp);for (int n : data)lambda_priority_queue.push(n);pop_println("lambda_priority_queue", lambda_priority_queue);
}

#include <iostream>
#include <queue>
#include <vector>
#include <functional>template<typename T>void print_queue(T& q){while(!q.empty()){std::cout << q.top() << " " ;q.pop();}std::cout << '\n';
}int main(){std::priority_queue<int> q;for(int n:{1,9,2,8,3,7,4,6,5,0})q.push(n);print_queue(q);std::priority_queue<int, std::vector<int>, std::greater<int>> q1;for(int n:{1,9,2,8,3,7,4,6,5,0})q1.push(n);print_queue(q1);auto cmp = [](int left, int right){return (left) > (right);};std::priority_queue<int, std::vector<int>, decltype(cmp) > q3(cmp);for(int n:{99,11,88,22,77,33,66,44,55})q3.push(n); print_queue(q3);ereturn 0;
}