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

Question

В этом вопросе я не спрашиваю, как это сделать, но КАК ЭТО СДЕЛАНО.
Я пытаюсь (в качестве примера) реализовать простую карту, и хотя у меня нет проблем с реализацией ссылок и их поведения (как найти следующее место для вставки новой ссылки и т. д.) Я застрял с проблемой, как реализовать итерации по карте.Когда вы думаете об этом и смотрите на std :: map, эта карта может возвращать начало и конец итератора.Как?Особенно конец?
Если карта это дерево, как вы можете сказать, какая ветвь этой карты является концом?Я просто не понимаю этого.Как перебрать карту?Начиная с вершины дерева и что дальше?Идти и перечислить все слева?Но эти узлы слева также имеют ссылки справа.Я действительно не знаю.Я буду очень рад, если кто-нибудь сможет мне это объяснить или дать ссылку, чтобы я мог прочитать об этом.

Answer 1

A 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_ или что-то подобное).

Answer 2

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

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

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

Answer 3

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

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 () или используете оператор [], но вам никогда не нужно напрямую обращаться к представлению дерева.

Answer 4

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

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

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

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