Wprowadzenie.
Lista “List” to kontener sekwencyjny. Kontener ten charakteryzuje się stałym czasem wstawiania lub usuwania elementu z obu kierunków.
Kontener ten zaimplementowany jest jako lista dwukierunkowa. Każdy element listy zawiera wskaźnik na następny i poprzedni obiekt elementu listy, dzięki czemu kolejne elementy nie są powiązane ze sobą miejscem alokacji.
Zakres artykułu.
- Właściwości kontenera
- Program w C++
- Plik Makefile
- Testy
Właściwości kontenera
- Implementacja kontenera list jest podobna do kontenera forward list. Różnica między nimi polega na tym, że kontener forward list posiada wskaźnik tylko do następnego elementu kontenera przez co iteracja może odbywać się jedynie w przód;
- 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 listy może zwiększyć efektywność programu;
- Bezpośredni dostęp do elementów listy jest niemożliwy. W celu dostania się do konkretnego elementu należy przeiterować kontener określoną ilość razy.
Program w C++
Kod programu, który pozwoli na przetestowanie kontenera “List” zapisałem w pliku main.c i wygląda następująco.
#include <iostream> #include <list> #define ROZMIAR_KOLEKCJI 5 using namespace std; int main() { int i = 0; list<int> mojaKolekcja; int liczbaElementow = 0; // Wstawianie elementów for(i=0; i<ROZMIAR_KOLEKCJI; i++) { mojaKolekcja.push_back(i); } for(i=10; i>=ROZMIAR_KOLEKCJI; i--) { mojaKolekcja.push_front(i); } liczbaElementow = mojaKolekcja.size(); // Wyświetlenie kolekcji for(list<int>::iterator element = mojaKolekcja.begin(); element != mojaKolekcja.end(); element++) { cout << *element << endl; } }
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:
5
6
7
8
9
10
0
1
2
3
4