Praktyczna znajomość kontenerów dostępnych w standardowych bibliotekach języka C++ jest bardzo ważnym atrybutem dobrego programisty. W niniejszym artykule rzucimy trochę światła dziennego na iteratory kontenerów vector i deque. Wspomniane kontenery oferują nam bowiem bardzo zbliżoną funkcjonalność i bardzo często można je stosować wymiennie bez istotnej zmiany w wydajności.
Iteratory
Jak zapewne wiesz iterator jest to obiekt, który umożliwia dostęp sekwencyjny do wszystkich elementów kontenera. W przypadku kontenerów vector i deque dostęp ten nie jest ograniczony tylko do poprzednika i następnia, ale również umożliwia nam skok o dowolną ilość elementów do przodu bądź do tyłu.
Skoro wiemy co to jest iterator zastanówmy się teraz do czego możemy go wykorzystać.
Listowanie danych
Iterator jest bardzo wygodnym narzędziem do wszelkiego listowania danych:
typedef std::vector < int > DaneT;
DaneT dane;
for( DaneT::iterator i = dane.begin(); i != dane.end(); i++ )
{
printf( "%d, ", * i );
}
Inne zastosowania
Iteratory również stosuje się przy:
Powyższe zastosowania są oczywiste i wynikają de'facto z interfejsu jaki udostępnia nam dany kontener. Problemy mogą się pojawić gdy nasze zapotrzebowania okażą się znacznie bardziej wyrafinowane i nimi się teraz zajmiemy.
Definicja problemu
Załóżmy teraz, że mamy następującą sytuację:
W tym momencie powinno Ci się nasunąć następujące pytanie: czy zapamiętany iterator wskazuje nadal na poprawne dane? Możliwe odpowiedzi, które chodziły mi po głowie były następujące:
Rozwiewamy wątpliwości
Chcąc odpowiedzieć na wyżej postawione pytanie możemy wykorzystać trzy metody:
Analiza kodu jak wiadomo zazwyczaj jest czasochłonna, a gdy czas goni nas to opcja taka nie wchodzi w grę. Drugą możliwością jest poszukanie odpowiedzi w Internecie, jednak i to może wymagać sporego nakładu czasu oraz szanse na znalezienie odpowiedzi są stosunkowo małe dla tak sformułowanego pytania. Zatem najprostszym rozwiązaniem będzie po prostu napisanie małego programu. W celu zbadania zachowania iteratorów kontenera vector napisałem więc następujący program:
#include <vector>
#include <iostream>
using namespace std;
int main()
{
std::vector < int > liczby;
std::vector < int >::iterator it;
for( int i = 0; i < 10; i++ ) it = liczby.insert( liczby.end()
, i );
cout <<* it << endl;
for( int i = 10; i < 15; i++ ) liczby.insert( liczby.begin(), i );
cout <<* it << endl;
return 0;
}
W chwili, gdy poznałem odpowiedź stało się oczywiste, że takie zachowanie nie jest porządane - dane są nieprawidłowe i nie wskazują na żaden element należący do kontenera. Co więcej - iterator jest również niepoprawny i jest różny od wartości zwracanej przez metodę end() użytego kontenera.
Pojawiło się więc kolejne pytanie: jak uzyskać poprawny wynik? Odpowiedź na to pytanie jest bardzo prosta, ale wpaść na to można tylko wtedy, gdy zna się dobrze własności kontenerów C++. Wystarczy zamienić kontener std::vector na std::deque.
#include <deque>
#include <iostream>
using namespace std;
int main()
{
std::deque < int > liczby;
std::deque < int >::iterator it;
for( int i = 0; i < 10; i++ ) it = liczby.insert( liczby.end()
, i );
cout <<* it << endl;
for( int i = 10; i < 15; i++ ) liczby.insert( liczby.begin(), i );
cout <<* it << endl;
return 0;
}