Jak działa Iterator w zestawie

Question

Zastanawiam się, w jaki sposób iteratory ustawione w C++ działają w STL. Domyślam się, że zestaw jest zaimplementowany przy użyciu drzewa wyszukiwania binarnego, co oznacza, że ​​iteratory wykonują w trybie inordacji to drzewo. Ale moje pytanie brzmi: kiedy robią to przechodzenie, na samym początku , kiedy robimy to: it = s.begin() i przechowujemy wewnętrznie przechodzące wskaźniki w rodzaju stosu i odnosimy się tylko do tej struktury danych przy każdej inkrementacji w iteratorze lub inkrementacja w iteratorze powoduje nowe przejście na drzewo.

Znaczy kiedy zainicjować jak

 set<int> s; 
    set<int>::iterator it; 

//and then use it like: 

     for(it = s.begin(); it!=s.end();) 
     { 
      dosth(); 
      ++it;  // does this do a inorder traversal of the tree again to find the next 
        // node or it gets the next node in the tree by reading the internal 
        // data structure(of inorder traversal) which is created when we do s.begin(). 
     } 

Answer 1

Jest zależna od implementacji. Jednak iteratory std :: set są unieważniane tylko wtedy, gdy iterator odwołuje się do elementu, który został usunięty z zestawu. W związku z tym można myśleć o iteratorach std::set jako węzłach w drzewie. ++ przesuwa go w jednym kierunku ruchu drzewa i - przesuwa go w drugi.

Należy zauważyć, że iteratory zwracane są przez inne funkcje, które są begin, więc ich ważność nie jest ograniczona do samego rozpoczęcia/zakończenia iteracji.

Answer 2

To interesujące pytanie. Jak zauważył Nicol, jest to zależne od implementacji i podczas wdrażania własnego zestawu musisz zdecydować, czy preferujesz mniejsze iteratory, czy szybsze przejście (możesz umieścić więcej danych w iteratorach, aby przyspieszyć).

Na mojej platformie (64-bitowej) std::set<T>::iterator ma rozmiar 8 bajtów, co sugeruje, że po prostu wskaźnik pozostaje w aktualnym węźle. Jeśli zestaw jest zaimplementowany przy użyciu jakiegoś drzewa, to inkrementacja iteratora zdecydowanie nie jest operacją O (1) i wymaga przechodzenia do logowania (N) dodatkowych węzłów (jeśli mówimy o zrównoważonym drzewie). Sprawdziłem także szybkość działania ++it dla różnych węzłów i nie jest stała co sugeruje dodatkowe ruchy. Jest to całkowicie w porządku dla kontenera ogólnego przeznaczenia, ponieważ spełnia oczekiwania dotyczące złożoności drzewa i ludzie zazwyczaj zakładają, że iteratory są tak małe, jak to tylko możliwe. Jeśli zastosujesz standardowe rekursyjne przechodzenie drzewa, to jest dokładnie to samo, po prostu ukrywasz dodatkowe wizyty w węźle na stosie.

Proszę spojrzeć na Implementing an iterator over a binary search tree, aby uzyskać więcej informacji na temat wdrażania własnego iteratora drzewa.