Wprowadzenie.
Lista w przód “Forward list” to kontener sekwencyjny. Kontener ten charakteryzuje się stałym czasem wstawiania oraz usuwania elementów niezależnie od ich położenia.
Zakres artykułu.
- Właściwości kontenera
- Program w C++
- Plik Makefile
- Testy
Właściwości kontenera
- Kolejne elementy nie są przechowane w pamięci obok siebie, przez co dostęp do określonego elementu uzyskuje się poprzez przeiterowanie listy od pierwszego elementu;
- Każdy element kontenera posiada informację o lokalizacji następnego elementu.
- Operacje wstawiania, wydobywania i przenoszenia są szybsze niż w przypadku kontenerów: array, vector i deque. Zaleta ta sugeruje, że w przypadku algorytmów sortujących zastosowanie kontenera forward list może zwiększyć efektywność programu;
- Brak możliwości uzyskania bezpośrednio dostępu do każdego elementu.
Program w C++
Kod programu, który pozwoli na przetestowanie kontenera “Forward list” zapisałem w pliku main.c i wygląda następująco.
#include <iostream> #include <forward_list> #define ROZMIAR_KOLEKCJI 10 using namespace std; int main() { int i = 0; forward_list<int> mojaKolekcja; // Wstawianie elementów for(i=5; i<ROZMIAR_KOLEKCJI; i++) { mojaKolekcja.push_front(i); } // Wyswietlenie kolekcji for(forward_list<int>::iterator element = mojaKolekcja.begin(); element != mojaKolekcja.end(); element++) { cout << *element << endl; } return 0; }
Plik Makefile
Plik Makefile wygląda następująco:
CC = g++
CFLAGS =
LIBS =
OBJ =\
main.o
all: main
clean:
rm -f *.o test
.c.o:
$(CC) -c $(INCLUDES) $(CFLAGS) $<
main: $(OBJ)
$(CC) $(OBJ) $(LIBS) -o test
Testy
Gdy już mamy wszystko przygotowane wówczas w konsoli wpisujemy polecenie:
$ make
Następnie uruchamiamy nasz program poleceniem:
$ ./test
Wynik jaki otrzymamy powinien wyglądać następująco:
9
8
7
6
5