[C++ STL] jak sprawdzić, czy iterator jest past-the-end

Jak sprawdzić, czy iterator nieznanego kontenera set jest iteratorem past-the-end ?

Porownaj z iteratorem wzietym z end(), np.

vector <int> wektor;
vector <int>::iterator it = wektor.end();

pozdrawiam
johny

A jeśli nie znam, który kontener jest właścicielem tego iteratora ? Iterator past-the-end posiada jakieś specjalne cechy ?

dodam, jeszcze że iterator jest typu set<void*>::iterator czyli _Rb_tree_iterator<void*, _Nonconst_traits<void*> >.

adf88 napisał(a)

A jeśli nie znam, który kontener jest właścicielem tego iteratora ? Iterator past-the-end posiada jakieś specjalne cechy ?

dodam, jeszcze że iterator jest typu set<void*>::iterator czyli _Rb_tree_iterator<void*, _Nonconst_traits<void*> >.

O ile ja sie orientuje, to KAZDY kontener w metodzie end() zwraca past-the-end, wiec nie wazne, ze nie wiesz jaki.

pozdrawiam
johny

No ale to end() trzeba wywołać na jakimś obiekcie, a jak NIE ZNAM KTÓRY TO

mam kiedyśtam zapisany iterator
set<void*>::iterator it = ...
i teraz potrzebuje odczytać wartość na jaką wskazuje, oraz wszystkie kolejne aż do końca używając operatora ++. Czy nie znając kontenera, do którego należy ten iterator moge jakoś sprawdzić, czy jest już ostatni ? Chce uniknąć zapisywania kontenera wraz z iteratorem.

A w czym problem, zeby przy ustawianiu iteratora zapamietac end() lub nawet wskaznik na kontener?

foflik napisał(a)

A w czym problem, zeby przy ustawianiu iteratora zapamietac end() lub nawet wskaznik na kontener?

Raczej mało eleganckie. Sam jestem ciekaw czy da się coś takiego napisać.

Teraz zalapalem - myslalem, ze nie znasz TYPU. Pomysl z zapamietaniem iteratora z end() wydaje mi sie najlepszy.

pozdrawiam
johny

Ja doszedlem do takiego tworu:

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main()
{
	const char  * tab[] = { "a", "b", "c", "d" };
	set<string> s( tab, tab+4 );
	set<string>::iterator i = s.begin();

	while(1)
	{
		if( ((std::set<string> *)i._Mycont)->end() == i )
		{
			cout << "koniec\n";
			break;
		}

		cout << *i << endl;
		i++;
	}

	system("PAUSE");
	return 0;
}

[C++ Error] HostMain.cpp(40): E2316 '_Mycont' is not a member of 'list<void *,allocator<void *> >'
Niestety, '_Mycont' hulnie na VC++, ja używam Buildera.

Pozostane przy zapisywaniu wskaźnika do kontenera wraz z iteratorem (nie zapisuje end()'a bo sie może zmieniać).
Chciałem tego uniknąć, gdyż zależy mi na szybkości pewnej funkcji. Funkcja ta przegląda wszystkie węzły drzewa i ewentualnie coś z nimi robi (np tworzy liste wszystkich liści). Każdy węzeł przechowuje wskaźniki do dzieci (innych węzłów lub liści) w kontenerze set. Drzewo może być nawet baardzo duże. Przeglądając je, zamiast rekurencji odkładam na stosie iteratory do węzłów - teraz będe potrzebował drugi stos na kontenery :)

Apropos _Rb_tree_iterator Borlanda, jest to wskaźnik do struktury _Rb_tree_node opakowany w funkcje inline. Struktura ta posiada 4 pola:
_Rb_tree_node *_M_parent;
_Rb_tree_node *_M_left;
_Rb_tree_node *_M_right;
_Value _M_value_field;

Nie bardzo wiem jak jest budowane drzewo set i nie wiem czy z tych wartości _M_parent, _M_left, _M_right można jakoś wywniskować czy jest to iterator end(). Pole _M_value_field przechowuje zawartość iteratora. Doświadczalnie, w iteratorze end() pole jest to wyzerowane jednak nie wiem czy to pewniak i wole nie ryzykować. Dokopałem się do funkcji odpowiedzialnej za inicjalizacje pamięci dla _M_value_field:

fragment _alloc.c

template <bool __threads, int __inst>
void* _STLP_CALL
__node_alloc<__threads, __inst>::_M_allocate(size_t __n) {
  void*  __r;
  _Obj * _STLP_VOLATILE * __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
  // #       ifdef _STLP_THREADS
  /*REFERENCED*/
  _Node_Alloc_Lock<__threads, __inst> __lock_instance;
  // #       endif
  // Acquire the lock here with a constructor call.
  // This ensures that it is released in exit or during stack
  // unwinding.
  if ( (__r  = *__my_free_list) != 0 ) {
    *__my_free_list = ((_Obj*)__r) -> _M_free_list_link;
  } else {
    __r = _S_refill(__n);
  }
  // lock is released here
  return __r;
}

jednak w tym miejscu stanąłem :/ i nie wiem czy zawsze będzie to wyzerowany obszar. Wygląda to jakby funkcja kożystała z już zaalokowanej pamięci (_S_free_list ?).