Задача «Trie»

Справка:

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 и обхода его с помощью итератора

Блок задач

Темы

Сложность 6