Utrzymywanie pozycji bieżącego elementu wektora i listy

Załóżmy, że jest program z dwiema procedurami, gdzie jedna dopisuje elementy do listy, a druga wyświetla te elementy bez usuwania z listy i jest utrzymywany iterator, żeby za każdym razem nie przechodzić listy od początku. Wykorzystując wektor sprawa jest prosta:

#include <iostream>
#include <vector>

using namespace std;

int BufI;
vector<int> Buf;

void Dopisz(int X)
{
	Buf.push_back(X);
	if (Buf.size() == 1)
	{
		cout << "Inicjalizacja iteratora" << endl;
		BufI = 0;
	}
}

void Wyswietl()
{
	while (BufI < Buf.size())
	{
		cout << Buf[BufI] << endl;
		BufI++;
	}
}

int main()
{
	Dopisz(1);
	Dopisz(2);
	Dopisz(3);
	Wyswietl();
	Dopisz(4);
	Dopisz(5);
	Wyswietl();
	return 0;
}

Program wyświetla liczby od 1 do 5 prawidłowo. Teraz identyczny program, w którym zamiast wektora wykorzystuję listę

#include <iostream>
#include <list>

using namespace std;

list<int>::iterator BufI;
list<int> Buf;

void Dopisz(int X)
{
	Buf.push_back(X);
	if (Buf.size() == 1)
	{
		cout << "Inicjalizacja iteratora" << endl;
		BufI = Buf.begin();
	}
}

void Wyswietl()
{
	while (BufI != Buf.end())
	{
		cout << *BufI << endl;
		BufI++;
	}
}

int main()
{
	Dopisz(1);
	Dopisz(2);
	Dopisz(3);
	Wyswietl();
	Dopisz(4);
	Dopisz(5);
	Wyswietl();
	return 0;
}

Ten program działa do pierwszego wyświetlenia. Zauważyłem, że jak jest spełniony warunek "BufI == Buf.end()", to po dopisaniu kolejnych elementów, warunek "BufI == Buf.end()" nadal jest spełniony.

Ten program działa poprawnie, czyli w wyświetla liczby od 1 do 5, ale wracanie na początek i odliczanie wyświetlonych elementów przy każdym wywołaniu wyświetlania nie jest rozsądnym podejściem.

#include <iostream>
#include <list>

using namespace std;

int BufI;
list<int> Buf;

void Dopisz(int X)
{
	Buf.push_back(X);
	if (Buf.size() == 1)
	{
		cout << "Inicjalizacja iteratora" << endl;
		BufI = 0;
	}
}

void Wyswietl()
{
	list<int>::iterator BufI_;
	BufI_ = Buf.begin();
	advance(BufI_, BufI);
	while (BufI_ != Buf.end())
	{
		cout << *BufI_ << endl;
		BufI_++;
		BufI++;
	}
}

int main()
{
	Dopisz(1);
	Dopisz(2);
	Dopisz(3);
	Wyswietl();
	Dopisz(4);
	Dopisz(5);
	Wyswietl();
	return 0;
}

Jak zrealizować powyższy program wykorzystując listę i bez odliczania wszystkich elementów przy każdym wyświetleniu?
Na wyjściu powinien pokazać się taki tekst:

Inicjalizacja iteratora
1
2
3
4
5

Zakładam, że to program testowy w celu nauki. W przeciwnym razie nie używaj list, chyba że masz żelazne dowody na taką konieczność, nie używaj zmiennych globalnych, nie łam SRP i pewnie coś jeszcze.

Dodatkowo - dla wektora używasz indeksu, nie iteratora.

W każdym razie, w przypadku ogólnym możesz zamienić kolejnością definicję kontenera i jego iteratora, przypisując mu niewłaściwą-końcową wartość:

list<int> Buf;
auto it = Buf.end();

W funkcji dodającej sprawdź czy jesteś na końcu:

void Dopisz(int X)
{
    Buf.push_back(X);
    if (it == Buf.end())
    {
        cout << "Inicjalizacja iteratora" << endl;
        it = prev(Buf.end());
    }
}

To powinno działać dla wszystkich std::list

kq napisał(a):

Zakładam, że to program testowy w celu nauki. W przeciwnym razie nie używaj list, chyba że masz żelazne dowody na taką konieczność, nie używaj zmiennych globalnych, nie łam SRP i pewnie coś jeszcze.

To jest rzeczywiście program testowy napisany specjalnie po to, żeby zilustrować problem. Stosowanie "dobrych praktyk" uznałem za nie istotne, ważne było tylko to, żeby kod kompilował się i działał w Ideone.

Jeśli chodzi o strukturę w programie docelowym (ten, który rzeczywiście robię i potrzebuję), są następujące założenia:

1. Dostęp sekwencyjny z możliwością zapamiętania aktualnej pozycji, na której stoję poza pętlą przeglądającą, nie potrzeba dostępu losowego
2. Jak najmniejszy narzut przy dodawaniu elementu na końcu struktury
3. W danej chwili ilość elementów może być bardzo różna, od kilku do co najmniej kilku tysięcy, trudno zakładać początkową wielkość
   Program testowy ilustruje przewidywane czynności na tej strukturze. Wydaje mi się się, że rozważając lista vs wektor, to lista lepiej pasuje do powyższych założeń. Wektor ma to do siebie, że jak jest duży i się dodaje kolejne elementy, to on cały się przealokowuje i program musi znaleźć dla niego ciągły fragment pamięci, dla listy tego problemu nie ma. Nie zmienia to faktu, że można na próbę posłużyć się wektorem i sprawdzić, czy w praktyce to jest problem. Czy według Ciebie lepszy w tym przypadku będzie wektor, czy lista? Czy coś jeszcze innego? Wydaje mi się, że w C++ struktury "stack" i "queue" to tylko obudowana lista lub wektor z procedurami zapewniającymi wprowadzanie i pobieranie elementów z odpowiedniej strony struktury.

kq napisał(a):

Dodatkowo - dla wektora używasz indeksu, nie iteratora.

W przedstawionym przeze mnie kodzie w wersji wykorzystującej wektor rzeczywiście wykorzystuję indeks, co nie zmienia faktu, że do wektora można użyć iteratora w identyczny sposób, jak do listy.

kq napisał(a):

W każdym razie, w przypadku ogólnym możesz zamienić kolejnością definicję kontenera i jego iteratora, przypisując mu niewłaściwą-końcową wartość:

list<int> Buf;
auto it = Buf.end();

W funkcji dodającej sprawdź czy jesteś na końcu:

void Dopisz(int X)
{
    Buf.push_back(X);
    if (it == Buf.end())
    {
        cout << "Inicjalizacja iteratora" << endl;
        it = prev(Buf.end());
    }
}

To powinno działać dla wszystkich std::list

Teraz przechodzimy do sedna sprawy. Wypróbowałem te modyfikacje i program zadziałał tak, jak potrzebuję. Natomiast ja nadal nie rozumiem, jak to jest z tymi iteratorami. Wyobrażam sobie, że układam pudełka od zapałek obok siebie wzdłuż krawędzi stołu. Wykonanie "begin", to jest położenie palca wskazującego prawej reki przy pierwszym pudełku. Wykonanie "end", to jest położenie palca wskazującego prawej reki w miejscu za ostatnim pudełkiem. Palec mogę przesuwać o jedno pudełko w prawo lub w lewo. Jeżeli położę palec za ostatnim pudełkiem, a potem lewą ręką dołożę jedno pudełko na koniec szeregu (odpowiednik "push_back") bez ruszania prawej ręki, to palec prawej reki będzie pokazywać nowo dołożone pudełko i dopiero po przesunięciu o jedno miejsce w prawo będzie za tym pudełkiem. W wersji, gdzie używam wektora i indeksu działa to bardzo dobrze, w zmiennej "BufI" zapamiętuję położenie palca w odniesieniu do położenia pierwszego pudełka i program działa zgodnie z tym wyobrażeniem.

Na jakiej podstawie, przy iteratorze wskazującym miejsce za ostatnim elementem, po dodaniu elementu, iterator nadal wskazuje miejsce za ostatnim elementem tak, jakby iterator przesuwał się za każdym razem, gdy dodaję nowy element, jakby punktem odniesienia iteratora był koniec struktury? Czyli tak naprawdę punktem odniesienia iteratora jest początek, czy koniec struktury?

Jak duże będą te elementy? Tak czy inaczej, benchmarkuj koniecznie. Inaczej nie używaj std::list.

Jeśli chodzi o iteratory, to traktuj je jak wskaźniki, które wiedzą jak wykonać inkrementację/dekrementację dla swojego kontenera. W rzeczy samej, std::vector<T>::iterator może być zdefiniowany jako T*, i tak jest w przypadku niektórych bibliotek standardowych. W tym momencie, od kontenera zależy, czy wskaźniki-iteratory po modyfikacji kontenera zachowują swoją wartość, a jak tak to które.

kq napisał(a):

Jak duże będą te elementy? Tak czy inaczej, benchmarkuj koniecznie. Inaczej nie używaj std::list.

Docelowo to mają być liczby całkowite (int). Można przyjąć założenie, że nie nigdy nie przekroczy się 10 tys do 1mln elementów, a przy dopisywaniu kolejnych elementów najstarsze będą usuwane. Czy może lepiej tu zastosować wektor lub tablicę i dwie zmienne liczbowe pracujące jako bufor cykliczny? Wiem, że dopisywanie elementów może realokować wektor. Czy usuwanie i czyszczenie też może realokować wektor redukując wielkość w pamięci? W takim razie wypróbuję z buforem cyklicznym. Czy C++11 lub nowszy ma standardowo tak bufor, czy muszę utworzyć go samemu poprzez napisanie klasy?

kq napisał(a):

Jeśli chodzi o iteratory, to traktuj je jak wskaźniki, które wiedzą jak wykonać inkrementację/dekrementację dla swojego kontenera. W rzeczy samej, std::vector<T>::iterator może być zdefiniowany jako T*, i tak jest w przypadku niektórych bibliotek standardowych. W tym momencie, od kontenera zależy, czy wskaźniki-iteratory po modyfikacji kontenera zachowują swoją wartość, a jak tak to które.

Czy to znaczy, że jak są zdefiniowane i zapamiętane iteratory, to w ogólnym przypadku po jakiejkolwiek zmianie zawartości kontenera te iteratory mogą przestać być użyteczne i zawsze trzeba pokazać im początek lub koniec kontenera i ewentualnie przejść odpowiednią liczbę kroków w zależności od potrzeb?

Boost ma bufor cykliczny. Biblioteka standardowa nie ma.

Co do iteratorów - mniej więcej, ale właśnie różne kontenery dają różne gwarancje. map/set i wariacje nigdy nie inwalidują iteratorów (pomijając kasowanie elementów). deque nigdy tego nie robi przy push_front/push_back (poza odpowiednio begin() i end()). vector przy push_back zmienia tylko end(), chyba, że zaszła realokacja. list nigdy nie inwaliduje (znów pomijając kasowanie).