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