Jak wykonać iterację wstecz za pośrednictwem listy STL?

Question

Piszę kod między platformami między Windows i Mac.

Jeśli list :: end() "zwraca iterator, który adresuje lokalizację po ostatnim elemencie na liście" i może być sprawdzany podczas przewijania listy do przodu, jaki jest najlepszy sposób przechodzenia wstecz?

Ten kod workson Mac, ale nie na systemie Windows (nie może zmniejszyć się poza pierwszym elemencie):

list<DVFGfxObj*>::iterator iter = m_Objs.end(); 
for (iter--; iter!=m_Objs.end(); iter--)// By accident discovered that the iterator is circular ? 
{ 
} 

to działa w systemie Windows:

list<DVFGfxObj*>::iterator iter = m_Objs.end(); 
    do{ 
     iter--; 
    } while (*iter != *m_Objs.begin()); 

Czy istnieje inny sposób na przechodzenie do tyłu, że może być zaimplementowany w pętli for?

Answer 1

Użyj reverse_iterator zamiast iteratora. Użyj funkcji rbegin() & rend() zamiast begin() & end().

Inną możliwością, jeśli chcesz użyć makra BOOST_FOREACH, jest użycie makra BOOST_REVERSE_FOREACH wprowadzonego w kroku Boost 1.36.0.

Answer 2

Prawdopodobnie potrzebujesz odwrotnych iteratorów. Z pamięci:

list<DVFGfxObj*>::reverse_iterator iter = m_Objs.rbegin(); 
for(; iter != m_Objs.rend(); ++iter) 
{ 
} 

Answer 3

Jak już wspomniano przez Ferruccio, stosowanie reverse_iterator:

for (std::list<int>::reverse_iterator i = s.rbegin(); i != s.rend(); ++i) 

Answer 4

To powinno działać:

list<DVFGfxObj*>::reverse_iterator iter = m_Objs.rbegin(); 
for (; iter!= m_Objs.rend(); iter++) 
{ 
} 

Answer 5

najlepszy/Najprostszym sposobem, aby odwrócić iteracyjne lista jest (jak już wspomniano) do używania odwrotnych iteratorów rbegin/rend.

Jednakże, chciałbym wspomnieć, że implementowane są odwrócone iteratory przechowujące "bieżącą" pozycję iteratora jeden po drugim (przynajmniej w wersji GNU standardowej biblioteki).

Ma to na celu uproszczenie wdrażania, w celu zakresie w odwrotnej kolejności, aby mieć takie same semantykę jako zakres przodu [początek, koniec) i [rbegin, rozdzierać)

Oznacza to, że dereferencing iteracyjnej polega na tworzeniu nowej tymczasowe, a następnie zmniejszanie go każdym razem:

reference 
    operator*() const 
    { 
_Iterator __tmp = current; 
return *--__tmp; 
    } 

Zatem dereferencing reverse_iterator jest mniejsza niż normalny iteracyjnej.

Można jednak zamiast korzystać ze zwykłych iteratorów dwukierunkowych symulować odwrócić iteracja siebie, unikając tego narzutu:

for (iterator current = end() ; current != begin() ; /* Do nothing */) 
{ 
    --current; // Unfortunately, you now need this here 
    /* Do work */ 
    cout << *current << endl; 
} 

Testy wykazały to rozwiązanie będzie ~ 5 razy szybciej dla każdego dereference stosowanego w Ciało pętli.

Uwaga: Testowanie nie zostało wykonane przy użyciu powyższego kodu, ponieważ std :: cout stanowiłoby wąskie gardło.

Uwaga: różnica czasu "zegara ściennego" wynosiła ~ 5 sekund, a rozmiar std :: list wynosił 10 milionów elementów. Realistycznie, o ile rozmiar danych nie jest tak duży, po prostu trzymaj się rbegin() rend()!