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

Question

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

Answer 1

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

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

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

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

Answer 2

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

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; 

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

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

Answer 3

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 4

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

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

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

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