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

Question

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

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

    Node root_;
};

现在我想制作另一个模板参数，可以选择另一个底层容器，例如list. 如何做呢？

Answer 1

带模板模板参数（未经测试的代码，但大体思路应该没问题）：

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 = ....;