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