Thread: Trie Problems

I'm trying to implement a trie using a recursive node based method. Each node contains a map of keys mapped to nodes corresponding to that key.

My problem, right now, is with dealing with the map and iterator classes in a template.

So far, all I've tried to test is the insert method. Here's the problem:

Code:

    void insert(typename T::iterator start, typename T::iterator end, U value)
    {
        if(start != end)
        {
            std::pair<T, node<T, U>> p(*start, node<T, U>()); // this gives an error, saying this constructor doesn't exist
            typename std::map<T, node<T, U>>::iterator t = _subnodes.insert(p).first;
            start++;
            t->second.insert(start, end, value);
        }
        else
        {
            _value = new U(value);
        }
    }

Obviously, I'm screwing up something. How should this be done?

Here's the entire class.

Code:

#include <iterator>
#include <map>

template<typename T, typename U>
class node
{
    public:
    node() : _value(nullptr) {}
    ~node()
    {
        delete _value;
        _subnodes.clear();
    }

    void insert(typename T::iterator start, typename T::iterator end, U value)
    {
        if(start != end)
        {
            std::pair<T, node<T, U>> p(*start, node<T, U>());
            typename std::map<T, node<T, U>>::iterator t = _subnodes.insert(p).first;
            start++;
            t->second.insert(start, end, value);
        }
        else
        {
            _value = new U(value);
        }
    }

    void erase(typename T::const_iterator start, typename T::const_iterator end)
    {
        typename std::map<T, node<T, U>>::iterator t = _subnodes.find(*start);

        if(t == _subnodes.end())
            return;

        start++;

        if(start == end)
            _subnodes.erase(t);
        else
            t->erase(start, end);
    }

    U find(typename T::const_iterator start, typename T::const_iterator end)
    {
        if(start != end)
        {
            typename std::map<T, node<T, U>>::iterator t = _subnodes.find(*start, node<T, U>()).first();
            start++;
            return t->find(start, end);
        }
        else
            return _value;
    }

    private:
    U *_value;
    std::map<T, node<T, U>> _subnodes;
};

T is supposed to be any sequence with a forward iterator. My design goals dictate that a string or vector should work.

I think I've found the root of my problem. I'm using T for the key type of the map when I should be using the type referenced by the iterators I'm using. So, how do I declare a map similar to this:

Code:

std::map<T::iterator::reference, node<T, U>> _subnodes;