iterator we własnych kontenerach

Witajcie

Chciałbym stworzyć własny kontener danych, działający powiedzmy na zasadzie drzewa, a także dorobić do niego iterator wejściowy. Mógłbym zdefiniować własną klasę Iterator, dorobić wszystkie potrzebne definicje operatorów i w ten sposób posługiwać się iteratorami, lecz zastanawiam się, czy nie ma możliwośći wykorzystania w tym celu standardowej biblioteki <iterator>? A jeśli jest -> czy moglibyście zaprezentować jak, wykorzystując ją, zdefiniować własny typ iteratora, odpowiedni dla kontenera?

http://stackoverflow.com/questions/16434681/stl-compatible-iterators-for-custom-containers
http://stackoverflow.com/questions/4857892/defining-iterator-of-my-own-container
http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-iterator-define.html
http://www.dreamincode.net/forums/topic/58468-making-your-own-iterators/

Dzięki za pomoc, gdyż choć większość z tych linków już widziałem, pierwszy mi bardzo pomógł. Mam jednak kolejne pytanie. W pierwszym linku w przykładzie autor definiuje iterator do tablicy. Definiowanie operatora inkrementacji (post czy pre) jest dla takiego obiektu bardzo proste. A czy ktoś mógłby mi pomóc, ze zdefiniowaniem takiego operatora dla drzewa BST? Nie mam pojęcia jak wymyśleć algorytm do poruszania się po elementach drzewa w kolejności, nie mogąc użyć rekurencji...

Szukasz ty cos w google?
http://en.wikipedia.org/wiki/Tree_traversal#Types drugi akapit.

node *increment(node *cur)
  {
   if(cur->right)
     {
      cur=cur->right;
      while(cur->left) cur=cur->left;
     }
   else
     {
      node *tmp=cur->parent;
      while(cur==tmp->right) tmp=(cur=tmp)->parent;
      if(cur->right!=tmp) cur=tmp;
     }
    return cur;
   }

n0name_l napisał(a):

Szukasz ty cos w google?
http://en.wikipedia.org/wiki/Tree_traversal#Types drugi akapit.

Co innego to przechodzenie rekurencyjnie po wszystkich elementach drzewa, co jest proste i bezbolesne, a co innego to inkrementacja iteratora, który nie ma jak odwoływać się rekurencyjnie do pozostałych poddrzew, dlatego też TAK, mam za sobą długie godziny szukania w google, które nie dały mi konkretnej odpowiedzi jak to szukanie zrealizować, biorąc pod uwagę możliwe modyfikacje drzewa pomiędzy inkrementacjami iteratora (odpada zapisywanie pozycji w stacku). Tym bardziej dziękuję za powyższy algorytm

Jeszcze jedno pytanie specyficzne dla drzewa - jak zdefiniować metodę end()? Mam problem z wymyśleniem jak zdefiniować iterator "pierwszy za ostatnim" (past the end) -> nie może to być null, bo jest ich w drzewie dużo, nie może to być ostatni element, gdyż w pętli
for(it=drzewo.begin();it!=drzewo.end();++it)
zostałby pominięty. Próbowałem zdefiniować obiekt statyczny, który umieszczałbym za ostatnim elementem, lecz musi on być zainicjalizowany przez użytkownika klasy...
Będę wdzięczny za pomoc

http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/classstd_1_1___rb__tree.html

Jeszcze jedno pytanie specyficzne dla drzewa - jak zdefiniować metodę end()?
Pokaż co zrobiłeś do tej pory.