C++容器适配器应用

C容器适配器应用容器适配器基于底层容器提供特定接口。标准库提供stack栈、queue队列和priority_queue优先队列三种适配器。stack提供后进先出的栈语义。#include#include#include#include#includevoid stack_example() {std::stack s;s.push(10);s.push(20);s.push(30);std::cout Stack size: s.size() \n;std::cout Top: s.top() \n;while (!s.empty()) {std::cout s.top() ;s.pop();}std::cout \n;}templateclass Stack {Container container_;public:void push(const T value) { container_.push_back(value); }void push(T value) { container_.push_back(std::move(value)); }void pop() {if (!container_.empty()) container_.pop_back();}T top() { return container_.back(); }const T top() const { return container_.back(); }bool empty() const { return container_.empty(); }size_t size() const { return container_.size(); }};void custom_stack_demo() {Stack s;s.push(1);s.push(2);s.push(3);while (!s.empty()) {std::cout s.top() ;s.pop();}std::cout \n;}queue提供先进先出的队列语义。void queue_example() {std::queue q;q.push(First);q.push(Second);q.push(Third);std::cout Front: q.front() \n;std::cout Back: q.back() \n;while (!q.empty()) {std::cout q.front() ;q.pop();}std::cout \n;}priority_queue默认是最大堆。void priority_queue_example() {std::priority_queue pq;pq.push(30);pq.push(10);pq.push(50);pq.push(20);std::cout Max heap: ;while (!pq.empty()) {std::cout pq.top() ;pq.pop();}std::cout \n;std::priority_queue, std::greater min_pq;min_pq.push(30);min_pq.push(10);min_pq.push(50);min_pq.push(20);std::cout Min heap: ;while (!min_pq.empty()) {std::cout min_pq.top() ;min_pq.pop();}std::cout \n;}优先队列实现任务调度。struct Task {int priority;std::string name;bool operator(const Task other) const {return priority other.priority;}};void task_scheduler() {std::priority_queue tasks;tasks.push({1, Low priority});tasks.push({5, High priority});tasks.push({3, Medium priority});tasks.push({4, Important task});while (!tasks.empty()) {auto task tasks.top();tasks.pop();std::cout Executing: task.name (priority: task.priority )\n;}}栈实现表达式求值。class ExpressionEvaluator {std::stack operands_;std::stack operators_;int precedence(char op) {if (op || op -) return 1;if (op * || op /) return 2;return 0;}int apply(int a, int b, char op) {switch (op) {case : return a b;case -: return a - b;case *: return a * b;case /: return a / b;default: return 0;}}public:int evaluate(const std::string expr) {for (size_t i 0; i expr.length(); i) {if (isspace(expr[i])) continue;if (isdigit(expr[i])) {int num 0;while (i expr.length() isdigit(expr[i])) {num num * 10 (expr[i] - 0);i;}--i;operands_.push(num);} else if (expr[i] () {operators_.push(expr[i]);} else if (expr[i] )) {while (!operators_.empty() operators_.top() ! () {int b operands_.top(); operands_.pop();int a operands_.top(); operands_.pop();char op operators_.top(); operators_.pop();operands_.push(apply(a, b, op));}if (!operators_.empty()) operators_.pop();} else {while (!operators_.empty() operators_.top() ! ( precedence(operators_.top()) precedence(expr[i])) {int b operands_.top(); operands_.pop();int a operands_.top(); operands_.pop();char op operators_.top(); operators_.pop();operands_.push(apply(a, b, op));}operators_.push(expr[i]);}}while (!operators_.empty()) {int b operands_.top(); operands_.pop();int a operands_.top(); operands_.pop();char op operators_.top(); operators_.pop();operands_.push(apply(a, b, op));}return operands_.top();}};void expression_demo() {ExpressionEvaluator eval;std::cout 3 5 * 2 eval.evaluate(3 5 * 2) \n;std::cout (3 5) * 2 eval.evaluate((3 5) * 2) \n;std::cout 10 - 3 * 2 4 eval.evaluate(10 - 3 * 2 4) \n;}双端队列实现滑动窗口最大值。std::vector max_sliding_window(const std::vector nums, int k) {std::vector result;std::deque dq;for (int i 0; i nums.size(); i) {while (!dq.empty() dq.front() i - k 1) dq.pop_front();while (!dq.empty() nums[dq.back()] nums[i]) dq.pop_back();dq.push_back(i);if (i k - 1) result.push_back(nums[dq.front()]);}return result;}void sliding_window_demo() {std::vector nums {1, 3, -1, -3, 5, 3, 6, 7};auto result max_sliding_window(nums, 3);std::cout Sliding window max: ;for (int v : result) std::cout v ;std::cout \n;}容器适配器提供了简洁的接口是算法实现的重要工具。