Adaptory kontenerów

Adaptory kontenerów

szablony klas używające kontenerów do przechowywania elementów oraz udostępniające ograniczony interfejs.

Informacja

Adaptory nie posiadają iteratorów. Nie można ich stosować w standardowych algorytmach.

stack<T>

• stos
• pozwala jedynie na dodawanie i usuwanie elementów na jego końcu (LIFO)
• <stack>

queue<T>

• kolejka FIFO
• <queue>

priority_queue<T>

• kolejka priorytetowa układa elementy w takiej kolejności, że pierwszy jest zawsze element o największej wartości
• możliwe jest dodanie elementu do kolejki a także sprawdzenie i usunięcie pierwszego elementu
• <queue>

std::stack

Stos jest kontenerem sekwencyjnym pozwalającym na dodawanie i usuwanie elementów tylko z jednego końca (LIFO).

Szablon klasy std::stack jest adaptorem dowolnego kontenera sekwencyjnego (deque, vector, list) udostępniającego składowe back, push_back i pop_back. Domyślnie stosowany jest kontener std::deque.

Interfejs stosu:

bool stack::empty() const

zwraca true jeśli stos jest pusty

void stack::pop()

usuwa element ze szczytu stosu

void stack::push(const value_type &x)

wstawia element x na szczyt stosu

size_type stack::size() const

zwraca liczbę elementów na stosie

value_type &stack::top()

zwraca element ze szczytu stosu

std::queue

Kolejka jest kontenerem sekwencyjnym, pozwalającym na dodawanie elementów na jednym końcu i usuwanie ich na drugim (FIFO)

Szablon klasy std::queue<T, Container> jest adaptorem dowolnego kontenera sekwencyjnego udostępniającego metody: front, back, push_back i pop_front. Domyślnie stosowany jest kontener std::deque.

Interfejs kolejki:

bool queue::empty() const

zwraca true jeśli kolejka jest pusta

void queue::pop()

usuwa pierwszy element z kolejki

value_type &queue::front()

zwraca pierwszy element kolejki

value_type &queue::back()

zwraca ostatni, czyli ostatnio dodany element kolejki

void queue::push(const value_type &x)

na koniec kolejki wstawia element x

size_type queue::size() const

zwraca liczbę elementów znajdujących się w kolejce

std::bitset

std::bitset

efektywny zbiór bitowy o stałej wielkości.

Różnice w stosunku do vector<bool>

• nie zawiera iteratorów
• rozmiar musi być znany w trakcie kompilacji

bitset<16> small_set(string("1011011011"));  // konstruktor - 16 bitów

small_set.flip();  // odwrócenie wszystkich bitów
small_set.flip(8);  // odwrócenie 8-go bitu

cout << small_set << endl; // wypisanie na ekranie

if (bset_one.test(4))
    cout << "bit na pozycji 4 jest ustawiony" << endl;
else
    cout << "bit na pozycji 4 nie jest ustawiony" << endl;

std::bitset - metody

bool any() const

zwraca true, jeżeli jakikolwiek bit jest ustawiony na 1

size_t count() const

zwraca ilość bitów ustawionych na 1

bitset<N> &flip()

odwraca wartość wszystkich bitów

bitset<N> &flip(size_t n)

odwraca wartość n-tego bitu

bool none() const

zwraca true, gdy wszystkie bity są zerami

bitset<N> &reset()

zeruje wszystkie bity

bool test(size_t n) const

testuje wartość n-tego bitu

string to_string() const

zwraca ciąg znaków reprezentujących bity np. „10000101”

long to_ulong() const

przetwarza zawartość obiektu bitset na wartość całkowitą

std:bitset - operacje bitowe

Na obiektach bitset<N> możliwe jest wykonywanie operacji bitowych.

Zdefiniowane są odpowiednie operatory: &, |, >>, <<, ~, ^

// operacje bitowe
std::bitset<8> one;
std::bitset<8> two;

one[2] = 1;
two[5] = 1;

bitset<8> three = ~( one>>1 | two );
std::cout << three << " : " << three.to_ulong() << '\n'; // 11011101 : 221