Use member types to declare variable

[TylerH]

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:

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?

 

[AlephZero]

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.

 

[TylerH]

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).

That's exactly what I'm doing. I'm developing a container (trie) that uses a map for underlying storage.

#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?

 

[AlephZero]

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?

Why not define a typedef for the typename?

typedef typename std::map<T, node<T, U...>>::iterator trie_iterator;

or whatever you want to call it.

 

[TylerH]

I finally took the time to finish it. Here it is if anyone wants to use it. It's public domain.

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