Итерация по карте

Представление итератора вашей карты полностью зависит от вас. Я думаю, что достаточно использовать один обернутый указатель на node. Например.:

template <typename T>
struct mymapiterator
{
  typename mymap<T>::node * n;
};

Или что-то подобное. Теперь mymap::begin() может вернуть такой экземпляр итератора, что n будет указывать на крайний левый узел. mymap::end() может возвращать экземпляр с n, указывающим на корень, вероятно, или на какой-то другой специальный узел, из которого все еще можно вернуться к крайнему правому узлу, чтобы он мог удовлетворить двунаправленную итерацию от конечного итератора.

Операция перемещения между узлами (operators++() и operator--() и т. д.) заключается в обходе дерева от меньших значений к большим или наоборот. Операция, которую вы, вероятно, уже реализовали при реализации операции вставки.

map реализован с использованием двоичного дерева поиска. Чтобы соответствовать требованиям сложности, это должно быть самобалансирующееся дерево, поэтому обычно используется красно-черное дерево, но это не влияет на то, как вы выполняете итерацию по дереву.

Чтобы прочитать элементы из двоичного дерева поиска в порядке от наименьшего к наибольшему, вам необходимо выполнить обход дерева по порядку. Рекурсивная реализация довольно проста, но не очень практична для использования в итераторе (итератору пришлось бы поддерживать внутренний стек, что сделало бы его копирование относительно дорогим).

Вы можете реализовать итеративный обход по порядку. Это реализация, взятая из библиотеки древовидных контейнеров, которую я написал некоторое время назад. NodePointerT — это указатель на узел, где узел имеет left_, right_ и parent_ указатели типа NodePointerT.

// Gets the next node in an in-order traversal of the tree; returns null
// when the in-order traversal has ended
template <typename NodePointerT>
NodePointerT next_inorder_node(NodePointerT n)
{
    if (!n) { return n; }

    // If the node has a right child, we traverse the link to that child
    // then traverse as far to the left as we can:
    if (n->right_)
    {
        n = n->right_;
        while (n->left_) { n = n->left_; }
    }
    // If the node is the left node of its parent, the next node is its
    // parent node:
    else if (n->parent_ && n == n->parent_->left_)
    {
        n = n->parent_;
    }
    // Otherwise, this node is the furthest right in its subtree; we 
    // traverse up through its parents until we find a parent that was a
    // left child of a node.  The next node is that node's parent.  If 
    // we have reached the end, this will set node to null:
    else
    {
        while (n->parent_ && n == n->parent_->right_) { n = n->parent_; }
        n = n->parent_;
    }
    return n;
}

Чтобы найти первый узел для итератора begin, вам нужно найти самый левый узел в дереве. Начиная с корневого узла, следуйте указателю левого дочернего элемента, пока не встретите узел, у которого нет левого дочернего узла: это первый узел.

Для итератора end вы можете установить указатель узла так, чтобы он указывал на корневой узел или на последний узел в дереве, а затем оставить в итераторе флаг, указывающий, что это конечный итератор (is_end_ или что-то в этом роде).

В целях сортировки карта ведет себя как отсортированный контейнер ключей/значений (также известный как словарь); вы можете думать об этом как о отсортированной коллекции пар ключ/значение, и это именно то, что вы получаете, когда запрашиваете итератор. Наблюдать:

map<string, int> my_map;
my_map["Hello"] = 1;
my_map["world"] = 2;
for (map<string, int>::const_iterator i = my_map.begin(); i != my_map.end(); ++i)
    cout << i->first << ": " << i->second << endl;

Как и любой другой тип итератора, итератор карты ведет себя как указатель на элемент коллекции, а для карты это std::pair, где first сопоставляется с ключом, а second сопоставляется со значением.

std::map использует внутренний бинарный поиск, когда вы вызываете его метод find() или используете оператор [], но вам никогда не понадобится прямой доступ к представлению дерева.

Одна большая хитрость, которую вы можете упустить, заключается в том, что итератору end() не нужно ни на что указывать. Это может быть NULL или любое другое специальное значение.

Оператор ++ устанавливает для итератора то же специальное значение, когда он проходит за конец карты. Тогда все работает.

Чтобы реализовать ++, вам может понадобиться сохранить указатели next/prev в каждом узле, или вы можете вернуться вверх по дереву, чтобы найти следующий узел, сравнив узел, который вы только что оставили, с самым правым узлом родителя, чтобы увидеть, нужно ли вам идти к этому родительскому узлу и т. д.

Не забывайте, что итераторы карты должны оставаться действительными во время операций вставки/стирания (пока вы не стерли текущий узел итератора).