Kolekcje standardowe
kolekcje sekwencyjne
Kolekcje asocjacyjne
Zaawansowane programowanie w C++ (PCP)
Wykład 8 - biblioteka standardowa. Kolekcje i iteratory
dr inż. Robert Nowak
27 kwietnia 2007
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe
kolekcje sekwencyjne
Kolekcje asocjacyjne
Powtórzenie - sprytne wskaz
niki
Zalety: upraszczajÄ… zarzÄ…dzanie obiektami na stercie
Wady: narzuty
Sprytne wskaz
niki dostępne w bibliotekach standardowych:

boost::scoped_ptr

std::auto_ptr

boost::shared_ptr

boost::weak_ptr

boost::intrusive_ptr
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe
PrzeglÄ…d
kolekcje sekwencyjne
Wzorzec iteratora
Kolekcje asocjacyjne
Lista kolekcji standardowych
vector jodnowymiarowa tablica
list lista dwukierunkowa
deque kolejka o dwu końcach
queue kolejka
priority_queue kolejka priorytetowa
stack stos
set zbiór
map tablica asocjacyjna (słownik)
multiset zbiór, wartość może występować wielokrotnie
multimap słownik, klucz może występować wielorotnie
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe
PrzeglÄ…d
kolekcje sekwencyjne
Wzorzec iteratora
Kolekcje asocjacyjne
iteratory
Iterator (forward iterator):

dereferencja (dostęp do elementu)

inkrementacja (wskazuje następny element)
iterator
wektor
iterator
lista
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe
PrzeglÄ…d
kolekcje sekwencyjne
Wzorzec iteratora
Kolekcje asocjacyjne
iteratory przykład
vector v;
//operacje na wektorze
vector::const_iterator ii = v.begin();
for(; ii != v.end(); ++ii )
//*ii dostarcza element wskazywany przez iterator
list l;
//operacje na liście
list::const_iterator ii = l.begin();
for(; ii != l.end(); ++ii )
//*ii dostarcza element wskazywany przez iterator
Używaj iteratorów do dostępu do elementów kolekcji
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe wektor
kolekcje sekwencyjne lista dwukierunkowa
Kolekcje asocjacyjne inne kolekcje sekwencyjne
std::vector
Nagłówek:
//Deklaracja
template >
class std::vector;
vector
size
5
capacity
10
ptr
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe wektor
kolekcje sekwencyjne lista dwukierunkowa
Kolekcje asocjacyjne inne kolekcje sekwencyjne
vector - definicje typów
value_type typ elementu
iterator iterator do elementów wektora
const_iterator
reverse_iterator iterator odwrotny
const_reverse_iterator
pointer, const_pointer wskaz
nik do elementu
reference, const_reference referencja do elementu
typedef vector MyVector;//Definicja typu kolekcji
MyVector v;//Przykładowa kolekcja
//utworzenie obiektu iteratora
MyVector::const_iterator ii = v.begin();//ii jest iteratorem
MyVector::value_type val = v[0]; //val ma typ taki jak element
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe wektor
kolekcje sekwencyjne lista dwukierunkowa
Kolekcje asocjacyjne inne kolekcje sekwencyjne
vector - dostęp do elementów
Dostęp do elementu:
reference operator[](size_type n); bez kontroli
const_reference operator[](size_type n) const;
reference at(size_type n); kontrola zakresu
const_reference at(size_type n) const;
reference front(); pierwszy element
const reference front() const;
reference back(); ostatni element
const reference back() const;
Informacje pomocnicze:
size_type size() const; liczba elementów
size_type capacity() const; liczba elementów dla których zaaloko-
wano pamięć
bool empty() const; bada czy size() == 0
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe wektor
kolekcje sekwencyjne lista dwukierunkowa
Kolekcje asocjacyjne inne kolekcje sekwencyjne
vector - konstruktory
vector(); pusty kontener
vector(size_type n, const T& val = T()); n kopii val
template vector(In first, In last); kopiuje zakres
vector(const vector& v); konstruktor kopiujÄ…cy
vector& operator=(const vector& v);
Przykłady:
const int TAB[] = { 3, 2, 0, 8 };
const int TAB_SIZE = sizeof(TAB)/sizeof(TAB[0]);
//kopiowanie zakresu
vector v(TAB, TAB + TAB_SIZE);
//Wypełnia stałą
vector v2(TAB_SIZE, 0);
vector v3 = v1;//Konstruktor kopiujÄ…cy
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe wektor
kolekcje sekwencyjne lista dwukierunkowa
Kolekcje asocjacyjne inne kolekcje sekwencyjne
vector - przeglądanie kolejnych elementów
iterator begin(); iterator do pierwszego elementu
iterator end(); iter. do pierwszego za ostatnim
reverse_iterator rbegin(); iteratory dla odwrotnej kolejności
reverse_iterator rend();
begin
end
A B C D
rbegin
rend
D C B A
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe wektor
kolekcje sekwencyjne lista dwukierunkowa
Kolekcje asocjacyjne inne kolekcje sekwencyjne
vector - dodawanie i usuwanie elementów
void push_back(const T&); wstawia na koniec
void pop_back(); usuwa ostatni
iterator insert(iterator pos, const T& t); wstawia przed
iterator erase(iterator pos); usuwa
template wstawia zakres
void insert(iterator pos, In first, In last);
iterator erase(iterator first, iterator last); usuwa
void clear(); usuwa wszystkie
Inne funkcje:

void vector::swap(vector& v);

bool operator==(const vector&, const vector&);

bool operator<(const vector&, const vector&);
Specjalizacje: vector
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe wektor
kolekcje sekwencyjne lista dwukierunkowa
Kolekcje asocjacyjne inne kolekcje sekwencyjne
std::list
Nagłówek:
//Deklaracja
template >
class std::vector;
list
head
tail
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe wektor
kolekcje sekwencyjne lista dwukierunkowa
Kolekcje asocjacyjne inne kolekcje sekwencyjne
operacje dla listy dwukierunkowej
dostarcza operacji takich jak vector za wyjÄ…tkiem:

dostępu swobodnego do elementów

operatora indeksowania (operator[])

metody at()

rezerwacji pamięci ( capacity(), reserve() )
Dodatkowe operacje:

operacje na poczÄ…tku listy:

reference front();

const_reference front() const;

void push_front(const T&);

void pop_front();

inne operacje:

void remove(const T& val); //usuwa el. równe val

void reverse(); //odwraca porządek elementów

splice, merge, sort
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe wektor
kolekcje sekwencyjne lista dwukierunkowa
Kolekcje asocjacyjne inne kolekcje sekwencyjne
std::deque - kolejka o dwu końcach
Nagłówek
deque
start
end
Operacje:

takie jak dla wektora (za wyjÄ…tkiem capacity(), reserve() )

operacje z przodu ciÄ…gu (tak jak dla listy)
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
empty
empty
empty
Kolekcje standardowe wektor
kolekcje sekwencyjne lista dwukierunkowa
Kolekcje asocjacyjne inne kolekcje sekwencyjne
Porównanie kolekcji sekwencyjnych
indeksowanie insert, erase poczÄ…tek koniec
tablica O(1) - - -
vector O(1) O(n)+ - O(1)+
list - O(1) O(1) O(1)
deque O(1) O(n) O(1) O(1)

tablica - struktura odziedziczona po  C

wektor - optymalizacja przy dostępie przez indeks,
rezerwowanie pamięci.
- optymalne wstawianie i usuwanie elementów.
lista
- optymalne operacje na końcach, indeksowanie prawie
deque
tak optymalne jak w wektorze.
dr inż. Robert Nowak Zaawansowane programowanie w C++ (PCP)
Kolekcje standardowe słownik
kolekcje sekwencyjne inne kontenery asocjacyjne
Kolekcje asocjacyjne porówanie kolekcji sekwencyjnych i asocjacyjnych
słownik
Nagłówek: