Kolekcje, algorytmy
Biblioteka STL
Sebastian Deorowicz
Politechnika ÅšlÄ…ska
2006 10 23
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 1 / 84
Plan wykładu
1
Kolekcje sekwencyjne
Kolekcja deque
Adaptatory kolekcji
Adaptator kolekcji queue
Adaptator kolekcji stack
Adaptator kolekcji priority queue
2
Kolekcje asocjacyjne
Klasa pair
Kolekcja set
Kolekcja multiset
Kolekcja bitset
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 2 / 84
Plan wykładu
1
Kolekcje sekwencyjne
Kolekcja deque
Adaptatory kolekcji
Adaptator kolekcji queue
Adaptator kolekcji stack
Adaptator kolekcji priority queue
2
Kolekcje asocjacyjne
Klasa pair
Kolekcja set
Kolekcja multiset
Kolekcja bitset
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 3 / 84
Kolekcja deque
Czym jest kolekcja deque?1
Kolekcja sekwencyjna
Podobna do kolekcji vector w tym, że wspiera bezpośredni dostęp do elementów
a czas wstawiania i usuwania elementów ze środka jest liniowy
Podobna do kolekcji list w tym, że czas wstawiania i usuwania elementów z początku
i końca jest stały
1
Dostępna w pliku nagłówkowym deque
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 4 / 84
Kolekcja deque
Konstruktory
Analogiczne jak w list i vector
Przypisania
Metody assign analogiczne jak w list i vector
Operator przypisania również analogiczny
Metody zwracajÄ…ce iteratory
Dostępne metody begin, end, rbegin, rend zwracające iteratory o takim samym
znaczeniu jak w innych kolekcjach sekwencyjnych
Metody zwiÄ…zane z rozmiarem
Dostępne metody size, max size, resize, empty o takim samym znaczeniu jak
w innych kolekcjach sekwencyjnych
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 5 / 84
Kolekcja deque  dostęp swobodny do elementów
reference operator[](size_type n)
const_reference operator[](size_type n) const
Działanie: Zwraca referencję (stałą referencję) do n-tego elementu kolekcji
Parametr:
n  numer elementu
Zwracana wartość: Referencja (stała referencja) do elementu
Złożoność: O(1)
Uwaga: Brak kontroli zakresu, więc możliwe zachowanie niezdefiniowane jeśli podany
błędny indeks
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 6 / 84
Kolekcja deque  dostęp swobodny do elementów
reference at(size_type n)
const_reference at(size_type n) const
Działanie: Zwraca referencję (stałą referencję) do n-tego elementu kolekcji
Parametr:
n  numer elementu
Zwracana wartość: Referencja (stała referencja) do elementu
Złożoność: O(1)
Uwaga: Kontrola zakresu, więc jeśli podany błędny indeks to generuje wyjątek
out_of_range
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 7 / 84
Kolekcja deque  dostęp swobodny do elementów
reference front()
const_reference front() const
reference back()
const_reference back() const
Działanie: Zwraca referencję (stałą referencję) do pierwszego (ostatniego) elementu
kolekcji
Parametry: brak
Zwracana wartość: Referencja (stała referencja) do elementu kolekcji
Złożoność: O(1)
Uwaga: Brak kontroli zakresu, więc jeśli kolekcja pusta to zachowanie
niezdefiniowane
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 8 / 84
Kolekcja deque  operacje na końcach
void push_front(const T& x)
void push_back(const T& x)
Działanie: Dodaje element na początek (koniec) kolekcji
Parametr:
x  wstawiany element
Zwracana wartość: brak
Złożoność: O(1)
void pop_front()
void pop_back()
Działanie: Usuwa element z początku (końca) kolekcji
Parametry: brak
Zwracana wartość: brak
Złożoność: O(1)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 9 / 84
Kolekcja deque  wstawianie i usuwanie elementów
Wstawianie elementów
Dostępne 3 metody insert o identycznych parametrach i działaniu jak dla
kolekcji vector i list
Złożoność: O(n), gdzie n to rozmiar kolekcji
Usuwanie elementów
Dostępne 2 metody erase o identycznych parametrach i działaniu jak dla
kolekcji vector i list
Złożoność: O(n), gdzie n to rozmiar kolekcji
Inne
Metoda clear identyczna jak dla innych kolekcji (złożoność O(n))
Metoda swap identyczna jak dla innych kolekcji (złożoność O(1))
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 10 / 84
Kolekcja deque  wstawianie i usuwanie elementów
Wstawianie elementów
Dostępne 3 metody insert o identycznych parametrach i działaniu jak dla
kolekcji vector i list
Złożoność: O(n), gdzie n to rozmiar kolekcji
Usuwanie elementów
Dostępne 2 metody erase o identycznych parametrach i działaniu jak dla
kolekcji vector i list
Złożoność: O(n), gdzie n to rozmiar kolekcji
Inne
Metoda clear identyczna jak dla innych kolekcji (złożoność O(n))
Metoda swap identyczna jak dla innych kolekcji (złożoność O(1))
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 10 / 84
Kolekcja deque  wstawianie i usuwanie elementów
Wstawianie elementów
Dostępne 3 metody insert o identycznych parametrach i działaniu jak dla
kolekcji vector i list
Złożoność: O(n), gdzie n to rozmiar kolekcji
Usuwanie elementów
Dostępne 2 metody erase o identycznych parametrach i działaniu jak dla
kolekcji vector i list
Złożoność: O(n), gdzie n to rozmiar kolekcji
Inne
Metoda clear identyczna jak dla innych kolekcji (złożoność O(n))
Metoda swap identyczna jak dla innych kolekcji (złożoność O(1))
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 10 / 84
Kolekcja deque  przykład
Przykład
#include
using namespace std;
const int MAX = 10;
int main(int argc, char* argv[])
{
int tab[MAX] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
deque di(tab, tab+5);
ShowCollection(di); // 1 2 3 4 5
di.insert(di.begin()+3, tab+7, tab+10);
ShowCollection(di); // 1 2 3 8 9 10 4 5
di.pop_front();
ShowCollection(di); // 2 3 8 9 10 4 5
di.push_front(12);
ShowCollection(di); // 12 2 3 8 9 10 4 5
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 11 / 84
Adaptatory kolekcji
Kolekcje sekwencyjne
Kolekcje vector, list, deque częściowo mogą być używane zamiennie ale zawsze
pewnym kosztem
Nie można żadnej z nich zbudować w oparciu o inną bez utraty wydajności
Adaptatory
Często przydają się także inne kolekcje sekwencyjne
Ponieważ można je oprzeć na jednej z tych 3 podstawowych, to nie są one
implementowane osobno, a jako adaptacje jednej z kolekcji podstawowych
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 12 / 84
Adaptator queue
Składnia2
template class Collection = deque >
class queue {
...
};
Opis
Implementuje kolejkÄ™ FIFO
Nie udostępnia operacji  nie kolejkowych
Kolekcja domyślnie oparta o deque ale można użyć dowolnej kolekcji dostarczającej
metod front, back, push back, pop front (czyli nie vector)
2
Dostępna w pliku nagłówkowym queue
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 13 / 84
Adaptator queue  konstruktor
queue(const Collection& = Collection())
Działanie: Tworzy pustą kolejkę (jeśli brak parametru) lub kolejkę zainicjalizowaną
zawartością przekazanej kolekcji
Parametr:
Kolekcja inicjalizujÄ…ca kolejkÄ™
Zwracana wartość: brak
Złożoność: Stała jeśli nie ma parametru bądz
liniowa jeśli jest parametr
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 14 / 84
Adaptator queue  operacje kolejkowe
Implementacja
bool empty() const {return c.empty();}
size_type size() const {return c.size();}
reference front() {return c.front();}
const_reference front() const {return c.front();}
reference back() {return c.back();}
const_reference back() const {return c.back();}
void push(const value_type & x) {c.push_back(x);}
void pop() {c.pop_front();}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 15 / 84
Adaptator queue  inne operacje
Inne operacje
Dostępne operatory porównywania kolekcji działające identycznie jak dla kolekcji,
na której jest oparta kolejka
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 16 / 84
Adaptator queue  przykład
Przykład
#include
#include
#include
using namespace std;
const int MAX = 10;
template void ShowQueue(Queue q) {
for(; !q.empty(); q.pop())
std::cout << q.front() << " ";
std::cout << std::endl;
}
int main(int argc, char* argv[])
{
int tab[MAX] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
deque di(tab, tab+10);
queue qdi(di);
// ShowCollection(qdi); // BÅ‚Ä…d kompilacji: brak metod begin() i end()
ShowQueue(qdi); // 1 2 3 4 5 6 7 8 9 10
// BÅ‚Ä…d kompilacji: vector nie ma metody pop!
// queue > qvi(vector(tab, tab+10));
// ShowQueue(qvi);
list li(tab, tab+10);
li.reverse();
queue > qli(li);
ShowQueue(qli); // 10 9 8 7 6 5 4 3 2 1
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 17 / 84
Adaptator stack
Składnia3
template class Collection = deque >
class stack {
...
};
Opis
Implementuje stos
Nie udostępnia operacji  nie stosowych
Kolekcja domyślnie oparta o deque ale można użyć dowolnej kolekcji dostarczającej
metod back, push back, pop back (czyli np. vector, list, deque)
3
Dostępna w pliku nagłówkowym stack
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 18 / 84
Adaptator stack  konstruktor
stack(const Collection& = Collection())
Działanie: Tworzy pusty stos (jeśli brak parametru) lub stos zainicjalizowany
zawartością przekazanej kolekcji
Parametr:
Kolekcja inicjalizujÄ…ca stos
Zwracana wartość: brak
Złożoność: Stała jeśli nie ma parametru bądz
liniowa jeśli jest parametr
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 19 / 84
Adaptator stack  operacje stosowe
Implementacja
bool empty() const {return c.empty();}
size_type size() const {return c.size();}
reference top() {return c.back();}
const_reference top() const {return c.back();}
void push(const value_type& x) {c.push_back(x);}
void pop() {c.pop_back();}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 20 / 84
Adaptator stack  inne operacje
Inne operacje
Dostępne operatory porównywania stosów działające identycznie jak dla kolekcji,
na której jest oparta kolejka
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 21 / 84
Adaptator stack  przykład
Przykład
#include
#include
#include
using namespace std;
const int MAX = 10;
template void ShowStack(Stack q) {
for(; !q.empty(); q.pop())
std::cout << q.top() << " ";
std::cout << std::endl;
}
int main(int argc, char* argv[])
{
int tab[MAX] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector vi(tab, tab+10);
stack > svi(vi);
ShowStack(svi); // 10 9 8 7 6 5 4 3 2 1
deque di(tab, tab+10);
stack sdi(di);
ShowStack(sdi); // 10 9 8 7 6 5 4 3 2 1
sdi.push(10);
ShowStack(sdi); // 10 10 9 8 7 6 5 4 3 2 1
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 22 / 84
Adaptator priority queue
Składnia4
template class Collection = vector,
class Compare = less >
class priority_queue {
...
};
Opis
Implementuje kolejkę priorytetową, czyli taką kolejkę, w której elementy są
umieszczane według priorytetu
Nie udostępnia operacji  nie kolejkowych ani operatorów porównania kolekcji
Kolekcja domyślnie oparta o vector ale można użyć dowolnej kolekcji dostarczającej
metod front, push back, pop back oraz iteratorów dostępu swobodnego (czyli np.
vector, deque, ale nie list)
Ostatni parametr wzorca określa kryterium porównywania dla ustalenia priorytetu 
domyślnie przy użyciu operatora <
Wewnętrznie implementowana za pomocą kopca
4
Dostępna w pliku nagłówkowym queue
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 23 / 84
Adaptator priority queue  konstruktory
priority_queue(const Compare& comp = Compare(),
const Collection& = Collection())
Działanie: Tworzy pustą kolejkę priorytetową i inicjalizuje ją (jeśli jest parametr)
zawartością kolekcji przekazanej jako drugi parametr
Parametry:
pierwszy  określa kryterium sortowania
drugi  zawiera dane do inicjalizacji kolekcji
Zwracana wartość: brak
Złożoność: Stała jeśli nie ma parametru bądz
O(n) jeśli jest parametr
Uwaga: Po inicjalizacji kolejki wywoływana jest funkcja STL:
make_heap(c.begin(), c.end(), comp)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 24 / 84
Adaptator priority queue  konstruktory
priority_queue(InputIterator first, InputIterator last,
const Compare& comp = Compare(),
const Collection& y = Collection())
Działanie: Tworzy pustą kolejkę priorytetową i inicjalizuje ją zawartością określoną
przekazanymi iteratorami: [first,last)
Parametry:
first, last  iteratory specyfikujące zakres kolekcji używanej do inicjalizacji
kolejki priorytetowej
trzeci  określa kryterium sortowania
czwarty  zawiera dane do inicjalizacji kolekcji
Zwracana wartość: brak
Złożoność: O(n)
Uwaga: Po inicjalizacji kolejki wywoływana jest funkcja STL:
make_heap(c.begin(), c.end(), comp)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 25 / 84
Adaptator priority queue  operacje kolejkowe
Implementacja
bool empty() const {return c.empty();}
size_type size() const {return c.size();}
const_reference top() const {return c.front();}
void push(const value_type& x);
void pop();
Złożoność
empty, size, top  w zależności od złożoności tych operacji dla kolekcji, na której
jest oparta kolejka priorytetowa; dla wektora będzie to O(1)
push, pop  O(log n)
Uwaga
Zachowanie metod top i pop dla pustej kolejki jest niezdefiniowane
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 26 / 84
Adaptator priority queue  przykład
Przykład
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 10;
template void ShowPQ(PQ &pq) {
for(; !pq.empty(); pq.pop())
cout << pq.top() << " ";
cout << endl;
}
int main(int argc, char* argv[]) {
int tab[MAX] = {5, 6, 8, 1, 2, 3, 4, 10, 7, 9};
vector vi(tab, tab+10);
priority_queue, less > pqvi1(less(), vi);
ShowPQ(pqvi1); // 10 9 8 7 6 5 4 3 2 1
priority_queue > pqvi2(tab, tab+10);
ShowPQ(pqvi2); // 10 9 8 7 6 5 4 3 2 1
priority_queue, greater > pqdi1(greater(), deque(tab, tab+10));
ShowPQ(pqdi1); // 1 2 3 4 5 6 7 8 9 10
priority_queue > pqs;
pqs.push("Ola"); pqs.push("Jola"); pqs.push("Iza");
ShowPQ(pqs); // Ola Jola Iza
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 27 / 84
Plan wykładu
1
Kolekcje sekwencyjne
Kolekcja deque
Adaptatory kolekcji
Adaptator kolekcji queue
Adaptator kolekcji stack
Adaptator kolekcji priority queue
2
Kolekcje asocjacyjne
Klasa pair
Kolekcja set
Kolekcja multiset
Kolekcja bitset
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 28 / 84
Klasa pair
Opis5
Grupuje dwie wartości różnych typów w ramach jednej struktury
Jest wykorzystywana w kolekcjach i algorytmach STL
Definicja
template
struct pair {
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair();
pair(const T1& x, const T2& y);
template pair(const pair &p);
};
5
Klasa zdefiniowana w pliku utility
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 29 / 84
Klasa pair  konstruktory
pair()
Działanie: Inicjalizuje parę domyślnymi wartościami typów składowych
pair(const T1& x, const T2& y)
Działanie: Inicjalizuje parę wartościami x i y
template pair(const pair &p)
Działanie: Inicjalizuje parę wartością pary p
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 30 / 84
Klasa pair  operator porównania
bool operator==(const pair& x, const pair& y)
Działanie: Porównuje dwie pary za pomocą operatorów == wywoływanych dla
pierwszych i drugich składowych
Parametry:
x, y  porównywane pary
Zwracana wartość: x.first == y.first && x.second == y.second
Złożoność: O(1)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 31 / 84
Klasa pair  funkcja make pair
template
pair make_pair(T1 x, T2 y)
Działanie: Tworzy obiekt pary
Parametry:
x, y  pierwszy i drugi element pary
Zwracana wartość: obiekt pary zawierający x i y
Złożoność: O(1)
Uwaga: Funkcja umożliwia niepodawanie w sposób jawny typów, w odróżnieniu
od wywołania konstruktora:
std::pair(10,5.6)
std::make_pair(10,5.6)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 32 / 84
Klasa pair  przykład
Przykład
#include
#include
#include
using namespace std;
template
void ShowPair(Pair p)
{
cout << "*" << p.first << "* " << p.second << endl;
}
int main(int argc, char* argv[])
{
pair p1;
ShowPair(p1); // ** 0
pair p2("Test", 10);
ShowPair(p2); // *Test* 10
ShowPair(make_pair(10, 5.7)); // *10* 5.7
ShowPair(make_pair("Zuzia", 5.7)); // *Zuzia* 5.7
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 33 / 84
Kolekcja set
Opis6
Kolekcja umożliwia przechowywanie elementów
W odróżnieniu od kolekcji sekwencyjnych, w kolekcji set porządek elementów nie jest
określany przez pozycję, na której są one wstawiane
Elementy są uporządkowywane automatycznie zgodnie z określonym kryterium
sortowania
Kolekcja umożliwia przechowywanie tylko jednej kopii elementu (powtórzenia są
zabronione)
Kolekcja jest dostosowana do wymagań algorytmów realizujących operacje zbiorowe
(suma, przecięcie, itd.)
6
Dostępna w pliku nagłówkowym set
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 34 / 84
Kolekcja set
Kryterium sortowania
Uporządkowanie ścisłe słabe:
Jeśli prawdziwe x < y, to y < x jest nieprawdziwe
Jeśli x < y i y < z, to musi zachodzić x < z
x < x jest zawsze fałszywe
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 35 / 84
Kolekcja set  konstruktory
set(const Compare &comp = Compare(), const Allocator& = Allocator())
Działanie: Tworzy pusty zbiór
Parametry:
comp  kryterium sortowania (domyślnie less)
Allocator  obiekt alokatora
Zwracana wartość: brak
Złożoność: O(1)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 36 / 84
Kolekcja set  konstruktory
set(InputIterator first, InputIterator last,
const Compare& comp = Compare(), const Allocator& = Allocator())
Działanie: Tworzy zbiór i inicjalizuje go elementami z zakresu [first,last)
Parametry:
first, last  iteratory wejściowe specyfikujące zakres
comp  kryterium sortowania (domyślnie less)
Allocator  obiekt alokatora
Zwracana wartość: brak
Złożoność (n  liczba elementów w zakresie):
O(n) jeśli elementy posortowane
O(n log n) jeśli elementy nieposortowane
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 37 / 84
Kolekcja set  konstruktory
set(const set& x)
Działanie: Tworzy zbiór i inicjalizuje go elementami ze zbioru x
Parametr:
x  zbiór użyty do zainicjalizowania tworzonej kolekcji
Zwracana wartość: brak
Złożoność: liniowa względem liczby elementów x
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 38 / 84
Kolekcja set  przykład
Przykład
#include
#include
using namespace std;
const int MAX = 10;
typedef enum {poniedzialek, wtorek, sroda, czwartek, piatek, sobota, niedziela} t_days;
int main(int argc, char* argv[])
{
int tab[MAX] = {1, 52, 31, 25, 4, 8, 65, 45, 65, 10};
set si, si2(tab, tab+10);
ShowCollection(si); //
ShowCollection(si2); // 1 4 8 10 25 31 45 52 65
set sd;
set > sd2;
sd.insert(wtorek); sd.insert(piatek);
ShowCollection(sd); // 1 4
sd2.insert(sroda); sd2.insert(sobota);
ShowCollection(sd2); // 5 2
set > sd3(sd2);
ShowCollection(sd3); // 5 2
set > sd4(sd.begin(), sd.end());
ShowCollection(sd4); // 4 1
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 39 / 84
Kolekcja set  przypisanie
set& operator =
(const set& x)
Działanie: Operator przypisania, kopiujący zawartość kolekcji
Parametr:
x  kopiowany zbiór
Złożoność: liniowa względem sumy liczby elementów kopiowanego zbioru i liczby
elementów zbioru bieżącego (elementy z bieżącego zbioru muszą być usunięte)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 40 / 84
Kolekcja set  inne metody
Metody zwracajÄ…ce iteratory
Dostępne metody begin, end, rbegin, rend zwracające iteratory analogiczne
do iteratorów dla kolekcji sekwencyjnych
Złożoność: O(1)
Uwaga: kolejność elementów określana przez kryterium sortowania
Metody zwiÄ…zane z rozmiarem
Dostępne metody empty, size, max size analogiczne jak dla kolekcji sekwencyjnych
Złożoność: O(1)
Operatory
Dostępne operatory ==, !=, <, <=, >=, > porównujące zbiory
Złożoność: liniowa względem rozmiaru mniejszego ze zbiorów
Uwaga: kolejność wstawiania elementów do porównywanych zbiorów nie ma
znaczenia  liczy się tylko ich zawartość
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 41 / 84
Kolekcja set  wstawianie elementów
pair insert(const value_type& x)
Działanie: Wstawia element do zbioru
Parametr:
x  wstawiany element
Zwracana wartość: Para opisująca wynik wstawiana; składowe oznaczają:
first  iterator do wstawionego elementu lub do elementu już istniejącego jeśli
próbujemy wstawiać element już istniejący
second  wartość logiczna określająca czy element udało się wstawić (true) czy też
taki element już istniał (false)
Złożoność: O(log n), gdzie n jest liczbą elementów w kolekcji
Przykład
#include
#include
int main(int argc, char* argv[]) {
std::set si;
std::pair::iterator, bool> status;
status = si.insert(5);
std::cout << status.second << std::endl; // 1
status = si.insert(5);
std::cout << status.second << std::endl; // 0
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 42 / 84
Kolekcja set  wstawianie elementów
iterator insert(iterator position, const value_type& x)
Działanie: Wstawia element do zbioru
Parametry:
position  wskazówka dla metody gdzie rozpocząć poszukiwanie miejsca dla
wstawianego elementu;
x  wstawiany element
Zwracana wartość: Iterator do wstawionego (bądz
istniejącego już wcześniej
w zbiorze) elementu
Złożoność: O(log n), gdzie n to liczba elementów w kolekcji
Uwaga: Elementy są posortowane wewnątrz kolekcji, więc podanie jako parametr
miejsca bliskiego docelowemu pozwala na szybsze wstawianie  nawet w czasie
O(1)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 43 / 84
Kolekcja set  wstawianie elementów
void insert(InputIterator first, InputIterator last)
Działanie: Wstawia do zbioru elementy z zakresu [first,last)
Parametry:
first, last  iteratory specyfikujące zakres wstawianych elementów
Zwracana wartość: brak
Złożoność (n oznacza liczbę wstawianych elementów, s oznacza liczbę elementów
w kolekcji):
O(n + log s) jeśli elementy z zakresu są posortowane
O(n log n + log s) jeśli elementy z zakresu nie są posortowane
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 44 / 84
Kolekcja set  usuwanie elementów
void erase(iterator position)
Działanie: Usuwa element wskazywany przez iterator
Parametr:
position  iterator wskazujący element do usunięcia
Zwracana wartość: brak
Złożoność: O(1)
Uwaga: Jeśli position nie jest iteratorem wskazującym na istniejący element, to
zachowanie niezdefiniowane
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 45 / 84
Kolekcja set  usuwanie elementów
size_type erase(const key_type& x)
Działanie: Usuwa element x ze zbioru
Parametr:
x  element do usunięcia
Zwracana wartość: liczba usuniętych elementów (0 bądz
1)
Złożoność: O(log n) gdzie n oznacza liczbę elementów w zbiorze
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 46 / 84
Kolekcja set  usuwanie elementów
iterator erase(iterator first, iterator last)
Działanie: Usuwa elementy z zakresu [first,last)
Parametry:
first, last  iteratory specyfikujÄ…ce zakres
Zwracana wartość: brak
Złożoność: O(last-first)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 47 / 84
Kolekcja set  usuwanie elementów i zamiana zbiorów
void clear()
Działanie: Usuwa wszystkie elementy ze zbioru
Parametry: brak
Zwracana wartość: brak
Złożoność: O(n)
void swap(set&)
Działanie: Zamienia zbiór ze zbiorem podanym jako parametr
Parametr: zbiór do zamiany
Zwracana wartość: brak
Złożoność: O(1)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 48 / 84
Kolekcja set  wyszukiwanie
iterator find(const key_type& x)
const_iterator find(const key_type& x) const
Działanie: Wyszukuje element x w zbiorze
Parametr:
x  wyszukiwany element
Zwracana wartość: Iterator (stały iterator) do pozycji zawierającej element x lub
iterator do pozycji za ostatnim elementem (wynik działania end()) jeśli elementu
nie ma w zbiorze
Złożoność: O(log n), gdzie n to liczebność kolekcji
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 49 / 84
Kolekcja set  zliczanie
size_type count(const key_type& x) const
Działanie: Zwraca liczbę elementów x w zbiorze
Parametr:
x  wyszukiwany element
Zwracana wartość: Liczba wystąpień x w zbiorze (0 lub 1)
Złożoność: O(log n), gdzie n to liczebność kolekcji
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 50 / 84
Kolekcja set  przykład
Przykład
#include
#include
using namespace std;
const int MAX = 5;
int main(int argc, char* argv[])
{
int tab[MAX] = {1, 2, 3, 4, 5};
set si(tab, tab+MAX), si2(tab, tab+MAX);
ShowCollection(si); // 1 2 3 4 5
// y
le!
set::iterator p = si.find(3);
*p = 7; // To jest niestety legalne
ShowCollection(si); // 1 2 7 4 5
cout << *si.find(4) << " " << si.count(4) << endl; // 0 2 !!!
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 51 / 84
Kolekcja set  modyfikacja wartości kluczy
SkÄ…d te problemy?7
Standard C++ wymaga aby obiekty przechowywane w kolekcji set nie miały
modyfikatora const
Taki element można w związku z tym zmodyfikować posługując się iteratorem!
Jak poprawnie modyfikować klucze?
1
Wyszukać element do zmiany
2
Sporządzić jego lokalną kopię
3
Zmodyfikować kopię (w obiektach można modyfikować np. jedno z pól  klucz, po
którym zbiór jest sortowany)
4
Usunąć element do zmiany
5
Wstawić nowy element
7
Więcej w S. Meyers, STL w praktyce. 50 sposobów efektywnego wykorzystania
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 52 / 84
Kolekcja set  przykład
Przykład
#include
#include
using namespace std;
const int MAX = 5;
int main(int argc, char* argv[])
{
int tab[MAX] = {1, 2, 3, 4, 5};
set si(tab, tab+MAX), si2(tab, tab+MAX);
ShowCollection(si); // 1 2 3 4 5
// y
le!
set::iterator p = si.find(3);
*p = 7; // To jest niestety legalne
ShowCollection(si); // 1 2 7 4 5
cout << *si.find(4) << " " << si.count(4) << endl; // 0 2 !!!
// Dobrze
p = si2.find(3);
int tmp = *p;
tmp = 7; // Dla obiektów modyfikujemy np. jedno z pól (klucz)
si2.erase(p);
si2.insert(tmp);
ShowCollection(si2); // 1 2 7 4 5
cout << *si2.find(4) << " " << si2.count(4) << endl; // 4 1 !!!
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 53 / 84
Kolekcja set  wyszukiwanie
iterator lower_bound(const key_type& x)
const_iterator lower_bound(const key_type& x) const
Działanie: Wyszukuje najmniejszy element nie mniejszy niż x
Parametr:
x  wyszukiwana wartość
Zwracana wartość: Iterator do najmniejszego elementu nie mniejszego niż x bądz

wartość zwracana przez end()
Złożoność: O(log n), gdzie n to liczebność kolekcji
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 54 / 84
Kolekcja set  wyszukiwanie
iterator upper_bound(const key_type& x)
const_iterator upper_bound(const key_type& x) const
Działanie: Wyszukuje największy element nie większy niż x
Parametr:
x  wyszukiwana wartość
Zwracana wartość: Iterator do najmniejszego elementu większego niż x bądz
wartość
zwracana przez end()
Złożoność: O(log n), gdzie n to liczebność kolekcji
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 55 / 84
Kolekcja set  wyszukiwanie
pair equal_range(const key_type& x)
pair equal_range(const key_type& x) const
Działanie: Wyszukuje zakres elementów zawierających x
Parametr:
x  wyszukiwana wartość
Zwracana wartość: Wyniki działania lower_bound i upper_bound w postaci pary
Złożoność: O(log n), gdzie n to liczebność kolekcji
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 56 / 84
Kolekcja set  wyszukiwanie
Przykład
#include
#include
using namespace std;
const int MAX = 5;
int main(int argc, char* argv[])
{
int tab[MAX] = {1, 19, 32, 15, 25};
set si(tab, tab+MAX);
pair::iterator,set::iterator> range;
ShowCollection(si); // 1 15 19 25 32
cout << *si.lower_bound(15) << endl; // 15
cout << *si.lower_bound(16) << endl; // 19
cout << *si.upper_bound(15) << endl; // 19
cout << *si.upper_bound(25) << endl; // 32
range = si.equal_range(15);
cout << *range.first << " " << *range.second << endl; // 15 19
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 57 / 84
Kolekcja set
Jak to wszystko jest w środku zbudowane?
Złożoności operacji mocno sugerują, że dane przechowywane są w zrównoważonych
drzewach poszukiwań binarnych
Często są to drzewa czerwono-czarne
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 58 / 84
Kolekcja multiset
Opis8
Kolekcja jest tym samym co kolekcja set z takim wyjątkiem, że elementy mogą się
powtarzać
Interfejs jest w zasadzie identyczny jak dla zbioru, z wyjÄ…tkiem jednej metody
wstawiania elementów
Nieco większego sensu nabierają takie metody jak count zwracające liczbę wystąpień
elementu w wielozbiorze
Złożoności niektórych operacji rosną
usuwanie klucza  O(log n + count)
zliczanie wystąpień klucza  O(log n + count)
8
Dostępna w pliku nagłówkowym set
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 59 / 84
Kolekcja multiset  wstawianie elementu
iterator insert(const value_type& x)
Działanie: Wstawia element x do wielozbioru
Parametr:
x  element do wstawienia
Zwracana wartość: Iterator do wstawionego elementu (dla zbioru była tu para:
iterator, wartość logiczna)
Złożoność: O(log n), gdzie n to liczebność kolekcji
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 60 / 84
Kolekcja bitset9
Opis
Tablica zawierająca ustaloną liczbę wartości logicznych
Wygodna np. do zarządzania zbiorem znaczników
Rozmiar kolekcji przekazywany jest jako parametr wzorca a nie jako parametr
konstruktora!
8
Dostępna w pliku nagłówkowym bitset
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 61 / 84
Kolekcja bitset  konstruktory
bitset()
Działanie: Tworzy obiekt klasy bitset zainicjalizowany wartościami 0 dla
wszystkich bitów
Parametry: brak
Zwracana wartość: brak
Złożoność: O(N)
bitset(unsigned long val)
Działanie: Tworzy obiekt klasy bitset zainicjalizowany M najmłodszymi
bitami val, gdzie M = min(N,sizeof(unsigned long))
Parametr:
val  wartość używana do inicjalizacji
Zwracana wartość: brak
Złożoność: O(1)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 62 / 84
Kolekcja bitset  konstruktory
bitset(const basic_string& str,
typename basic_string::size_type pos=0,
typename basic_string::size_type n =
basic_string::npos)
Działanie: Tworzy obiekt klasy bitset zainicjalizowany wartościami
przekazanymi jako obiekt klasy string (jakkolwiek  magicznie to wyglÄ…da)
Parametry:
str  obiekt klasy string używany do inicjalizacji
pos  początkowa pozycja, od której pobierane są bity do inicjalizacji
n  maksymalna liczba bitów, które mają być użyte do inicjalizacji
Zwracana wartość: brak
Złożoność: O(M), gdzie M = min(N,str.size() - pos)
Zgłaszane wyjątki:
invalid_argument  któryś ze znaków inicjalizujących miał wartość różną od 0 i 1
out_of_range  pos > str.size()
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 63 / 84
Kolekcja bitset  operatory
bitset& operator&=(const bitset& rhs)
Działanie: Iloczyn bitowy dwóch kolekcji bitset (zmieniana jest zawartość kolekcji
bieżącej)
Parametr:
rhs  kolekcja, z którą wykonywany jest iloczyn bitowy kolekcji bieżącej
Zwracana wartość: referencja do bieżącego obiektu
Złożoność: O(N)
Podobne operatory
bitset& operator|=(const bitset& rhs)  suma logiczna
bitset& operatorĆ=(const bitset& rhs)  różnica symetryczna
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 64 / 84
Kolekcja bitset  operatory
bitset& operator<<=(size_t pos)
Działanie: Przesuwa w lewo bity bieżącej kolekcji o pos pozycji
Parametr:
pos  liczba bitów do przesunięcia
Zwracana wartość: referencja do bieżącego obiektu
Złożoność: O(N)
Uwaga: pos bitów z prawej strony otrzymuje wartość 0
Podobny operator
bitset& operator>>=(size_t pos)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 65 / 84
Kolekcja bitset  operatory
bitset& set()
Działanie: Ustawia wartość wszystkich bitów na 1
Parametry: brak
Zwracana wartość: referencja do bieżącego obiektu
Złożoność: O(N)
bitset& set(size_t pos, bool val=true)
Działanie: Ustawia wartość bitu na pozycji pos na val
Parametry:
pos  pozycja bitu
val  nowa wartość bitu
Zwracana wartość: referencja do bieżącego obiektu
Złożoność: O(1)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 66 / 84
Kolekcja bitset  przykład
Przykład
#include
#include
#include
using namespace std;
int main(int argc, char* argv[])
{
bitset<10> bs10;
cout << bs10 << endl; // 0000000000
bitset<14> bs14(0xFFA9);
cout << bs14 << endl; // 11111110101001
bitset<20> bs20(string("101001011001"));
cout << bs20 << endl; // 00000000101001011001
// bs10 &= bs14; // BÅ‚Ä…d kompilacji!
bs10 Ć= bs10;
cout << bs10 << endl; // 0000000000
bs14 <<= 2;
cout << bs14 << endl; // 11111010100100
bs20.set();
cout << bs20 << endl; // 11111111111111111111
bs10.set(3);
cout << bs10 << endl; // 0000001000
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 67 / 84
Kolekcja bitset  metody
bitset& reset()
Działanie: Ustawia wartość wszystkich bitów na 0
Parametry: brak
Zwracana wartość: referencja do bieżącego obiektu
Złożoność: O(N)
bitset& reset(size_t pos)
Działanie: Ustawia wartość bitu na pozycji pos na 0
Parametr:
pos  pozycja bitu
Zwracana wartość: referencja do bieżącego obiektu
Złożoność: O(1)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 68 / 84
Kolekcja bitset  operatory
bitset operatorÜ() const
Działanie: Zwraca obiekt będący kopią bieżącego obiektu, w którym wszystkie bity
sÄ… zanegowane
Parametry: brak
Zwracana wartość: Kopia bieżącego obiektu, w którym wszystkie bity są zanegowane
Złożoność: O(N)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 69 / 84
Kolekcja bitset  negowanie bitów
bitset& flip()
Działanie: Neguje wartości wszystkich bitów w kolekcji
Parametry: brak
Zwracana wartość: referencja do bieżącego obiektu
Złożoność: O(N)
bitset& flip(size_t pos)
Działanie: Neguje wartość bitu na pozycji pos
Parametr:
pos  pozycja bitu do zanegowania
Zwracana wartość: referencja do bieżącego obiektu
Złożoność: O(1)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 70 / 84
Kolekcja bitset  konwersja
unsigned long to_ulong() const
Działanie: Konwertuje zawartość kolekcji na typ unsigned long
Parametry: brak
Zwracana wartość: Wartość typu unsigned long zawierająca na kolejnych pozycjach
wartości bitów z kolekcji bitset
Złożoność: O(1)
Uwaga: Jeśli rozmiar kolekcji jest większy niż sizeof(unsigned long) to
generowany jest wyjÄ…tek overflow_error
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 71 / 84
Kolekcja bitset  konwersja
basic_string to_string() const
basic_string >to_string() const
basic_string , allocator > to_string()
const
basic_string , allocator > to_string() const
Działanie: Tworzy obiekt klasy string zawierający na kolejnych znakach wartości 0
bÄ…dz
1 odpowiadające wartościom bitów
Parametry: brak
Zwracana wartość: Obiekt klasy string reprezentujący wartości bitów z kolekcji
Złożoność: O(N)
Uwaga: Pierwszy bit obiektu klasy string odpowiada najstarszemu bitowi kolekcji
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 72 / 84
Kolekcja bitset  inne metody
size_t count() const
Działanie: Zwraca liczbę ustawionych bitów w kolekcji
Parametry: brak
Zwracana wartość: Liczba ustawionych bitów
Złożoność: O(N)
size_t size() const
Działanie: Zwraca rozmiar kolekcji
Parametry: brak
Zwracana wartość: N
Złożoność: O(1)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 73 / 84
Kolekcja bitset  operatory porównań
bool operator==(const bitset& rhs) const
Działanie: Porównuje dwa obiekty klasy bitset
Parametr:
rhs  kolekcja do porównania
Zwracana wartość: true jeśli obiekty są identyczne
Złożoność: O(N)
bool operator!=(const bitset& rhs) const
Działanie: Porównuje dwa obiekty klasy bitset
Parametr:
rhs  kolekcja do porównania
Zwracana wartość: true jeśli obiekty nie są identyczne
Złożoność: O(N)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 74 / 84
Kolekcja bitset  testowanie bitów
bool test(size_t pos) const
Działanie: Sprawdza wartość bitu pos
Parametr:
pos  numer bitu do sprawdzenia
Zwracana wartość: true jeśli bit jest ustawiony
Złożoność: O(1)
Uwaga: Jeśli pos nie jest prawidłowym numerem pozycji to generuje wyjątek
out_of_range
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 75 / 84
Kolekcja bitset  testowanie bitów
bool any() const
Działanie: Sprawdza czy jakikolwiek bit jest ustawiony
Parametry: brak
Zwracana wartość: true jeśli jakikolwiek bit kolekcji jest ustawiony
Złożoność: O(N), choć może być nawet O(1) dla niektórych implementacji
bool none() const
Działanie: Sprawdza czy żaden bit nie jest ustawiony
Parametry: brak
Zwracana wartość: true jeśli żaden bit kolekcji nie jest ustawiony
Złożoność: O(N), choć może być nawet O(1) dla niektórych implementacji
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 76 / 84
Kolekcja bitset  operatory przesunięć bitowych
bitset operator<<(size_t pos) const
Działanie: Zwraca obiekt będący kopią obiektu bieżącego przesuniętą o pos bitów
w lewo
Parametr:
pos  przesunięcie
Zwracana wartość: Kopia obiektu bieżącego przesunięta w lewo o pos bitów
Złożoność: O(N)
bitset operator>>(size_t pos) const
Działanie: Zwraca obiekt będący kopią obiektu bieżącego przesuniętą o pos bitów
w prawo
Parametr:
pos  przesunięcie
Zwracana wartość: Kopia obiektu bieżącego przesunięta w prawo o pos bitów
Złożoność: O(N)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 77 / 84
Kolekcja bitset  operatory indeksowania
bool operator[](size_t pos) const
Działanie: Zwraca wartość bitu na pozycji pos
Parametr:
pos  pozycja bitu
Zwracana wartość: true jeśli bit jest ustawiony
Złożoność: O(1)
Uwaga: Jeśli pos jest niepoprawne to zachowanie niezdefiniowane
bitset::reference operator[](size_t pos)
Działanie: Zwraca obiekt typu bitset::reference taki, że:
(*this)[pos] == this->test(pos)
(*this)[pos ] = val jest równoważne this->set(pos, val)
Parametr:
pos  pozycja bitu
Zwracana wartość: Obiekt typu bitset::reference
Złożoność: O(1)
Uwaga: Jeśli pos jest niepoprawne to zachowanie niezdefiniowane
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 78 / 84
Kolekcja bitset  dostęp do bitów przez operator[]
Metody
reference& operator=(bool x)  umożliwia przypisania b[i] = x
reference& operator=(const reference&)  umożliwia przypisania
b[i] = b[j]
bool operatorÜ() const  umożliwia zanegowanie bitu: a = Üb[i]
operator bool() const  umożliwia automatyczną konwersję do typu bool:
x = b[i]
reference& flip()  umożliwia negowanie bitu: b[i].flip()
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 79 / 84
Kolekcja bitset  operatory bitowe
bitset operator&(const bitset& lhs, const bitset& rhs)
Działanie: Zwraca obiekt klasy bitset będący iloczynem bitowym lhs i rhs
Parametry:
lhs, rhs  obiekty, na których wykonywany jest iloczyn bitowy
Zwracana wartość: Obiekt klasy bitset zawierający iloczyn bitowy
Złożoność: O(N)
Podobne operatory
bitset operator|(const bitset& lhs, const bitset & rhs) 
zwraca sumÄ™ logicznÄ…
bitset operatorĆ(const bitset& lhs, const bitset & rhs) 
zwraca różnicę symetryczną
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 80 / 84
Kolekcja bitset  operatory strumieniowe
template
basic_istream&
operator>>(basic_istream& is, bitset& x)
Działanie: Wczytuje ze strumienia wejściowego nie więcej niż N bitów do kolekcji
Parametry:
is  strumień wejściowy
x  obiekt klasy bitset
Zwracana wartość: referencja do obiektu strumienia wejściowego
Złożoność: O(N)
Uwaga: Wczytywanie bitów kończy się jeśli zajdzie dowolny z warunków:
wczytano N bitów
napotkano znak EOF w strumieniu
następny znak w strumieniu jest różny od 0 i 1
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 81 / 84
Kolekcja bitset  operatory strumieniowe
template
basic_ostream&
operator<<(basic_ostream& os, const bitset& x)
Działanie: Wypisuje bity z kolekcji w postaci łańcucha znakowego do strumienia
wyjściowego
Parametry:
os  strumień wyjściowy
x  kolekcja bitset
Zwracana wartość: referencja do obiektu strumienia wyjściowego
Złożoność: O(N)
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 82 / 84
Kolekcja bitset  przykład
Przykład
#include
#include
#include
using namespace std;
int main(int argc, char* argv[])
{
bitset<16> bs(0xF1F1);
cout << bs << endl; // 1111000111110001
cout << Übs << endl; // 0000111000001110
bs[4].flip();
bs[5] = 0;
cout << bs << endl; // 1111000111000001
bs[4] = bs[0];
cout << bs << endl; // 1111000111010001
cout << bs.count() << endl; // 9
cout << (bs Ć bitset<16>(string("10010010"))) << endl; // 1111000101000011
}
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 83 / 84
Co będzie za tydzień?
Poznamy kolejne kolekcje asocjacyjne (map, multimap)
Dowiemy się jeszcze więcej o iteratorach
Poznamy też kolejne algorytmy
Sebastian Deorowicz (PÅšl) Kolekcje, algorytmy 2006 10 23 84 / 84