Konwersja wskaźnika do iteratora

Czym jest iterator w STL każdy wiedzieć powinien.

Mogę wspomnieć ze jest to typ z zachowaniem podobnym do wskaźnika, który służy do poruszania się po kontenerach biblioteki standardowej, ale nie jest to wskaźnik, mimo iż w większości implementacjach jest to opakowany w obiekt wskaźnik.

Kilka flejmów na ten temat można znaleźć w usenetowych archiwach pl.comp.lang.c ;)

Konwersja (słowo tutaj zbytnio nie pasuje) iteratora wskazującego na dany element kontenera do typowego wskaźnika jest bardzo prosta. Wystarczy pobrać adres elementu z dereferencji iteratora:

Obj* p = &(*it);	// nawiasy nie sa konieczne

Jak szybko i prosto dokonać konwersji w drugą stronę?

Nieraz mamy “wyłuskany” wskaźnik z iteratora, a potrzebujemy z powrotem iterator. Co wtedy zrobić?

Problem dosyć złożony, ale można kilka prostych sposób znaleźć, jak chociażby przeiterowanie kontenera i porównanie wskaźników do każdego elementu lub przeszukanie kontenera pod kryterium występowania w nim elementu na jaki wskazuje nasz wskaźnik.

Dla jasności przykładów, załóżmy że mamy jakiś kontener i wskaźnik, wskazujący na jakiś element kontenera:

vector vec;
for(int i = 0; i < 10; i++)
	vec.push_back(i);

vector::iterator it = vec.begin();
std::advance(it, 3);

int* ptr = &*it;

Niektóre metody kontenera przyjmują jako argument referencje do danego elementu, więc w takim przypadku nie ma problemu z przekazaniem dereferencji wskaźnika.

Dereferencji wskaźnika możemy także użyć wraz algorytmem find, aby otrzymać odpowiadający danemu elementowi iterator.

vector::iterator result;
result = std::find(vec.begin(), vec.end(), *ptr);

W kolejnych naszych zabawach pomocny może okazać się prosty funktor porównujący nasz wskaźnik z elementami kontenera:

template<typename T>
class pointers_equal : public std::unary_function {
public:
	pointers_equal(const T* ptr) : m_ptr(ptr) {}
	bool operator()(const T& element) { return &element == m_ptr; }
private:
	const T* m_ptr;
};

Jak wspomniałem, można przeszukać kontener np. za pomocą find_if porównując wskaźniki do elementów, w wyniku otrzymamy odpowiedni iterator lub end() (gdy nasz wskaźnik nie jest poprawny - nie wskazuje na żaden element zawarty w kontenerze):

vector::iterator result;
result = std::find_if(vec.begin(), vec.end(), pointers_equal(ptr));

Ogólnie w większości algorytmów i metod kontenera _*if można zastosować powyższy funktor, nie powinno wystąpić żadnych powikłań w sytuacji, gdy nasz wskaźnik nie wskazuje na żaden element kontenera.

W niektórych przypadkach takie szukanie elementu może być kosztowne. Dlatego można pomyśleć o innym sposobie, który Mozę się nadać do konkretnego przypadku.

W szczególnych przypadkach, takich jak mój, gdzie mam pewność, że wskaźnik wskazuje na element kontenera, a kontener jest vectorem, czyli wszystkie elementy kontenera znajdują się w jednym ciągłym kawałku pamięci, to mogę skorzystać z arytmetyki na wskaźnikach.

W sumie wskaźnik nie musi być wtedy valid, bo można to łatwo sprawdzić:

bool valid = ptr >= &vec.first() && ptr<= &vec.last();

Mając nasz wskaźnik i wskaźnik pierwszego elementu możemy łatwo obliczyć dystans jaki dzieli element wskazywany przez wskaźnik od pierwszego elementu:

size_t offset = ptr - &vec.first();

a później juz prosto otrzymac iterator:

vector::iterator result = vec.begin() + offset;

lub bardziej “formalnie”:

vector::iterator result = vec.begin();
std::advance(result, offset);

Choć w moim przypadku vectro używany jest wewnętrznie przez klasę, na zewnątrz tylko vectorowe bebechy do łatwego iterowania po przechowywanych danych, czyli iteratory wraz z begin() i ()end(), operatorem indeksowania, więc może dodam dodatkowe metody przyjmujące wskaźniki, w tych miejscach, gdzie to konieczne. Od strony implementacyjnej tych metod to bez znaczenia czy przekazuje do nich wskaźnik czy iterator, bo operacja jakaś wykonywana jest na wskazywanym obiekcie. Uniknę wtedy narzutu na konwersje wskaźnik -> iterator.

Mnie problem z tytułową konwersją zaskoczył przy kompilacji kodu pod VC9, pod starym GCC3.x używałem konstruktora iteratora i działało dobrze. Pod VC konstruktor iteratora również przyjmuje jako argument wskaźnik, ale w wersji debug lub z ustawieniami secure, dodatkowo wskaźnik na kontener, pewnie do sprawdzania zakresu. Standard tego prawdopodobnie nie określa, wiec trzeba zrezygnować nie przenośnego sposobu z ctorem.

// 2008-11-08 19:49:20 +01:00

Kontynuując moje rozważania o iteratorach i wskaźnikach, chciałbym rzucić nieco więcej światła i nowych spostrzeżeń jakie mnie naszły po popełnieniu tego wpisu, po którym nie mogłem spokojnie zasnąć ;)

Rewidując ponownie ten problem pod katem wydajnościowym i nie tylko doszedłem do wniosku, że w ogóle taka operacja jest bez sensu, uzycie takiej operacji w kodzie to bad design. Tak, świadczy to o złym projekcie i należałoby się dobrze zastanowić co dalej zrobić.

Gdy mamy opcje: wskaźnik czy iterator, powinniśmy bez namysłu wybrać iterator i z niego korzystać. W sytuacji, gdzie jakiś powodów mamy sam wskaźnik, a potrzebnym nam jest iterator to należy pomyśleć o zmianie projektu lub umożliwić wykonanie danej usługi bezpośrednio na wskazywanym obiekcie, o ile oczywiście jest to możliwe do zrealizowania.

Do potwierdzenia bezsensowności rozważmy przedstawione w poprzedniej notce sposoby wyznaczania iteratora na podstawie wskaźnika przy wykorzystaniu algorytmy find i find_if z biblioteki standardowej, przy założeniu, że implementacja wykorzystuje wskaźniki wewnątrz iteratorów, a nasz wskaźnik wskazuje na istniejący w kontenerze element.

Końcowa wersja funkcji z find po wygenerowaniu i rozwiniecie kodu przez kompilator, mogłaby wyglądać następująco:

Obj* find(Obj* first, Obj* last, const Obj& val) {

	while (first != last && *first != val)
		++first;
	return first;

}

Jako argument val podajemy nasz wskaźnik, funkcja przechodzi przez wszystkie elementy do napotkania elementu na jaki wskazuje nasz wskaźnik, po czym zwraca ten sam wskaźnik.

W wyniku czego otrzymujemy wskaźnik, ten sam wskaźnik jaki mieliśmy, wiec nic nie otrzymaliśmy. Prócz wygenerowania zbędnego kodu i narzutu w czasie wykonania. Dodatkowo, prócz zbędnej pętli, której wykonanie rośnie liniowo ze wzrostem rozmiarów kontenera i dereferencjach w każdej iteracji, wykorzystywany jest operator porównania typu Obj, co przy “cięższym” typie może być trochę kosztowne.

Wersja z find_if będzie trochę lepsza:

Obj* find_if(Obj* first, Obj* last, const Obj* val) {

	while (first != last && first != val)
		++first;
	return first;

}

Tutaj tylko porównanie wskaźników, ale nadal wykonanie pętli jest zbędne, bo z góry znamy wynik.

Oczywiście sprawa wygląda całkiem inaczej, gdy wskaźnik nie wskazuje na żaden element kontenera tylko na inny obiekt, a my chcemy znaleźć wystąpienie tego elementu w kontenerze i otrzymać odpowiedni iterator.

W innym wypadku (konwersja) jest to czysta głupota, świadczącą o źle zaprojektowanym projekcie. Powinniśmy wystrzegać się takich bezsensownych operacji.

Dobrze, że w moim projekcie, łatwo da się rozwiązać problem wskaźnik -> iterator.