c++ - 如何通过自定义选择底层容器来制作树结构？

Question

我尝试制作一个模板化的 Trie 结构。它表示内部私有(private)结构 Node 中的树，其中包含 TElem，bool 表示此特定节点是一个终端和子 vector :

template<typename TElem>
class Trie
{
    // ...
private:
    struct Node
    {
        TElem elem;
        bool isTerminal;
        std::vector<std::shared_ptr<Node>> children;
    };

    Node root_;
};

现在我想制作另一个模板参数，可以选择另一个底层容器，例如列表。怎么做到的？

Answer 1

With template 模板参数(未经测试的代码，但总体思路应该没问题):

template <typename TElem, 
          template <typename, typename> class Cont
          template <typename> class Allocator=std::allocator>
class Trie {
 private:
    struct Node
    {
        typedef std::shared_ptr<Node> NodePtr_;
        TElem elem;
        bool isTerminal;
        Cont<NodePtr_, Allocator<NodePtr_>> children;
    };

    Node root_;
};

然后

Trie<int, std::list> myTrie = ....;