Pointer to iterator

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.

5 przemyśleń nt. „Pointer to iterator”

  1. Najlepiej to tylko korzystac z iteratora, a sytuacje gdzie z jakis powodow otrzymalismy sam wskaznik, a potrzeba iteratora to nalezy zmienic projekt lub umozliwic wykonanie danej uslugi bezposrednio na wskazywanym obiekcie, powinno rozwiazac problemy i nie generowac zbednego narzutu.
    Wiecej o nowych przemysleniach napisze w nastepnej notce, jak wroce z uniwerku, bo po napisaniu biezacej nie moglem spokojnie zasnac ;)

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *