C++设计模式之组合模式中适用缓存机制提高遍历与查找速度

在组合设计模式中，为了提高反复遍历和查找的速度，可以引入缓存机制。缓存机制可以通过存储已经遍历过的子组件或计算过的结果来减少重复操作的开销。以下是一个示例，展示了如何在组合模式中使用缓存机制来提高性能。

示例：组合设计模式中的缓存机制

1. 组件接口

定义一个组件接口 Component，所有组件（叶子和组合节点）都实现这个接口。

#include <vector>
#include <unordered_map>
#include <iostream>
#include <string>

class Component {
public:
    virtual void operation() = 0;
    virtual void add(Component* component) {}
    virtual void remove(Component* component) {}
    virtual Component* find(const std::string& name) = 0;
    virtual ~Component() {}
    std::string name;
};

2. 叶子节点

定义一个叶子节点 Leaf，实现 Component 接口。

class Leaf : public Component {
public:
    Leaf(const std::string& name) {
        this->name = name;
    }
    void operation() override {
        std::cout << "Leaf " << name << " operation" << std::endl;
    }
    Component* find(const std::string& name) override {
        return (this->name == name) ? this : nullptr;
    }
};

3. 组合节点

定义一个组合节点 Composite，实现 Component 接口。组合节点管理子组件，并且在查找时使用缓存。

class Composite : public Component {
public:
    Composite(const std::string& name) {
        this->name = name;
    }
    void operation() override {
        std::cout << "Composite " << name << " operation" << std::endl;
        for (auto& component : components) {
            component->operation();
        }
    }
    void add(Component* component) override {
        components.push_back(component);
    }
    void remove(Component* component) override {
        components.erase(std::remove(components.begin(), components.end(), component), components.end());
    }
    Component* find(const std::string& name) override {
        // 检查缓存
        if (cache.find(name) != cache.end()) {
            return cache[name];
        }

        // 遍历子组件查找
        for (auto& component : components) {
            if (component->find(name) != nullptr) {
                cache[name] = component;
                return component;
            }
        }
        return nullptr;
    }

private:
    std::vector<Component*> components;
    std::unordered_map<std::string, Component*> cache;
};

4. 主程序

创建一个组合节点，并添加叶子节点，然后演示如何使用缓存机制提高查找速度。

int main() {
    Composite* root = new Composite("Root");
    root->add(new Leaf("Leaf1"));
    root->add(new Leaf("Leaf2"));

    Composite* subComposite = new Composite("SubComposite");
    subComposite->add(new Leaf("Leaf3"));
    subComposite->add(new Leaf("Leaf4"));
    root->add(subComposite);

    // 第一次查找，缓存未命中
    std::cout << "Searching for 'Leaf3' (first time)..." << std::endl;
    Component* found = root->find("Leaf3");
    if (found) {
        found->operation();
    } else {
        std::cout << "Not found" << std::endl;
    }

    // 第二次查找，缓存命中
    std::cout << "Searching for 'Leaf3' (second time)..." << std::endl;
    found = root->find("Leaf3");
    if (found) {
        found->operation();
    } else {
        std::cout << "Not found" << std::endl;
    }

    delete root;
    return 0;
}

解释

1. 缓存机制：在 Composite 类中，我们使用 std::unordered_map 来存储子组件的查找结果。当查找操作发生时，首先检查缓存中是否已经存在该组件。如果存在，直接返回缓存中的结果；如果不存在，则遍历子组件进行查找，并将结果存入缓存。

2. 性能提升：通过使用缓存机制，可以避免反复遍历子组件，从而显著提高查找操作的速度。

3. 适用场景：这种缓存机制特别适用于树形结构中频繁进行相同查找操作的场景。通过缓存已经查找过的结果，可以减少不必要的递归遍历，提升系统性能。

通过这种方式，你可以在组合设计模式中有效地利用缓存机制来提高反复遍历和查找的速度。