Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Use member types to declare variable

  1. Dec 11, 2011 #1
    The STL containers have a lot of member types, so I assume they must be there for declaring variables of those types. However, I can't discern how exactly it is that I'm supposed to use those member types to declare a variable.

    For example:
    Code (Text):
    map<int, char> t;

    t::key_type u; // I want this to mean "int u." That is the purpose of the member type, isn't it?
     
  2. jcsd
  3. Dec 11, 2011 #2

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    The reason for key_type etc is to make the library code hardware-independent and general-purpose, not necessarily for you to use directly.

    The only time you would want to declare a variable of type key_type is if you were building your own contaner template based on map, or something similar. In that case, you don't know what type the key will be, and also you don't know how the map class represents keys internally. (For example the code that implements the map might treated all keys as bit strings, indepedent of what variable type the user declared them to be).

    If your code declares and uses a map<int, char> to store data (and that is the most common way that application programs use the container classes), you know the keys for your paticular map are ints (because you declared them to be that!), and you can use int variables for anything to do with keys.
     
  4. Dec 11, 2011 #3
    That's exactly what I'm doing. I'm developing a container (trie) that uses a map for underlying storage.

    Code (Text):
    #ifndef NODE_H
    #define NODE_H

    #include <functional>
    #include <iterator>
    #include <map>
    #include <tuple>

    template<typename T, typename... U>
    class node
    {
        public:
        node() : _value(nullptr) {}

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

        typedef T key_type;
        typedef std::tuple<U...> value_type;

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

    #endif // NODE_H
    I could type "typename std::map<T, node<T, U...>>::iterator" every time, but that's an insanely long type and it do any good if I decide to change _subnodes from map to something else. Is there any other way?
     
  5. Dec 12, 2011 #4

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Why not define a typedef for the typename?

    Code (Text):

    typedef typename std::map<T, node<T, U...>>::iterator trie_iterator;
    or whatever you want to call it.
     
  6. Apr 5, 2012 #5
    I finally took the time to finish it. Here it is if anyone wants to use it. It's public domain.
    Code (Text):
    #include <algorithm>
    #include <iterator>
    #include <map>
    #include <memory>
    #include <utility>

    template<class T, typename U>
    class trie
    {
        public:
        trie() : _root(_data) {}

        typedef typename std::map<T, U>::iterator iterator;
        typedef typename std::map<T, U>::reverse_iterator reverse_iterator;

        iterator begin()
        {
            return _data.begin();
        }

        iterator end()
        {
            return _data.end();
        }

        reverse_iterator rbegin()
        {
            return _data.rbegin();
        }

        reverse_iterator rend()
        {
            return _data.rend();
        }

        inline void erase(const T &key)
        {
            _root.erase(key.begin(), key.end());
        }

        inline iterator find(const T &key)
        {
            return _root.find(key.begin(), key.end());
        }

        inline std::pair<iterator, bool> insert(const T &key, const U &value)
        {
            auto t = _data.insert(std::pair<T, U>(key, value));
            _root.insert(key.begin(), key.end(), t.first);
            return t;
        }

        protected:
        class subtrie
        {
            public:
            subtrie(std::map<T, U> &data) : _data(data) {}

            inline void erase(const T &key)
            {
                erase(key.begin(), key.end());
            }

            void erase(typename T::const_iterator begin, typename T::const_iterator end)
            {
                typename std::map<typename T::const_iterator::value_type, subtrie>::iterator t = _subtries.find(*begin);
                begin++;
                if(begin != end)
                    t->second.erase(begin, end);
                else
                    _subtries.erase(t);
            }

            inline iterator find(const T &key)
            {
                return find(key.begin(), key.end());
            }

            iterator find(typename T::const_iterator begin, typename T::const_iterator end)
            {
                if(begin != end)
                {
                    typename std::map<typename T::const_iterator::value_type, subtrie>::iterator t = _subtries.find(*begin);

                    if(t != _subtries.end())
                    {
                        begin++;
                        return t->second.find(begin, end);
                    }
                    else
                        return _data.end();
                }
                else
                    return _it;
            }

            inline void insert(iterator it)
            {
                insert(it->first.begin(), it->first.end(), it);
            }

            void insert(typename T::const_iterator begin, typename T::const_iterator end, const iterator it)
            {
                if(begin != end)
                {
                    typename std::map<typename T::const_iterator::value_type, subtrie>::iterator t = _subtries.insert(typename std::map<typename T::const_iterator::value_type, subtrie>::value_type(*begin, subtrie(_data))).first;
                    begin++;
                    t->second.insert(begin, end, it);
                }
                else
                    _it = it;
            }

            private:
            iterator _it;
            std::map<T, U> &_data;
            std::map<typename T::const_iterator::value_type, subtrie> _subtries;
        };

        private:
        subtrie _root;
        std::map<T, U> _data;
    };
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook