http://en.wikipedia.org/wiki/Trie - префиксное дерево
http://www.cplusplus.com/reference/map/map/ - интерфейс std::map (схожий)
http://www.cplusplus.com/reference/iterator/iterator/ - базовый класс итератора
Реализовать набор классов:
1) class Trie - класс-контейнер, реализующий префиксное дерево
2) class SubTrie - класс, использующийся для доступа к частям префиксного дерева. Содержит информацию о начале и конце обхода части дерева с помощью итераторов.
3) class TrieIterator - класс-итератор, использующийся для обхода дерева
4) class ConstTrieIterator - константный аналог вышеописанного итератора
Примерный интерфейс классов:
template <class T> class Trie
{
public:
typedef TrieIterator<T> iterator;
typedef ConstTrieIterator<T> const_iterator;
typedef T value_type;
typedef std::string key_type;
Trie();
template <class InputIterator> Trie(InputIterator first, InputIterator last);
Trie(const Trie<T> & trie);
~Trie();
Trie<T> & operator= (const Trie & trie);
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
bool empty() const; //Test whether container is empty
size_t size() const;
value_type& operator[] (const key_type& k);
std::pair<iterator,bool> insert (const key_type& k, const value_type& val);
template <class InputIterator> void insert (InputIterator first, InputIterator last);
//удаление
void erase (iterator position);
size_t erase (const key_type& k);
void erase (iterator first, iterator last);
void swap (Trie& trie);
void clear(); //очистить структуру
//найти элемент
iterator find (const key_type& k);
const_iterator find (const key_type& k) const;
SubTrie<T> GetSubTrie(const key_type & subKey); // получить subtree
};
Практически полностью повоторяет интерфейс Trie, но является лишь классом доступа к Trie.
template <class T> class SubTrie
{
};
Итератор
template <class T> class TrieIterator : public std::iterator<std::forward_iterator_tag, std::pair<std::string, T&>>
{
public:
TrieIterator(value_type & x);
TrieIterator(const TrieIterator& mit);
TrieIterator& operator++();
TrieIterator operator++(int);
bool operator==(const TrieIterator& rhs);
bool operator!=(const TrieIterator& rhs);
value_type operator*();
value_type * operator->();
};
Константный итератор - по аналогии с TrieIterator
template <class T> class ConstTrieIterator
{
};
Пояснения:
value_type& operator[] (const key_type& k); Возвращает ссылку на элемент, если таковой имется. Если нет - добавляет элемент с таким ключем и дефолтным значением и возвращает ссылку на него.
std::pair<iterator,bool> insert (const key_type& k, const value_type& val); Возвращает итератор на новое значение + true, если создался новый элемент, false - если изменена значение существующего.
template <class InputIterator> void insert (InputIterator first, InputIterator last); Итераторы должны указывать на pair<key_type, value_type>
Проверка всех операций над Trie
Проверка всех операций над SubTrie
Проверка выделения SubTrie из Trie и обхода его с помощью итератора