Trie Problems

This is a discussion on Trie Problems within the C++ Programming forums, part of the General Programming Boards category; I'm trying to implement a trie using a recursive node based method. Each node contains a map of keys mapped ...

  1. #1
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587

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

  2. #2
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    T is supposed to be any sequence with a forward iterator. My design goals dictate that a string or vector should work.

  3. #3
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    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;

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Patricia trie - skipping redundant entries
    By grigorianvlad in forum C++ Programming
    Replies: 4
    Last Post: 09-24-2010, 07:24 PM
  2. trie algorithm question..
    By transgalactic2 in forum C Programming
    Replies: 10
    Last Post: 04-04-2009, 10:26 PM
  3. fread problems or memory problems
    By Lechuza in forum C Programming
    Replies: 1
    Last Post: 03-22-2009, 12:45 PM
  4. Hash vs Trie
    By faxo in forum C Programming
    Replies: 2
    Last Post: 08-13-2007, 01:34 AM
  5. Linking problems, class problems
    By Kheila in forum C++ Programming
    Replies: 12
    Last Post: 11-22-2005, 12:47 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21