字典树Trie

#include <memory>

#include <array>

#include <string>

template<typename Functor>

class TrieNode

public:

    TrieNode():

      m_is_end(false),

      m_pfun(nullptr),

      m_children(256, nullptr)

{}

    explicit TrieNode(std::shared_ptr<Functor> pfunc):

      m_children(256, nullptr),

      m_is_end(false),

      m_pfun(pfunc)

{}

    TrieNode(const TrieNode&)            = delete;

    TrieNode(TrieNode&&)                 = delete;

    TrieNode& operator=(const TrieNode&) = delete;

    TrieNode& operator=(TrieNode&&)      = delete;

    ~TrieNode()                          = default;

    std::vector<std::shared_ptr<TrieNode>> m_children;

    bool                     m_is_end;

    std::shared_ptr<Functor> m_pfun;

};

template<typename NodeFunctor>

class Trie

public:

    Trie():root(std::make_shared<TrieNode<NodeFunctor>>())

{}

    Trie(const Trie&)            = delete;

    Trie(Trie&&)                 = delete;

    Trie& operator=(const Trie&) = delete;

    Trie& operator=(Trie&&)      = delete;

    ~Trie()                      = default;

    void insert(const std::string& word, const NodeFunctor& node_functor)

        if (word.empty() || (nullptr == root))

            return;

        std::shared_ptr<TrieNode<NodeFunctor>> node = root;

        for (const char& c : word)

            uint8_t index = static_cast<uint8_t>(c);

            if (nullptr == node->m_children[index])

                node->m_children[index] = std::make_shared<TrieNode<NodeFunctor>>();

            node = node->m_children[index];

        node->m_is_end = true;

        node->m_pfun   = std::make_shared<NodeFunctor>(node_functor);

        return;

    bool find_word(std::shared_ptr<TrieNode<NodeFunctor>>& p_out_node, const std::string& word) const

        std::shared_ptr<TrieNode<NodeFunctor>> pnode = root;

        for (const char& c : word)

            uint8_t index = static_cast<uint8_t>(c);

            if (nullptr == pnode->m_children[index])

                return false;

            pnode = pnode->m_children[index];

        if (pnode->m_is_end)

            p_out_node = pnode;

        return pnode->m_is_end;

    void clear()

        root = std::make_shared<TrieNode<NodeFunctor>>();

        return;

    bool empty()

        if (nullptr != root)

            for (const auto& child: root->m_children)

                if (nullptr != child)

                    return false;

        return true;

private:

    std::shared_ptr<TrieNode<NodeFunctor>> root;

};