How to make tree structure with custom selection of underlying container?

Question

I try to make a templated Trie structure. It represents tree in internal private struct Node, which contains TElem, bool which indicates that this particular node is a terminal and a vector of children:

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

    Node root_;
};

Now I'd like to make another template parameter that would make possible to select another underling container, e.g. list. How can it be done?

template template parameters http://stackoverflow.com/questions/213761/what-are-some-uses-of-template-template-parameters-in-c. — juanchopanza, Aug 03 '12 at 10:59
See my last edit. It allows to chose an allocator class template without exposing `Node`. — juanchopanza, Aug 03 '12 at 11:49

juanchopanza · Accepted Answer · 2012-08-03T11:48:53.080

2

With template template parameters (untested code, but the general idea should be OK):

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_;
};

then

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

edited Aug 03 '12 at 11:48

answered Aug 03 '12 at 11:01

juanchopanza

223,364
34
402
480

Tahnk you, after some improvements (you forgot second template parameter `Allocator`) everything works fine. :) – Archie Aug 03 '12 at 11:16
@Archie and I guess one would need a nested template template parameter for the allocator too (unless you can keep that fixed to `std::allocator`. – juanchopanza Aug 03 '12 at 11:25
@Archie well, it took me a while to remind myself how to do this! – juanchopanza Aug 03 '12 at 11:50

How to make tree structure with custom selection of underlying container?

1 Answers1