Po co używać iteratorów zamiast indeksów tablicowych?

Weź następujące dwa wiersze kodu:

for (int i = 0; i < some_vector.size(); i++)
{
    //do stuff
}

I to:

for (some_iterator = some_vector.begin(); some_iterator != some_vector.end();
    some_iterator++)
{
    //do stuff
}

Powiedziano mi, że preferowany jest drugi sposób. Dlaczego to dokładnie jest?

Pierwsza forma jest skuteczna tylko wtedy, gdy vector.size () jest szybką operacją. Odnosi się to do wektorów, ale nie do list, na przykład. Co również planujesz zrobić w ciele pętli? Jeśli planujesz uzyskać dostęp do elementów jak w

T elem = some_vector[i];

wtedy przyjmujesz założenie, że kontener operator[](std::size_t)zdefiniował. To samo dotyczy wektora, ale nie dotyczy innych pojemników.

Zastosowanie iteratorów przybliża Cię do niezależności kontenera . Nie przyjmujesz założeń dotyczących możliwości losowego dostępu lub szybkiej size()operacji, tylko to, że kontener ma możliwości iteratora.

Możesz dodatkowo ulepszyć swój kod, używając standardowych algorytmów. W zależności od tego, co próbujesz osiągnąć, możesz zdecydować się na użyciestd::for_each() ,std::transform() i tak dalej. Używając standardowego algorytmu zamiast wyraźnej pętli, unikniesz ponownego wynalezienia koła. Twój kod prawdopodobnie będzie bardziej wydajny (jeśli wybrany zostanie odpowiedni algorytm), poprawny i będzie można go ponownie wykorzystać.

Jest to część nowoczesnego procesu indoktrynacji w C ++. Iteratory to jedyny sposób na iterację większości pojemników, więc używasz go nawet z wektorami, aby uzyskać właściwy sposób myślenia. Poważnie, to jedyny powód, dla którego to robię - nie sądzę, żebym kiedykolwiek zastępował wektor innym rodzajem pojemnika.

Myślę, że indeks tablicy jest bardziej czytelny. Odpowiada składni używanej w innych językach i składni używanej w przypadku starych tablic C. Jest również mniej gadatliwy. Wydajność powinna być myta, jeśli twój kompilator jest dobry i nie ma prawie żadnych przypadków, w których ma to znaczenie.

Mimo to wciąż często używam iteratorów z wektorami. Uważam, że iterator jest ważną koncepcją, dlatego promuję go, kiedy tylko mogę.

ponieważ nie wiążesz swojego kodu z konkretną implementacją listy some_vector. jeśli używasz indeksów tablicowych, musi to być jakaś forma tablicowa; jeśli używasz iteratorów, możesz użyć tego kodu w dowolnej implementacji listy.

Wyobraź sobie, że some_vector jest zaimplementowany z połączoną listą. Następnie żądanie elementu na i-tym miejscu wymaga wykonania operacji i, aby przejść przez listę węzłów. Teraz, jeśli używasz iteratora, ogólnie mówiąc, dołoży wszelkich starań, aby być tak wydajnym, jak to możliwe (w przypadku listy połączonej utrzyma wskaźnik do bieżącego węzła i będzie go przesuwał w każdej iteracji, wymagając tylko pojedyncza operacja).

Zapewnia to dwie rzeczy:

• Abstrakcja użycia: chcesz po prostu iterować niektóre elementy, nie obchodzi Cię, jak to zrobić
• Występ

Będę tutaj orędownikiem diabłów i nie polecam iteratorów. Głównym powodem jest to, że cały kod źródłowy, nad którym pracowałem, od tworzenia aplikacji komputerowych po tworzenie gier, nie musiałem używać iteratorów. Przez cały czas nie były one wymagane, a po drugie ukryte założenia, bałagan w kodzie i koszmary debugowania, które otrzymujesz z iteratorami, sprawiają, że są doskonałym przykładem tego, że nie można ich używać w aplikacjach wymagających szybkości.

Nawet z punktu widzenia konserwacji są bałaganem. To nie z ich powodu, ale z powodu aliasingu, który ma miejsce za sceną. Skąd mam wiedzieć, że nie zaimplementowałeś własnej listy wirtualnych wektorów lub tablic, która robi coś zupełnie innego niż standardy. Czy wiem, jaki typ jest obecnie w trakcie działania? Czy przeciążyłeś operatora? Nie miałem czasu na sprawdzenie całego kodu źródłowego. Do diabła, czy w ogóle wiem, jakiej wersji STL używasz?

Kolejnym problemem związanym z iteratorami jest nieszczelna abstrakcja, chociaż istnieje wiele stron internetowych, które szczegółowo o tym dyskutują.

Przepraszam, nie widziałem i nadal nie widziałem żadnego punktu w iteratorach. Jeśli odciągają od ciebie listę lub wektor, to w rzeczywistości powinieneś już wiedzieć, z jakim wektorem lub listą masz do czynienia, jeśli tego nie zrobisz, to po prostu przygotujesz się na wspaniałe sesje debugowania w przyszłości.

Możesz użyć iteratora, jeśli zamierzasz dodawać / usuwać elementy do wektora podczas iteracji.

some_iterator = some_vector.begin(); 
while (some_iterator != some_vector.end())
{
    if (/* some condition */)
    {
        some_iterator = some_vector.erase(some_iterator);
        // some_iterator now positioned at the element after the deleted element
    }
    else
    {
        if (/* some other condition */)
        {
            some_iterator = some_vector.insert(some_iterator, some_new_value);
            // some_iterator now positioned at new element
        }
        ++some_iterator;
    }
}

Jeśli korzystasz z indeksów, będziesz musiał przetasować elementy w górę / w dół w tablicy, aby obsłużyć wstawienia i usunięcia.

Rozdzielenie obaw

Bardzo miło jest oddzielić kod iteracyjny od „podstawowej” kwestii pętli. To prawie decyzja projektowa.

Rzeczywiście, iteracja według indeksu wiąże cię z implementacją kontenera. Pytanie o kontener do początku i końca iteratora umożliwia włączenie kodu pętli do użycia z innymi typami kontenerów.

Ponadto, w pewnymstd::for_each sensie, powiesz kolekcji, co robić, zamiast zadawać jej coś o jej wnętrznościach

Standard 0x wprowadzi zamknięcia, które znacznie ułatwią korzystanie z tego podejścia - spójrz na ekspresyjną moc np. Ruby [1..6].each { |i| print i; }...

Występ

Ale być może o wiele pilniejszym problemem jest to, że zastosowanie tego for_eachpodejścia daje możliwość równoległego wykonania iteracji - bloki wątków Intel mogą rozdzielić blok kodu na liczbę procesorów w systemie!

Uwaga: po odkryciu algorithmsbiblioteki, a zwłaszcza foreach, przeszedłem dwa lub trzy miesiące pisania śmiesznie małych struktur operatora pomocnika, które doprowadzą innych programistów do szaleństwa. Po tym czasie wróciłem do pragmatycznego podejścia - ciała o małej pętli nie zasługują na foreachnic więcej :)

Odwołaniem do iteratorów jest przeczytana książka „Extended STL” .

GoF ma mały akapit na końcu wzoru Iterator, który mówi o tej marce iteracji; nazywa się to „wewnętrznym iteratorem”. Spójrz też tutaj .

Ponieważ jest bardziej obiektowy. jeśli iterujesz z indeksem, zakładasz:

a) że te obiekty są uporządkowane
b) że te obiekty można uzyskać za pomocą indeksu
c) że przyrost indeksu uderzy w każdą pozycję
d) że ten indeks zaczyna się od zera

Za pomocą iteratora mówisz „daj mi wszystko, abym mógł z tym pracować”, nie wiedząc, na czym polega implementacja. (W Javie istnieją kolekcje, do których nie można uzyskać dostępu za pośrednictwem indeksu)

Ponadto dzięki iteratorowi nie musisz się martwić, że wyjdziesz poza granice tablicy.

Kolejną zaletą iteratorów jest to, że pozwalają lepiej wyrażać (i egzekwować) preferencje const. Ten przykład zapewnia, że ​​nie zmienisz wektora w środku pętli:

for(std::vector<Foo>::const_iterator pos=foos.begin(); pos != foos.end(); ++pos)
{
    // Foo & foo = *pos; // this won't compile
    const Foo & foo = *pos; // this will compile
}

Oprócz wszystkich innych doskonałych odpowiedzi ... intmoże nie być wystarczająco duży dla twojego wektora. Zamiast tego, jeśli chcesz użyć indeksowania, użyj size_typedla swojego kontenera:

for (std::vector<Foo>::size_type i = 0; i < myvector.size(); ++i)
{
    Foo& this_foo = myvector[i];
    // Do stuff with this_foo
}

Powinienem chyba zaznaczyć, że możesz również zadzwonić

std::for_each(some_vector.begin(), some_vector.end(), &do_stuff);

Iteratory STL są tam głównie, więc algorytmy STL, takie jak sort, mogą być niezależne od kontenera.

Jeśli chcesz po prostu zapętlić wszystkie wpisy w wektorze, użyj stylu pętli indeksu.

Jest mniej pisania i łatwiejsze do przeanalizowania dla większości ludzi. Byłoby miło, gdyby C ++ miał prostą pętlę foreach bez przesadzania z magią szablonów.

for( size_t i = 0; i < some_vector.size(); ++i )
{
   T& rT = some_vector[i];
   // now do something with rT
}
'

Nie sądzę, żeby miało to duże znaczenie dla wektora. Wolę sam korzystać z indeksu, ponieważ uważam, że jest on bardziej czytelny i możesz uzyskać dostęp przypadkowy, np. Przeskoczyć do przodu o 6 pozycji lub w razie potrzeby skoczyć do tyłu.

Chciałbym również odnieść się do elementu wewnątrz pętli w ten sposób, aby wokół tego miejsca nie było dużo nawiasów kwadratowych:

for(size_t i = 0; i < myvector.size(); i++)
{
    MyClass &item = myvector[i];

    // Do stuff to "item".
}

Korzystanie z iteratora może być dobre, jeśli uważasz, że w pewnym momencie w przyszłości może być konieczne zastąpienie wektora listą, a także wygląda bardziej stylowo dla maniaków STL, ale nie mogę wymyślić żadnego innego powodu.

Druga forma reprezentuje to, co robisz dokładniej. W twoim przykładzie tak naprawdę nie zależy ci na wartości i - wszystko, czego chcesz, to następny element w iteratorze.

Po tym, jak dowiedziałem się nieco więcej na temat tej odpowiedzi, zdaję sobie sprawę, że było to trochę nadmierne uproszczenie. Różnica między tą pętlą:

for (some_iterator = some_vector.begin(); some_iterator != some_vector.end();
    some_iterator++)
{
    //do stuff
}

I ta pętla:

for (int i = 0; i < some_vector.size(); i++)
{
    //do stuff
}

Jest dość minimalny. W rzeczywistości wydaje mi się, że składnia wykonywania pętli w ten sposób:

while (it != end){
    //do stuff
    ++it;
}

Iteratory odblokowują niektóre dość potężne funkcje deklaratywne, a w połączeniu z biblioteką algorytmów STL możesz robić całkiem fajne rzeczy, które są poza zakresem administrowania indeksem tablic.

Indeksowanie wymaga dodatkowej muloperacji. Na przykład vector<int> vkompilator konwertuje v[i]na &v + sizeof(int) * i.

Podczas iteracji nie musisz znać liczby elementów do przetworzenia. Potrzebujesz tego przedmiotu, a iteratory robią takie rzeczy bardzo dobrze.

Nikt jeszcze nie wspominał, że jedną z zalet indeksów jest to, że nie stają się one nieważne, gdy dodasz do ciągłego pojemnika, takiego jak std::vector , dzięki czemu możesz dodawać elementy do kontenera podczas iteracji.

Jest to również możliwe w przypadku iteratorów, ale musisz zadzwonić reserve(), a zatem musisz wiedzieć, ile elementów dołączysz.

Kilka dobrych punktów już. Mam kilka dodatkowych komentarzy:

1. Zakładając, że mówimy o standardowej bibliotece C ++, „wektor” oznacza kontener o swobodnym dostępie, który ma gwarancje macierzy C (losowy dostęp, układ pamięci contiguos itp.). Gdybyś powiedział „some_container”, wiele z powyższych odpowiedzi byłoby dokładniejszych (niezależność kontenera itp.).

2. Aby wyeliminować jakiekolwiek zależności związane z optymalizacją kompilatora, możesz przenieść some_vector.size () z pętli w indeksowanym kodzie, tak jak:

   const size_t numElems = some_vector.size ();
   dla (size_t i = 0; i 

3. Zawsze iteratory wstępnej inkrementacji i traktuj post-inkrementy jako wyjątkowe przypadki.

Więc zakładając i indeksowalne std::vector<> jak kontener, nie ma żadnego powodu, aby preferować jeden nad drugim, przechodząc kolejno przez kontener. Jeśli musisz często odwoływać się do starszych lub nowszych elemenentnych indeksów, wówczas indeksowana wersja jest bardziej odpowiednia.

Ogólnie rzecz biorąc, preferowane jest używanie iteratorów, ponieważ algorytmy je wykorzystują, a zachowanie może być kontrolowane (i domyślnie dokumentowane) poprzez zmianę typu iteratora. Lokalizacje tablic mogą być używane zamiast iteratorów, ale różnica składniowa będzie się utrzymywać.

Nie używam iteratorów z tego samego powodu, dla którego nie lubię instrukcji foreach. Mając wiele wewnętrznych pętli, trudno jest śledzić zmienne globalne / składowe bez konieczności pamiętania wszystkich lokalnych wartości i nazw iteratorów. Za użyteczne uważam użycie dwóch zestawów wskaźników na różne okazje:

for(int i=0;i<anims.size();i++)
  for(int j=0;j<bones.size();j++)
  {
     int animIndex = i;
     int boneIndex = j;


     // in relatively short code I use indices i and j
     ... animation_matrices[i][j] ...

     // in long and complicated code I use indices animIndex and boneIndex
     ... animation_matrices[animIndex][boneIndex] ...


  }

Nie chcę nawet skracać rzeczy takich jak „animation_matrices [i]” do jakiegoś losowego „iteratora” o nazwie anim_matrix, ponieważ wtedy nie możesz wyraźnie zobaczyć, z której tablicy pochodzi ta wartość.

• Jeśli lubisz być blisko metalu / nie ufasz szczegółom jego implementacji, nie używaj iteratorów.
• Jeśli podczas programowania regularnie zmieniasz jeden typ kolekcji na inny, użyj iteratorów.
• Jeśli trudno ci zapamiętać, jak iterować różne rodzaje kolekcji (być może masz w użyciu kilka typów z kilku różnych źródeł zewnętrznych), użyj iteratorów, aby ujednolicić sposób, w jaki chodzisz po elementach. Dotyczy to na przykład zamiany połączonej listy z listą tablic.

Naprawdę, to wszystko. To nie tak, że średnio zyskasz więcej zwięzłości w każdym kierunku, a jeśli zwięzłość naprawdę jest twoim celem, zawsze możesz polegać na makrach.

Jeśli masz dostęp do funkcji C ++ 11 , możesz także użyć pętli opartejfor na zakresie do iteracji po wektorze (lub dowolnym innym kontenerze) w następujący sposób:

for (auto &item : some_vector)
{
     //do stuff
}

Zaletą tej pętli jest to, że można uzyskać dostęp do elementów wektora bezpośrednio przez itemzmienną, bez ryzyka zepsucia indeksu lub popełnienia błędu przy dereferencji iteratora. Ponadto symbol zastępczy autozapobiega powtórzeniu rodzaju elementów kontenera, co jeszcze bardziej zbliża Cię do rozwiązania niezależnego od kontenera.

Uwagi:

• Jeśli potrzebujesz indeksu elementów w swojej pętli i operator[]istnieje on dla twojego kontenera (i jest dla ciebie wystarczająco szybki), lepiej idź pierwszy.
• forPętla oparta na zakresie nie może być używana do dodawania / usuwania elementów do / z kontenera. Jeśli chcesz to zrobić, lepiej trzymaj się rozwiązania zaproponowanego przez Briana Matthewsa.
• Jeśli nie chcesz zmieniać elementy w pojemniku, należy użyć słowa kluczowego constw następujący sposób: for (auto const &item : some_vector) { ... }.

Jeszcze lepsze niż „mówienie procesorowi, co ma robić” (imperatyw) jest „mówienie bibliotekom, co chcesz” (funkcjonalne).

Więc zamiast używać pętli powinieneś nauczyć się algorytmów obecnych w stl.

Dla niezależności kontenera

Zawsze używam indeksu tablic, ponieważ wiele moich aplikacji wymaga czegoś takiego jak „wyświetl miniaturę”. Więc napisałem coś takiego:

some_vector[0].left=0;
some_vector[0].top =0;<br>

for (int i = 1; i < some_vector.size(); i++)
{

    some_vector[i].left = some_vector[i-1].width +  some_vector[i-1].left;
    if(i % 6 ==0)
    {
        some_vector[i].top = some_vector[i].top.height + some_vector[i].top;
        some_vector[i].left = 0;
    }

}

Obie implementacje są poprawne, ale wolałbym pętlę „for”. Ponieważ zdecydowaliśmy się na użycie Vectora, a nie innego kontenera, najlepszym rozwiązaniem byłoby użycie indeksów. Używanie iteratorów z wektorami straciłoby bardzo korzyść z posiadania obiektów w ciągłych blokach pamięci, które ułatwiają ich dostęp.

Czułem, że żadna z odpowiedzi tutaj nie wyjaśnia, dlaczego lubię iteratory jako ogólną koncepcję nad indeksowaniem do kontenerów. Zauważ, że większość mojego doświadczenia z iteratorami nie pochodzi z C ++, ale z języków programowania wyższego poziomu, takich jak Python.

Interfejs iteratora nakłada mniej wymagań na użytkowników twojej funkcji, co pozwala im robić więcej.

Jeśli wszystko, co potrzebne jest, aby być w stanie przekazać powtórzyć, deweloper nie ogranicza się do korzystania z płytek z węglików pojemniki - mogą używać klasę wykonawczą operator++(T&), operator*(T)i operator!=(const &T, const &T).

#include <iostream>
template <class InputIterator>
void printAll(InputIterator& begin, InputIterator& end)
{
    for (auto current = begin; current != end; ++current) {
        std::cout << *current << "\n";
    }
}

// elsewhere...

printAll(myVector.begin(), myVector.end());

Twój algorytm działa w przypadku, gdy go potrzebujesz - iterując po wektorze - ale może być również przydatny w aplikacjach, których niekoniecznie przewidujesz:

#include <random>

class RandomIterator
{
private:
    std::mt19937 random;
    std::uint_fast32_t current;
    std::uint_fast32_t floor;
    std::uint_fast32_t ceil;

public:
    RandomIterator(
        std::uint_fast32_t floor = 0,
        std::uint_fast32_t ceil = UINT_FAST32_MAX,
        std::uint_fast32_t seed = std::mt19937::default_seed
    ) :
        floor(floor),
        ceil(ceil)
    {
        random.seed(seed);
        ++(*this);
    }

    RandomIterator& operator++()
    {
        current = floor + (random() % (ceil - floor));
    }

    std::uint_fast32_t operator*() const
    {
        return current;
    }

    bool operator!=(const RandomIterator &that) const
    {
        return current != that.current;
    }
};

int main()
{
    // roll a 1d6 until we get a 6 and print the results
    RandomIterator firstRandom(1, 7, std::random_device()());
    RandomIterator secondRandom(6, 7);
    printAll(firstRandom, secondRandom);

    return 0;
}

Próba zaimplementowania operatora w nawiasach kwadratowych, który robi coś podobnego do tego iteratora, byłaby wymyślona, ​​podczas gdy implementacja iteratora jest stosunkowo prosta. Operator nawiasów kwadratowych ma również wpływ na możliwości twojej klasy - które możesz indeksować w dowolnym dowolnym punkcie - co może być trudne lub nieefektywne.

Iteratory nadają się również do dekoracji . Ludzie mogą pisać iteratory, które biorą iterator w swoim konstruktorze i rozszerzają jego funkcjonalność:

template<class InputIterator, typename T>
class FilterIterator
{
private:
    InputIterator internalIterator;

public:
    FilterIterator(const InputIterator &iterator):
        internalIterator(iterator)
    {
    }

    virtual bool condition(T) = 0;

    FilterIterator<InputIterator, T>& operator++()
    {
        do {
            ++(internalIterator);
        } while (!condition(*internalIterator));

        return *this;
    }

    T operator*()
    {
        // Needed for the first result
        if (!condition(*internalIterator))
            ++(*this);
        return *internalIterator;
    }

    virtual bool operator!=(const FilterIterator& that) const
    {
        return internalIterator != that.internalIterator;
    }
};

template <class InputIterator>
class EvenIterator : public FilterIterator<InputIterator, std::uint_fast32_t>
{
public:
    EvenIterator(const InputIterator &internalIterator) :
        FilterIterator<InputIterator, std::uint_fast32_t>(internalIterator)
    {
    }

    bool condition(std::uint_fast32_t n)
    {
        return !(n % 2);
    }
};


int main()
{
    // Rolls a d20 until a 20 is rolled and discards odd rolls
    EvenIterator<RandomIterator> firstRandom(RandomIterator(1, 21, std::random_device()()));
    EvenIterator<RandomIterator> secondRandom(RandomIterator(20, 21));
    printAll(firstRandom, secondRandom);

    return 0;
}

Chociaż te zabawki mogą wydawać się przyziemne, nietrudno wyobrazić sobie używanie iteratorów i dekoratorów iteratorów do robienia potężnych rzeczy za pomocą prostego interfejsu - dekorowanie iteratora wyników bazy danych tylko do przodu za pomocą iteratora, który konstruuje obiekt modelowy z jednego wyniku, na przykład . Wzorce te umożliwiają wydajną pamięć nieskończonej liczby zestawów nieskończonych i, z filtrem takim jak ten, który napisałem powyżej, potencjalnie leniwą ocenę wyników.

Częścią potęgi szablonów C ++ jest interfejs iteratora, gdy zastosowany do takich jak tablice C o stałej długości, rozpada się na prostą i wydajną arytmetykę wskaźników , dzięki czemu jest to naprawdę zero-kosztowa abstrakcja.