To есть зависят от параметра шаблона. См. раздел Разрешение имен в главе 5. Как объяснялось в главе 5, подойдет любое допустимое уточнение, например, PQV::.

whiledpqi .emptyO) { cout pqi .topO : pqi.popO:

} III:-

Если флаг sorted равен true, значит, вектор не оформлен в виде кучи, а содержит отсортированную последовательность. Функция assureHeap() гарантирует, что он будет возвращен к нужной форме перед выполнением каких-либо операций, специфических для кучи. Теперь первый цикл for в функции main() выводит содержимое кучи по мере ее построения.

В двух предыдущих программах нам прищлось использовать вроде бы лищний префикс this->. Хотя некоторые компиляторы позволяют обойтись без него, по стандарту C-I-I- он необходим. Обратите внимание: класс PQV является производным от vector<T>, поэтому имена функций begin () и end(), унаследованных от vector<T>, принадлежат к числу зависимых. Компилятор не может разрешать имена из зависимых базовых классов (в данном случае vector) в определении шаблона, потому что для данной специализации может быть использована переопределенная версия шаблона, которая не содержит соответствующих членов. Специальные правила оформления имен предотвращают ситуацию, при которой в одних случаях вызывается функция базового класса, а в других - функция из внешней области видимости (например, глобальной). Компилятор не знает, что вызов begin() является зависимым, поэтому мы должны сообщить ему об этом при помощи уточнения this->l Так компилятор узнает, что begin() находится в области видимости PQV, и поэтому нужно ожидать полной специализации PQV. Если бы уточняющий префикс отсутствовал, то компилятор попытался бы использовать для имен begin и end раннее разрешение на стадии определения шаблона (такая попытка завершилась бы неудачей, потому что во внешних лексических областях видимости такие имена не объявлены). В нашей программе компилятор ожидает до момента создания специализации pqi, а затем находит правильные специализации begin() и end() в классе vector<int>.

Единственный недостаток этого решения состоит в том, что пользователь должен помнить о необходимости вызова sort() перед просмотром сортированной последовательности (хотя теоретически можно переопределить все функции, создающие итераторы, так чтобы они гарантировали сортировку). Другое решение - задействовать приоритетную очередь, которая вектором формально не является, и строить вектор по запросу пользователя:

: C07:PriorityQueue7.cpp

Приоритетная очередь, создающая

отсортированный вектор по запросу

linclude <algorithm>

linclude <cstdlib>

linclude <ctime>

linclude <iostream>

linclude <iterator>

linclude <queue>

linclude <vector>

using namespace std:

tempiate<class T. class Compare> class PQV {

vector<T> v: Compare comp: public:

Вызывать make heap() не нужно:

контейнер не содержит элементов

PQV (Compare cmp = CompareO) : comp (cmp) {}

void push(const T& x) {

Занести элемент в конец:

v.push back(x):

Внести изменения в кучу:

push heap(v.beginO. v.endO. comp):

void popO {

Перемещение верхнего элемента в последнюю позицию: pop heap(v.beginO. v.endO. comp): Удаление элемента: v.pop back():

const Т& topO { return v.frontO: } bool emptyO const { return v.emptyO: } int SizeO const { return v.sizeO: } typedef vector<T> TVec: TVec vectorO {

TVec r(v.beginO. v.endO):

Остается отсортировать существующую кучу

sort heap(г.beginO. r.endO. comp):

Приведение к порядку приоритетной очереди:

reverse(г.beginO, r.endO):

return г:

int mainO { PQV<int. less<int> > pqi: srand(time(0)): for(int i = 0: i < 100: i++)

pqi.push(rand() % 25): const vector<int>& v - pqi.vectorО: copy(v.beginO. v.endO,

ostream iterator<int>(cout, )):

cout \n...........\n :

whi 1 e(!pqi .emptyO) {

cout pqi .topO :

pqi .popO:

} /:-

Шаблон класса PQV построен по тому же образцу, что и шаблон priority queue библиотеки STL. Но в него включена дополнительная функция getVector() для создания нового вектора, являющегося копией содержимого PQV (то есть базовой кучи). Далее копия сортируется (при этом вектор PQV остается неизменным), а ее элементы переставляются в обратном порядке, чтобы порядок перебора в новом векторе соответствовал порядку извлечения элементов из приоритетной очереди.

Совмешение этой методики с наследованием от prion*ty queue (см. пример PriorityQueue4.cpp) позволяет получить более компактный код:

: C07:PriorityQueue8.cpp

Более компактная версия PriorityQueue7.cpp

linclude <a1gorithm> linclude <cstdlib> linclude <ctime> linclude <iostream> linclude <iterator> linclude <queue> using namespace std;

tempiate<class T> class PQV ; public priority queue<T> { public; typedef vector<T> TVec; TVec vector0 {

TVec r(c.beginO. c.endO);

Базовая куча хранится в переменной с

sort heap(r.begin(). r.endO. comp);

Приведение к порядку приоритетной очереди;

reverseCr.beginO. r.endO);

return г;

int mainO { PQV<int> pqi; srand(time(0)); forCint i = 0; i < 100; i++)

pqi .pushCrandO % 25): const vector<int>& v - pqi.vectorC): copyCv.beginO. v.endO.

ostream iterator<int>Ccout. )):

cout \n...........\n :

whileClpqi .emptyO) {

cout pqi .topO :

pqi .popO;

} /:-

Благодаря своей компактности это решение оказывается самым простым и удобным. Вдобавок оно гарантирует, что пользователь всегда получит доступ к отсортированному вектору. Теоретически существует только одна проблема: функция getVector() возвращает vector<T> по значению, что может привести к большим затратам ресурсов при сложных типах параметра Т.

Битовые поля

Принято считать, что язык С близок к оборудованию , поэтому многих программистов раздражает отсутствие в нем собственного варианта представления двоичных чисел. Есть десятичные числа, есть шестнадцатеричные (которые можно терпеть только из-за удобной группировки битов в уме), но работать в восьмеричной системе? Фу. Ни в одной спецификации микросхемы регистры не описываются ни в восьмеричной, ни в шестнадцатеричной системах - только в двоичной. Однако С не позволяет использовать запись вида ObOlOllOl, абсолютно естественную для языка, близкого к оборудованию .

Хотя в C-I--I- естественная двоичная запись так и не появилась, ситуация несколько улучшилась с появлением классов bitset и vector<bool>. Оба класса пред-