C++容器适配器应用指南

C++容器适配器应用指南

容器适配器是STL提供的特殊容器接口，它们基于底层容器实现特定的数据结构语义。标准库提供了stack、queue和priority_queue三种容器适配器。

std::stack提供后进先出的栈语义，默认使用deque作为底层容器。

#include
#include
#include
#include

void basic_stack_usage() {
std::stack s;

s.push(10);
s.push(20);
s.push(30);

std::cout << "Stack size: " << s.size() << "\n";
std::cout << "Top element: " << s.top() << "\n";

while (!s.empty()) {
std::cout << s.top() << " ";
s.pop();
}
std::cout << "\n";
}

template>
class 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 (!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_example() {
Stack> vec_stack;
vec_stack.push(1);
vec_stack.push(2);
vec_stack.push(3);

while (!vec_stack.empty()) {
std::cout << vec_stack.top() << " ";
vec_stack.pop();
}
std::cout << "\n";
}

std::queue提供先进先出的队列语义。

#include

void basic_queue_usage() {
std::queue q;

q.push("first");
q.push("second");
q.push("third");

std::cout << "Queue size: " << q.size() << "\n";
std::cout << "Front: " << q.front() << "\n";
std::cout << "Back: " << q.back() << "\n";

while (!q.empty()) {
std::cout << q.front() << " ";
q.pop();
}
std::cout << "\n";
}

template>
class Queue {
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 (!empty()) {
container_.pop_front();
}
}

T& front() {
return container_.front();
}

const T& front() const {
return container_.front();
}

T& back() {
return container_.back();
}

const T& back() const {
return container_.back();
}

bool empty() const {
return container_.empty();
}

size_t size() const {
return container_.size();
}
};

std::priority_queue实现优先队列，默认是最大堆。

void priority_queue_basic() {
std::priority_queue pq;

pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);

std::cout << "Priority queue (max heap):\n";
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 << "Priority queue (min heap):\n";
while (!min_pq.empty()) {
std::cout << min_pq.top() << " ";
min_pq.pop();
}
std::cout << "\n";
}

template,
typename Compare = std::less>
class PriorityQueue {
Container container_;
Compare comp_;

void heapify_up(size_t index) {
while (index > 0) {
size_t parent = (index - 1) / 2;
if (!comp_(container_[parent], container_[index])) {
break;
}
std::swap(container_[index], container_[parent]);
index = parent;
}
}

void heapify_down(size_t index) {
size_t size = container_.size();
while (true) {
size_t largest = index;
size_t left = 2 * index + 1;
size_t right = 2 * index + 2;

if (left < size && comp_(container_[largest], container_[left])) {
largest = left;
}
if (right < size && comp_(container_[largest], container_[right])) {
largest = right;
}

if (largest == index) break;

std::swap(container_[index], container_[largest]);
index = largest;
}
}

public:
void push(const T& value) {
container_.push_back(value);
heapify_up(container_.size() - 1);
}

void pop() {
if (empty()) return;
container_[0] = container_.back();
container_.pop_back();
if (!empty()) {
heapify_down(0);
}
}

const T& top() const {
return container_[0];
}

bool empty() const {
return container_.empty();
}

size_t size() const {
return container_.size();
}
};

void custom_priority_queue_example() {
PriorityQueue pq;
pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);

while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
std::cout << "\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_operator(int a, int b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
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_operator(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_operator(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_operator(a, b, op));
}

return operands_.top();
}
};

void expression_evaluation_example() {
ExpressionEvaluator eval;
std::cout << "3 + 5 * 2 = " << eval.evaluate("3 + 5 * 2") << "\n";
std::cout << "(3 + 5) * 2 = " << eval.evaluate("(3 + 5) * 2") << "\n";
}

优先队列可以实现任务调度系统。

#include
#include

struct Task {
int priority;
std::string name;
std::function action;

bool operator<(const Task& other) const {
return priority < other.priority;
}
};

class TaskScheduler {
std::priority_queue tasks_;

public:
void add_task(int priority, const std::string& name, std::function action) {
tasks_.push({priority, name, action});
}

void run_all() {
while (!tasks_.empty()) {
Task task = tasks_.top();
tasks_.pop();

std::cout << "Executing task: " << task.name
<< " (priority: " << task.priority << ")\n";
task.action();
}
}
};

void task_scheduler_example() {
TaskScheduler scheduler;

scheduler.add_task(1, "Low priority", []() {
std::cout << "Low priority task executed\n";
});

scheduler.add_task(5, "High priority", []() {
std::cout << "High priority task executed\n";
});

scheduler.add_task(3, "Medium priority", []() {
std::cout << "Medium priority task executed\n";
});

scheduler.run_all();
}

双端队列可以实现滑动窗口算法。

#include

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_example() {
std::vector nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;

auto result = max_sliding_window(nums, k);

std::cout << "Sliding window maximum:\n";
for (int val : result) {
std::cout << val << " ";
}
std::cout << "\n";
}

容器适配器提供了简洁的接口来实现常见的数据结构，是算法实现的重要工具。