[ Pobierz całość w formacie PDF ]
const Container& cont = Container())
: comp(cmp), c(cont) {
make_heap(c.begin(),c.end(),comp);
}
template
priority_queue(InputIterator first, InputIterator last,
const Compare& cmp = Compare(),
const Container& cont = Container())
: comp(cmp), c(cont) {
c.insert(c.end(),first,last);
make_heap(c.begin(),c.end(),comp);
}
void push(const value_type& x); {
c.push_back(x);
push_heap(c.begin(),c.end(),comp);
}
void pop() {
pop_heap(c.begin(),c.end(),comp);
c.pop_back();
}
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const value_type& top() const { return c.front(); }
};
}
Jak można zauważyć, kolejka priorytetowa używa algorytmów stogowych, zdefiniowa-
nych w bibliotece STL. Algorytmy te opisane sÄ… w podrozdziale 9.9.4. na stronie 375.
Zwróć uwagę jednak, że w odróżnieniu od innych kontenerów nie zostaly w tym miejscu
zdefiniowane żadne operatory porównania.
Poniższa część tego podrozdzialu zawiera szczególowy opis pól oraz operacji.
Definicje typu
priority_queue::value_type
" Rodzaj elementów umieszczonych w kontenerze.
" Skladowa równoważna jest skladowej container::value_type.
priority_queue::size_type
" Typ calkowity bez znaku, określający rozmiar umieszczonych elementów.
" Skladowa równoważna jest skladowej container::size_type.
420 10. KONTENERY SPECJALNE
priority_queue::container_type
" Rodzaj kontenera.
Konstruktory
priority_queue::priority_queue ()
" Konstruktor domyślny.
" Tworzy pustÄ… kolejkÄ™ priorytetowÄ….
explicit priority_queue::priority_queue (const CompFunc& op)
" Tworzy pustą kolejkę priorytetową wykorzystującą kryterium sortowania określone
przez argument op.
" Przyklady przedstawiające sposób przekazywania kryterium sortowania w postaci
argumentu konstruktora przedstawione zostaly na stronie 191 oraz 210.
priority_queue::priority_queue (const CompFunc& op,
const Container& cont)
" Tworzy kolejkÄ™ priorytetowÄ… inicjalizowanÄ… elementami zawartymi w kontenerze cont
oraz używającą kryterium sortowania przekazane w argumencie op.
" Kopiowane sÄ… wszystkie elementy umieszczone w kontenerze cont.
priority_queue::priority_queue (InputIterator beg,
InputIterator end)
" Tworzy kolejkę priorytetową inicjalizowaną elementami należącymi do zakresu
[beg,end).
" Funkcja ta jest wzorcem (patrz strona 27), dlatego też elementy zakresu zródlowego
mogą być dowolnego typu, który możliwy jest do przeksztalcenia na typ elementu
umieszczonego w kontenerze.
priority_queue::priority_queue (InputIterator beg,
InputIterator end,
const CompFunc& op)
" Tworzy kolejkę priorytetową inicjalizowaną elementami należącymi do zakresu
[beg,end), używającą kryterium sortowania przekazane w argumencie op.
" Funkcja ta jest wzorcem (patrz strona 27), dlatego też elementy zakresu zródlowego
mogą być dowolnego typu, który możliwy jest do przeksztalcenia na typ elementu
umieszczonego w kontenerze.
" Przyklady przedstawiające sposób przekazywania kryterium sortowania w postaci
arugumentu konstruktora przedstawione zostaly na stronie 191 oraz 210.
priority_queue::priority_queue (InputIterator beg,
InputIterator end,
const CompFunc& op,
const Container& cont)
" Tworzy kolejkÄ™ priorytetowÄ… inicjalizowanÄ… elementami zawartymi w kontenerze cont
oraz należącymi do zakresu [beg, end), używającą kryterium sortowania przeka-
zane w argumencie op.
10.4. KONTENER BITSET 421
" Funkcja ta jest wzorcem (patrz strona 27), dlatego też elementy zakresu zródlowego
mogą być dowolnego typu, który możliwy jest do przeksztalcenia na typ elementu
umieszczonego w kontenerze.
™nne funkcje skladowe
size_type priority_queue::size () const
" Zwraca bieżącą liczbę elementów.
" W celu sprawdzenia, czy kolejka jest pusta, używaj funkcji skladowej o nazwie
empty(), ponieważ może ona dzialać szybciej.
bool priority_queue::empty () const
" Zwraca wartość logiczną, określającą, czy kolejka jest pusta (nie zawiera elementów).
" Funkcja skladowa równoważna konstrukcji postaci priority_queue::size()
==0, lecz może dzialać od niej szybciej.
void priority_queue::push (const value_type& elem)
" Wstawia do kolejki kopię elementu określonego przez wartość elem.
const value_type& priority_queue::top () const
" Zwraca kolejny element kolejki priorytetowej. Będzie nim element posiadający naj-
większą wartość z wszystkich elementów kolejki. Jeśli istnieje więcej niż jeden taki
element, nie jest zdefiniowane, który z nich zostanie zwrócony.
" Przed wywolaniem funkcji skladowej należy upewnić się, czy kolejka zawiera jakie-
kolwiek elementy (size()>0). W innym przypadku jej dzialanie jest nieokreślone.
void priority_queue::pop ()
" Usuwa kolejny element kolejki priorytetowej. Będzie nim element posiadający mak- [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl rafalstec.xlx.pl
const Container& cont = Container())
: comp(cmp), c(cont) {
make_heap(c.begin(),c.end(),comp);
}
template
priority_queue(InputIterator first, InputIterator last,
const Compare& cmp = Compare(),
const Container& cont = Container())
: comp(cmp), c(cont) {
c.insert(c.end(),first,last);
make_heap(c.begin(),c.end(),comp);
}
void push(const value_type& x); {
c.push_back(x);
push_heap(c.begin(),c.end(),comp);
}
void pop() {
pop_heap(c.begin(),c.end(),comp);
c.pop_back();
}
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const value_type& top() const { return c.front(); }
};
}
Jak można zauważyć, kolejka priorytetowa używa algorytmów stogowych, zdefiniowa-
nych w bibliotece STL. Algorytmy te opisane sÄ… w podrozdziale 9.9.4. na stronie 375.
Zwróć uwagę jednak, że w odróżnieniu od innych kontenerów nie zostaly w tym miejscu
zdefiniowane żadne operatory porównania.
Poniższa część tego podrozdzialu zawiera szczególowy opis pól oraz operacji.
Definicje typu
priority_queue::value_type
" Rodzaj elementów umieszczonych w kontenerze.
" Skladowa równoważna jest skladowej container::value_type.
priority_queue::size_type
" Typ calkowity bez znaku, określający rozmiar umieszczonych elementów.
" Skladowa równoważna jest skladowej container::size_type.
420 10. KONTENERY SPECJALNE
priority_queue::container_type
" Rodzaj kontenera.
Konstruktory
priority_queue::priority_queue ()
" Konstruktor domyślny.
" Tworzy pustÄ… kolejkÄ™ priorytetowÄ….
explicit priority_queue::priority_queue (const CompFunc& op)
" Tworzy pustą kolejkę priorytetową wykorzystującą kryterium sortowania określone
przez argument op.
" Przyklady przedstawiające sposób przekazywania kryterium sortowania w postaci
argumentu konstruktora przedstawione zostaly na stronie 191 oraz 210.
priority_queue::priority_queue (const CompFunc& op,
const Container& cont)
" Tworzy kolejkÄ™ priorytetowÄ… inicjalizowanÄ… elementami zawartymi w kontenerze cont
oraz używającą kryterium sortowania przekazane w argumencie op.
" Kopiowane sÄ… wszystkie elementy umieszczone w kontenerze cont.
priority_queue::priority_queue (InputIterator beg,
InputIterator end)
" Tworzy kolejkę priorytetową inicjalizowaną elementami należącymi do zakresu
[beg,end).
" Funkcja ta jest wzorcem (patrz strona 27), dlatego też elementy zakresu zródlowego
mogą być dowolnego typu, który możliwy jest do przeksztalcenia na typ elementu
umieszczonego w kontenerze.
priority_queue::priority_queue (InputIterator beg,
InputIterator end,
const CompFunc& op)
" Tworzy kolejkę priorytetową inicjalizowaną elementami należącymi do zakresu
[beg,end), używającą kryterium sortowania przekazane w argumencie op.
" Funkcja ta jest wzorcem (patrz strona 27), dlatego też elementy zakresu zródlowego
mogą być dowolnego typu, który możliwy jest do przeksztalcenia na typ elementu
umieszczonego w kontenerze.
" Przyklady przedstawiające sposób przekazywania kryterium sortowania w postaci
arugumentu konstruktora przedstawione zostaly na stronie 191 oraz 210.
priority_queue::priority_queue (InputIterator beg,
InputIterator end,
const CompFunc& op,
const Container& cont)
" Tworzy kolejkÄ™ priorytetowÄ… inicjalizowanÄ… elementami zawartymi w kontenerze cont
oraz należącymi do zakresu [beg, end), używającą kryterium sortowania przeka-
zane w argumencie op.
10.4. KONTENER BITSET 421
" Funkcja ta jest wzorcem (patrz strona 27), dlatego też elementy zakresu zródlowego
mogą być dowolnego typu, który możliwy jest do przeksztalcenia na typ elementu
umieszczonego w kontenerze.
™nne funkcje skladowe
size_type priority_queue::size () const
" Zwraca bieżącą liczbę elementów.
" W celu sprawdzenia, czy kolejka jest pusta, używaj funkcji skladowej o nazwie
empty(), ponieważ może ona dzialać szybciej.
bool priority_queue::empty () const
" Zwraca wartość logiczną, określającą, czy kolejka jest pusta (nie zawiera elementów).
" Funkcja skladowa równoważna konstrukcji postaci priority_queue::size()
==0, lecz może dzialać od niej szybciej.
void priority_queue::push (const value_type& elem)
" Wstawia do kolejki kopię elementu określonego przez wartość elem.
const value_type& priority_queue::top () const
" Zwraca kolejny element kolejki priorytetowej. Będzie nim element posiadający naj-
większą wartość z wszystkich elementów kolejki. Jeśli istnieje więcej niż jeden taki
element, nie jest zdefiniowane, który z nich zostanie zwrócony.
" Przed wywolaniem funkcji skladowej należy upewnić się, czy kolejka zawiera jakie-
kolwiek elementy (size()>0). W innym przypadku jej dzialanie jest nieokreślone.
void priority_queue::pop ()
" Usuwa kolejny element kolejki priorytetowej. Będzie nim element posiadający mak- [ Pobierz całość w formacie PDF ]