Сделай Сам Свою Работу на 5

Алгоритмы для работы с хипом





В стандартной библиотеке используется макс-хип. Макс-хип – это представленное в виде массива двоичное дерево, для которого значение ключа в каждом узле больше либо равно значению ключа в каждом из узлов-потомков. (Подробное обсуждение макс-хипа можно найти в [SEDGEWICK88]. Альтернативой ему является мин-хип, для которого значение ключа в каждом узле меньше либо равно значению ключа в каждом из узлов-потомков.) В реализации из стандартной библиотеки самое большое значение (корень дерева) всегда оказывается в начале массива. Например, приведенная последовательность букв удовлетворяет требованиям, накладываемым на хип:

 

X T O G S M N A E R A I

 

В данном примере X – это корневой узел, слева от него находится T, а справа – O. Обратите внимание, что потомки не обязательно должны быть упорядочены (т.е. значение в левом узле не обязано быть меньше, чем в правом). G и S – потомки узла T, а M и N – потомки узла O. Аналогично A и E – потомки G, R и A – потомки S, I – левый потомок M, а N – листовой узел без потомков.

Четыре обобщенных алгоритма для работы с хипом: make_heap(), pop_heap(), push_heap() и sort_heap() – поддерживают его создание и различные манипуляции. В последних трех алгоритмах предполагается, что последовательность, ограниченная парой итераторов, – действительно хип (в противном случае поведение программы не определено). Заметим, что список нельзя использовать как контейнер для хранения хипа, поскольку он не поддерживает произвольный доступ. Встроенный массив для размещения хипа использовать можно, но в этом случае трудно применять алгоритмы pop_heap() и push_heap(), так как они требуют изменения размера контейнера. Мы опишем все четыре алгоритма, а затем проиллюстрируем их работу на примере небольшой программы.



Алгоритм make_heap()

template< class RandomAccessIterator > void make_heap( RandomAccessIterator first, RandomAccessIterator last );   template< class RandomAccessIterator, class Compare > void make_heap( RandomAccessIterator first,

RandomAccessIterator last, Compare comp );

make_heap() преобразует в хип последовательность, ограниченную диапазоном [first,last). В первом варианте для сравнения используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция comp.



Алгоритм pop_heap()

template< class RandomAccessIterator > void pop_heap( RandomAccessIterator first, RandomAccessIterator last );   template< class RandomAccessIterator, class Compare > void pop_heap( RandomAccessIterator first,

RandomAccessIterator last, Compare comp );

pop_heap() в действительности не исключает наибольший элемент, а переупорядочивает хип. Он переставляет элементы в позициях first и last-1, а затем перестраивает в хип последовательность в диапазоне [first,last-1). После этого “вытолкнутый” элемент можно получить посредством функции-члена back() контейнера либо по-настоящему исключить его с помощью pop_back(). В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция comp.

Алгоритм push_heap()

template< class RandomAccessIterator > void push_heap( RandomAccessIterator first, RandomAccessIterator last );   template< class RandomAccessIterator, class Compare > void push_heap( RandomAccessIterator first,

RandomAccessIterator last, Compare comp );

push_heap() предполагает, что последовательность, ограниченная диапазоном [first,last-1), – хип и что новый добавляемый к хипу элемент находится в позиции last-1. Все элементы в диапазоне [first,last) реорганизуются в новый хип. Перед вызовом push_heap() необходимо вставить новый элемент в конец контейнера, возможно, применив функцию push_back() (это показано в примере ниже). В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера; во втором – операция comp.

Алгоритм sort_heap()

template< class RandomAccessIterator > void sort_heap( RandomAccessIterator first, RandomAccessIterator last );   template< class RandomAccessIterator, class Compare > void sort_heap( RandomAccessIterator first,

RandomAccessIterator last, Compare comp );



sort_heap() сортирует последовательность в диапазоне [first,last), предполагая, что это правильно построенный хип; в противном случае поведение программы не определено. (Разумеется, после сортировки хип перестает быть хипом!) В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция comp.

#include <algorithm> #include <vector> #include <assert.h>   template <class Type> void print_elements( Type elem ) { cout << elem << " "; }   int main() { int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 }; vector< int, allocator > vec( ia, ia+12 );     // печатается: 51 35 40 23 29 20 26 22 19 12 17 15 make_heap( &ia[0], &ia[12] ); void (*pfi)( int ) = print_elements; for_each( ia, ia+12, pfi ); cout << "\n\n";   // печатается: 12 17 15 19 23 20 26 51 22 29 35 40 // минимальный хип: в корне наименьший элемент make_heap( vec.begin(), vec.end(), greater<int>() ); for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";   // печатается: 12 15 17 19 20 22 23 26 29 35 40 51 sort_heap( ia, ia+12 ); for_each( ia, ia+12, pfi ); cout << "\n\n";   // добавим новый наименьший элемент vec.push_back( 8 );   // печатается: 8 17 12 19 23 15 26 51 22 29 35 40 20 // новый наименьший элемент должен оказаться в корне push_heap( vec.begin(), vec.end(), greater<int>() ); for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";   // печатается: 12 17 15 19 23 20 26 51 22 29 35 40 8 // наименьший элемент должен быть заменен на следующий по порядку   pop_heap( vec.begin(), vec.end(), greater<int>() ); for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";

}

 

 


#

#include, директива

использование с using-директивой, 68, 427

использование с директивой связывания, 354

*

умножения оператор

комплексных чисел, 155

ч

члены класса

функции-члены

константные, 611–14

подвижные (volatile), 611–14

Д

деструктор(ы)

для элементов масс??а

освобождение динамической памяти, 693–94

abort(), функция

вызов из terminate() как подразумеваемое поведение, 541

abs(), функция

поддержка для комплексных чисел, 156

accumulate(), обобщенный алгоритм, 1104

adjacent_difference(), обобщенный алгоритм, 1106

adjacent_find(), обобщенный алгоритм, 1107

ainooi

к базовому классу, 880–88

algorithm, заголовочный файл, 584

any(), функция

в классе bitset, 167

append(), функция

конкатенация строк, 287

argc, переменная

счетчик аргументов в командной строке, 356

argv, массив

для доступа к аргументам в командной строке, 356

assert(), макрос, 51

использование для отладки, 226

at(), функция

контроль выхода за границы диапазона во время выполнения, 289

atoi(), функция

применение для обработки аргументов в командной строке, 360

auto_ptr, шаблон класса, 395–400

memory, заголовочный файл, 395

инициализация, 397

подводные камни, 399

aункции

интерфейс

включение объявления исключений в, 546

B

back(), функция

поддержка очереди, 316

back_inserter(), адаптор функции

использование в операции вставки push_back(), 577

begin(), функция

итератор

возврат с помощью, 578

использование, 261

binary_search(), обобщенный алгоритм, 1108

bind1st(), адаптор функции, 573

bind2nd(), адаптор функции, 573

bitset, заголовочный файл, 168

bitset, класс, 165

size(), функция, 167

test(), функция, 167

to_long(), функция, 170

to_string(), функция, 170

заголовочный файл bitset, 168

оператор доступа к биту ([]), 167

операции, 168–71

break, 218–19

break, инструкция

использование для выхода из инструкции switch, 203

сравнение с инструкцией return, 346

C

C, язык

символьные строки

динамическое выделение памяти для, 401

необходимость доступа из класса string, 128

отсутствие завершающего нуля как программная ошибка, 402

C_str(), функция

преобразование объектов класса string в C-строки, 137

C++, язык

std, пространство имен, 426–28

введение в (глава), 12–13

компоненты

(часть 2), 319

типы данных (глава), 98–140

предопределенные операторы (таблица), 727

case, ключевое слово

использование в инструкции switch (таблица), 202

catch-обработчик, 62, 534, 537

критерий выбора, 63

определение, 537

универсальный обработчик, 543–45

cerr, 26

представление стандартного вывода для ошибок с помощью, 1041

char *, указатель

работы с C-строками символов, 92

char, тип, 76

check_range(), пример функции

как закрытая функция-член, 51

cin, 26

использование итератора istream_iterator, 579

представление стандартного ввода с помощью, 1041

class, ключевое слово

typename как синоним, 479

использование в определении класса, 594

использование в определении шаблона класса, 801

использование в параметрах-типах шаблона

класса, 800

функции, 476

const, квалификатор

вопросы разрешения перегрузки функций

параметры-типы, 432

вопросы разрешения перезагрузки функций

использование преобразования квалификаторов, 449

ранжирование преобразований, связанных с инициализацией ссылочных параметров, 473

константная функция-член, 611–14

константные объекты, динамическое выделение и освобождение памяти, 402–3

константные параметры

параметры-ссылки с квалификатором const, 330, 340

передача массива из константных элементов, 336

константный итератор, 262

контейнеры, необходимость константного итератора, 575

преобразование объектов в константы, 101

сравнение с volatile, 127

ссылка, инициализация объектом другого типа, 105

указатели на константные объекты, 101

const_cast, оператор, 180

continue, инструкция, 219

copy(), обобщенный алгоритм, 1109

использование класса inserter, 305

конкатенация векторов с помощью, 557

count(), обобщенный алгоритм, 1112

использование istream_iterator и ostream_iterator, 581

использование с контейнерами multimap и multiset, 311

использование с множествами, 306

использование с отображениями, 298

count(), функция

в классе bitset, 167

count_if(), обобщенный алгоритм, 1114

cout, 26

представление стандартного вывода с помощью, 1041

cпецификации

исключений

для документирования исключений, 546

D

default, ключевое слово

использование в инструкции switch, 202, 205

delete, оператор, 35, 162–63, 744–53

безопасное и небезопасное использование, примеры, 394

для массивов, 749–51

объектов класса, 750

синтаксис, 402

для одиночного объекта, 392

использование класса-распределителя памяти (сноска), 256

размещения, 751–53

deque (двустороння очередь, дека)

использование итераторов с произвольным доступом, 583

как последовательный контейнер, 248–301

применение для реализации стека, 314

требования к вставке и доступу, 252

do-while, инструкция, 216–18

сравнение с инструкциями for и while, 209

E

иници??изация

массива

динамически выделенных объектов классов, 691–94

копиру??ий

конструктор, 680–82

end(), функция

итератор, использование, 261

endl, манипулятор потока iostream, 27

enum, ключевое слово, 112

equal_range(), обобщенный алгоритм

использование с контейнерами multimap и multiset, 310

extern "C"

и перегруженные функции, 438–39

неприменимость безопасного связывания, 440

указатели на функции, 373–75

extern, ключевое слово

использование с указателями на функции, 373

использование с членами пространства имен, 418

как директива связывания, 354

объявление

константы, 386

шаблона функции, 481

объявления объектов

без определения, 382

размещение в заголовочном файле, 384

F

f, суффикс

нотация для литерала с плавающей точкой одинарной точности, 77

find(), обобщенный алгоритм

использование с контейнерами multiset и multimap, 309

поиск объектов в множестве, 306

поиск подстроки, 273

поиск элемента отображения, 298

find_first_of(), обобщенный алгоритм

нахождение знаков препинания, 280

нахождение первого символа в строке, 273

find_last_ of(), 279

find_last_not_of(), 279

for, инструкция, 209–12

использование с инструкцией if, 196

front(), функция

поддержка очереди, 316

front_inserter(), адаптор функции

использование в операции push_front(), 577

fstream, класс

файловый ввод / вывод, 1042

full(), функция

модификация алгоритма динамического роста стека, 317

functional, заголовочный файл, 568

G

get(), функция, 1063–66

getline(), функция, 270, 1066–68

goto, инструкция, 219–22

greater, объект-функция, 571

greater_equal, объект-функция, 571

I

i?enaaeaaiea

почленное для объектов класса, 925–29

i?iecaiaiua eeannu

ae?ooaeuiua ooieoee, 899–925

определение

при одиночном наследовании, 876–78

присваивание

оператор

перегруженный, 925–29

if, инструкция, 192–98

If, инструкция

условный оператор как альтернатива, 158

insert(), функция

вставка символов в строку, 286

добавление элементов в множество, 305

реализация, 266

списки, 222

inserter(), адаптор функции

для вставки с помощью insert(), 577

inserter, класс, 305

Iomanip, заголовочный файл, 136

iostream библиотека

iostream.h, заголовочный файл, пример использования, 563

ввод

istream_iterator, 579

итератор чтения, 582

вывод

ostream_iterator, 580–82

итератор записи, 582

итератор чтения, 582

итераторы, 578–82

манипуляторы

endl, 27

операторы, сцепление, 28–29

iostream.h, заголовочный файл

пример использования для манипуляций с текстом, 563

isalpha(), функция, 206

ctype, заголовочный файл, 283

isdigit(), функция

ctype, заголовочный файл, 283

ispunct(), функция

ctype, заголовочный файл, 283

isspace(), функция

ctype, заголовочный файл, 283

istream_iterator, 579–80

iterator, заголовочный файл, 578

L

less, объект-функция, 572

less_equal, объект-функция, 572

limits, заголовочный файл, 145

list, заголовочный файл, 256

locale, заголовочный файл, 283

l-значение, 81

как возвращаемое значение, подводные камни, 348

оператор присваивания, требования, 149

преобразования, 447

преобразование точного соответствия, 445

точное соответствие при разрешении перегрузки функций, 457

трансформация, 450, 469

преобразование аргументов шаблона функции, 486

M

main(), 15

обработка аргументов в командной строке, 356–65

map, заголовочный файл, 293

использование с контейнером multimap, 309

memory, заголовочный файл, 395

merge(), обобщенный алгоритм

специализированная версия для спискаов, 588

minus(), объект-функция, 570

modulus, объект-функция, 571

multimap (мультиотображение), контейнер, 309–12

map, заголовочный файл, 310

сравнение с отображением, 303

multiplies, объект-функция, 570

multiset (мультимножество), контейнер, 309–12

set, заголовочный файл, 310

N

negate, объект-функция, 571

new оператор, 162–63

для константных объектов, 403–4

для массивов, 400–402

классов, 749–51

для объектов классов, 745

для одиночных объектов, 392–95

использование класса распределителя памяти (сноска), 256

оператор размещения new, 403–4

для объектов класса, 751–53

спецификации

исключений, 546–50

и указат??и на функции, 548–50

статические члены класса, 621–27

данные-члены, 621–27

функции-члены, 626–27

not_equal_to, объект-функция

(код), 571

not1(), адаптор функции

как адаптор-отрицатель, 573

not2(), адаптор функции

как адаптор-отрицатель, 573

numeric, заголовочный файл, 584

использование численных обобщенных алгоритмов, 586

O

oaaeiiu eeannia

конкретизация, 800–811

члены

шаблонов, 826–31

ofstream, тип, 1076–86

фун??ии-члены

volatile, 611–14

функции-члены

константные, 611–14

ostream_iterator, 580–82

P

pair, класс, 127

использование для возврата нескольких значений, 197

plus, объект-функция, 568, 570

pop_back(), функция

для удаления элементов из последовательного контейнера, 267

использование для реализации динамического роста стека, 317

push_back(), функция

векторы, вставка элементов, 123

поддержка в контейнерах, 257

стеки, использования для динамического выделения памяти, 317

push_front(), функция

поддержка в списковых контейнерах, 257

pаголовочные файлы

содержимое

объявления функций, с включением явной спецификации исключений, 546

Q

queue, заголовочный файл, 315

R

register, ключевое слово, 389–90

reinterpret_cast, оператор

опасности, 181

reinterpret_cast, оператор, 181

release()б функция

управление объектами с помощью класса auto_ptr, 400

reserve(), функция

использование для установки емкости контейнера, 255

reset(), функция

в классе bitset, 167

установка указателя auto_ptr, 398

resize(), функция

использование для изменения размера контейнера, 258

return, инструкция

завершение функции с помощью, 346

неявное преобразование типа в, 176

сравнение с выражением throw, 531

r-значение, 81

использование при вычислении выражений, 141

S

set, заголовочный файл, 304, 310

size(), функция

для модификации алгоритма выделения памяти в стеке, 317

sizeof, оператор, 159–62

использование с типом ссылки, 161

использование с типом указателя, 161

как константное выражение, 162

sort(), обобщенный алгоритм

вызов, 120

передача объекта=функции в качестве аргумента, 569

stack, заголовочный файл, 312

static_cast

сравнение с неявным преобразованием, 180

static_cast, оператор

опасности, 181

std, пространство имен, 426–28

string, заголовочный файл, 67

string, строковый тип, 95–98

substr(), функция, 275

пустая строка, 96

смешение объектов типа string и C-строк, 97

switch, инструкция, 207

использование ключевого слова case, 202

использование ключевого слова default, 202, 205

T

terminate(), функция, 541

this, указатель, 616–20

tolower(), функция

locale, заголовочный файл, 283

преобразование заглавных букв в строчные, 283

toupper(), функция

ctype, заголовочный файл, 283

locale, заголовочный файл, 283

true, ключевое слово, 108

typedef

для объявления указателя на функцию, 372

для улучшения читабельности, 295, 369

как синоним существующего имени типа, 431

массива указателей на функции, 369

typename, 242

использование с параметрами шаблона функции, 480

U

unexpected(), функция

для обработки нераспознанных исключений, 547

unique(), обобщенный алгоритм

удаление дубликатов из вектора, 557

unique_copy(), обобщенный алгоритм

запись целых чисел из вектора в стандартный вывод, 579

using-директивы, 423–26

влияние на разрешение перегрузки функции, 463

для объявления перегруженных функций, 437–38

сравнение с using-объявлениями, 423–26

using-объявления, 422–23

влияние на разрешение перегрузки функции, 462

для объявления перегруженных функций, 434–36

сравнение с using-директивами, 423–26

utility, заголовочный файл, 127

V

vector, заголовочный файл, 70, 121, 256

void

в списке параметров функции, 325

указатель, 179

void*

преобразование в void* как стандартное преобразование, 456

volatile, квалификатор, 127

для типа параметра, в связи с перегрузкой функций, 432

для функции-члена, 611–14

использование преобразования квалификаторов, 471

преобразование

квалификаторов, 449

W

while, инструкция, 213–16

сравнение с инструкциями for и do-while, 209

А

абстракция

объекта, класс комплексных чисел как пример, 154

стандартная библиотека, преимущества использования, 165

автоматические объекты, 388–90

объявление с ключевым словом register, 389–90

особенности хранения, 388

адапторы

функций, для объектов-функций, 573

адапторы функций, 573

адрес(а)

как значение указателя, 88

конкретизированных шаблонов функций, 484

алгоритм(ы)

функция

выведение аргумента шаблона, 489

разрешение перегрузки, 511

шаблон как, 475

аргумент(ы), 321

передача, 345

использование указателей для, 87

передача по значению, 327

по умолчанию, 340–43

должны быть хвостовыми, 341

и виртуальные функции, 913

и устоявшие функции, 472–73

тип

преобразования, разрешение перегрузки функции, 444–60

преобразования, расширение типа, 451–53

преобразования, ссылок, 457–59

преобразования, стандартные, 453–57

шаблона класса

для параметров-констант, 805–9

для параметров-типов, 800–811

шаблонов функции

явные, 490–93

шаблонов функций

выведение аргументов, 485–90

явная спецификация, мотивировка, 492

явная спецификация, недостатки, 492

явное специфицирование, 490

арифметические

исключения, 143

объекты-функции, 570

операторы, 142–45

таблица, 142

операции, поддержка для комплексных чисел, 126

преобразования, 175, 142–45

bool в int, 109

неявное выполнение при вычислении выражений, 175

типов, расширение типа перечисления, 112

указатели, 90

ассоциативность

операторов, влияние на вычисление выражений, 171–74

порядок вычисления подвыражений, 142

ассоциативные контейнеры, 248–301

неприменимость обобщенных алгоритмов переупорядочения, 587

ассоциирование

значений, использование класса pair, 127

Б

базовые классы

абстрактные базовые классы, 865–69, 908

видимость классов

при виртуальном наследовании, 983–84

видимость членов

при множественном наследовании, 968–71

при одиночном наследовании, 966–68

виртуальные базовые классы, 974–87

деструкторы, 896–99

доступ

к базовым классам, 958–64

к закрытым базовым классам, 963

к защищенным членам, 871

к членам, 880–88

доступ к элементам отображения с помощью, 299

конструирование

виртуальное наследование, 974–82

множественное наследование, 950–51

одиночное наследование, 889–96

почленная инициализация, 925–27

конструкторы, 889–99

определение базового класса

при виртуальном наследовании, 976–78

при множественном наследовании, 950–55

при одиночном наследовании, 871–75

преобразование к базовому классу, 865–69

при выведении аргументов шаблона функции, 487

присваивание, почленное присваивание, 927–29

байты

запись с помощью put(), 1063

чтение с помощью get(), 1063–66

безопасное связывание, 384

перегруженных функций, 440

бесконечный

рекурсия, 351

цикл, избежание в операциях поиска в строке, 274

бинарные

операторы, 141

битовое поле

как средство экономии памяти, 643–45

битовый вектор, 164

в сравнении с классом bitset, 164

блок

try-блок, 533–37

инструкций, 188

комментария, 24

функции, 321

функциональный try-блок, 533–37

и конструкторы, 1024–26

больше (>), оператор

поддержка в арифметических типах данных, 30

булевский(е)

константы, операторы, дающие в результате, 146

стандартные преобразования при разрешении перегрузки функции, 453

тип bool, 108–10

В

вектор(ы)

find(), обобщенный алгоритм, 554

емкость, связь с размером, 258

идиоматическое употребление в STL, 123

объектов класса, 689–96

присваивание, сравнение со встроенными массивами, 122

сравнение со списками, 251–52

требования к вставке и доступу, 252

увеличение размера, 253–56

вертикальная табуляция ()

как escape-последовательность, 77

взятия адреса (&) оператор

использование в определении ссылки, 104, 105

использование с именем функции, 367

как унарный оператор, 141

взятия индекса оператор ([]), 736

использование в векторах, 121

использование в классе bitset, 168

использование в отображениях, 294

отсутствие поддержки в контейнерах multimap и multiset, 312

взятия остатка, оператор (%), 142

видимость

определения символической константы, 386

переменных в условии цикла, 211, 379–81

роль в выборе функции-кандидата при разрешении перегрузки функции, 460

требование к встроенным функциям, 353, 387

членов класса, 607, 645–52

висячий

проблемы висячего else, описание и устранение, 195

указатель, 389

как проблема динамически выделенного объекта, 394

возврат каретки (\\r)

как escape-последовательность, 77

время жизни, 381

auto_ptr, влияние на динамически выделенные объекты, 395

автоматических объектов, 388

динамически выделенных объектов, 392

сравнение с указателями на них, 394

и область видимости (глава), 376–428

локальных объектов

автоматических и статических, 388

влияние раскрутки стека на объекты типа класса, 541

проблема возврата ссылки на локальный объект, 348

вставка элементов

в вектор, 123

в контейнер, с помощью адапторов функций, 577

в контейнеры multimap и multiset, 311

в отображение, 294

в последовательные контейнеры, 265

в стек, 314

использование push_back(), 257

итераторы, обозначение диапазона, 575–77

различные механизмы для разных типов контейнеров, 252

встроенные функции, 133, 322

объекты-функции, 559, 566

объявление, 352–53

шаблонов функций как, 481

определение, размещение в заголовочном файле, 385

перегруженные операторы вызова, 559

преимущества, 352

сравнение с не-встроенными функциями-членами, 605–7

встроенный(е)

массивы

запрет иниициализации другим массивом, 115

запрет использования в качестве возвращаемого значения функции, 324

запрет присваивания другому массиву, 324

запрет ссылаться на, 115

инициализация при выделении из хипа, 400

отсутствие поддержки операции erase(), 557

поддержка в обобщенных алгоритмах, 553

сравнение с векторами, 122

типы данных

арифметические, 30–33

выполнение

непоследовательные инструкции, 20

условное, 20

выражения

(глава), 141–87

использование аргументов по умолчанию, 342

порядок вычисления подвыражений, 142

разрешение имен, 377

вычисление

логических операторов, 146

порядок вычисления подвыражений, 142

вычитание

minus, объект-функция, 570

комплексных чисел, 154

Г

глобальное пространство имен

проблема засорения, 66, 406

глобальные объекты

и функции, 381–87

сравнение с параметрами и возвращаемыми значениями функций, 349–50

глобальные функции, 381

горизонтальная табуляция (\\t)

как escape-последовательность, 77

Д

данные члены, 595–96

данные-члены

битовые поля, 643–45

изменчивые (mutable), 614–16

статические, 621–28

в шаблонах классов, 821–24

указатель this, 616–21

члены базового и производного классов, 870–79

двойная кавычка (\\ ")

как escape-последовательность, 77

двойная обратная косая черта (\\)

как escape-последовательность, 77

двунаправленный итератор, 583

декремента оператор (--)

встроенный, 153–54

перегруженный, 740–44

постфиксная форма, 153, 743

префиксная форма, 153, 742

деление

комплексных чисел, 155

целочисленное, 143

деления по модулю оператор (%), 142

деструктор(ы), 682–89

для элементов массива, 690

динамическое выделение памяти

для массива, 162, 400–402

исчерпание памяти, исключение bad_alloc, 393

как требование к динамически растущему вектору, 253

объектов, 392–406

управление с помощью класса auto_ptr, 395

динамическое освобождение памяти

для массивов, 400–402

объектов, 392–406

константных, 402–3

одиночных объектов, 392–95

оператор delete, 134, 392, 394, 744–53

управление с помощью класса auto_ptr, 395

утечка памяти, 395

директивы, 21–24

директивы связывания, 353–55

в связи с перегрузкой, 438

использование с указателями на функции, 373

для элементов массива

динамическое выделение памяти, 691–94

доступ

к контейнеру

использование итератора для, 261

последовательный доступ как критерий выбора типа, 252

к массиву, 31

индекс, 45

индексирование, 113

к пространству имен

механизмы, компромиссные решения, 68

к членам, 598–99, 607–8

оператор доступа к членам ->, 740

произвольный, итератор с произвольным доступом, 583

уровни, protected, 49

друзья, 730–33

и специальные права доступа, 137, 599–600

перегруженные операторы, 730–33

См. также доступ, класс(ы), наследование, 815–21

Е

емкость контейнерных типов

в сравнении с размером, 253

начальная, связь с размером, 258

З

забой (, 77

заголовочные файлы

как средство повторного использования объявлений функций, 323

по имени

algorithm, 72, 584

bitset, 167

complex, 125

fstream, 1042

functional, 568

iomanip, 136

iterator, 578

limits, 145

locale, 283

map, 293

memory, 395

numeric, 584, 586

queue, 315

set, 304

sstream, 1044

stack, 312

string, 68

vector, 70, 121, 256

предкомпилированные, 385

содержимое

включение определения шаблона функции, преимущества и недостатки, 495

встроенные функции, 353

директивы связывания, 354

объявления, 82, 385–87

объявления явных специализаций шаблонов, 503

спецификация аргументов по умолчанию, 341

запись активации, 327

автоматическое включение объектов в, 388

запятая (,)

неправильное использование для индексации массива, 117

оператор, 163

звонок ()

как escape-последовательность, 77

знак вопроса ()

как escape-последовательность, 77

И

И, оператор, 142

идентификатор, 83

использования в качестве спецификатора типа класса, 129

как часть определения массива, 113

соглашения по именованию, 83

иерархии

определение, 862–69

идентификация членов, 870–80

исключений, в стандартной библиотеке C++, 1026–29

поддержка мезанизма классов, 128

изменчивый (mutable) член, 614–16

именование

соглашения об именовании идентификаторов, 83

имя, 83

typedef, как синоним, 126–27

именование членов класса, 607–8

квалифицированные имена, 410–12

статических членов класса, 622–23

членов вложенных пространств имен, 412–14

шаблонов функций как членов пространства имен, 524

область видимости объявления, 376

параметра шаблона

функции, 478

перегруженные операторы, 727–28

переменной, 83

псевдонимы пространства имен, как альтернативные имена, 420–21

разрешение, 377

в локальной области видимости, 379

в области видимости класса, 649–52

в определении шаблона функции, 514–20

инициализация

векторов, 121

сравнение с инициализацией встроенных массивов, 122

комплексного числа, 154

массива

динамически выделенного, 400

динамически выделенных объектов классов, 749

многомерного, 116

указателей на функции, 369

недопустимость инициализации другим массивом, 115

объектов

автоматических, 388

автоматических, по сравнению с локальными статическими, 391

глобальных, инициализация по умолчанию, 382

динамически выделенных, 393

константных, 101

статических локальных, 390, 391

поведение auto_ptr, 397

сравнение с присваиванием, 148

ссылок, 104

указателя на функцию, 367

влияние на спецификацию исключений, 549

вопросы, связанные с перегруженными функциями, 439

инкремента оператор (++)

встроенный, 154

перегруженный, 740–44

постфиксная форма, 153, 743

префиксная форма, 153, 742

инструкции, 188–98

break

для выхода из инструкции switch, 203

break, инструкция, 218–19

continue, 219

do-while, 216–17

сравнение с инструкциями for и while, 209

for, 209–13

goto, 219–21

if, 20, 192–98

if-else, условный оператор как альтернатива, 158

switch, 201–3

использование ключевого слова default, 202, 205

while, 213–16

сравнение с инструкциями for и do-while, 209

блок, 188

объявления, 189–92

простые, 188–89

составные, 188–89

инструкция

while, 21

использование преобразования квалификаторов, 449

использование шаблонов, 62

итератор с произвольным доступом, 583

итератор(ы), 123, 261

begin(), доступ к элементам контейнера, 261

end(), доступ к элементам контейнера, 261

iterator, заголовочный файл, 578

абстракция, использование а обобщенных алгоритмах для обхода, 552

адаптор, 557

вставка элементов в последовательные контейнеры, 266

доступ к подмножеству контейнера с помощью, 262

использование в обобщенных алгоритмах, 575–83

категории, 582–83

двунаправленный итератор, 583

итератор записи, 582

итератор с произвольным доступом, 583

итератор чтения, 582

однонаправленный итератор, 583

обозначение интервала с включенной левой границей, 583

обратные итераторы, 578

потоковык итераторы ввода/вывода, 578–82

istream_iterator, 579–80

ostream_iterator, 580–82

запись целых чисел из вектора в стандартный вывод, 578

чтение целых чисел из стандартного ввода в вектор, 579

требования к поведению, выдвигаемые обобщенными алгоритмами, 584

удаление элементов из последовательного контейнера, 267

К

китайский язык

поддержка двухбайтовых символьных литералов, 77

класс(ы)

возвращаемые значения, 347–49

вопросы эффективности, 712–18

друзья, 599–600, 731

заголовок, 594

объединение, 638–43

объявление, сравнение с определением класса, 600–601

определение, 594–601

сравнение с объявлением класса, 600–601

параметры

вопросы эффективности, 330, 712–18

для возврата сразу нескольких значений, 350

для передачи сразу нескольких параметров, 350

тело, 594

командная строка

класс, 363–65

опции, 356–65

argc, argv - аргументы main(), 356

использование встроенного массива для обработки, 356

пример программы, 361–63

комментарии, 24–26

блочные, 25

комплексные числа, 18, 125–26

выражения с участием, 155

заголовочный файл complex, 125

как абстракция класса, 30

операции, 154–58

представление, 156

типы данных, 30

композиция

объектов, 963–65

сравнение с наследованием, 960–62

конкретизация

шаблона функции, 482

явное объявление специализации

шаблона функции, 497–98

Конкретизация

шаблона функции

разрешение перегрузки, 506–13

конктеризация

точка конкретизации, 518

константы

константные выражения

sizeof() как пример, 162

размер массива должен быть, 113

литерал, 76–78

подстановка, 386

преобразование объектов в, 101

ссылки, рассматриваемые как, 104

конструктор(ы)

вызовы виртуальных функций в, 923–25

для базовых классов, 899

почленная инициализация, 925–30

при виртуальном наследовании, 974–82

при единичном наследовании, 896

при множественном наследовании, 950–51

для элементов массива

список инициализации массива, 689–91

и функциональные try-блоки, 1024–26

как коверторы, 761–64

конструкторы по умолчанию, 678–79

для элементов вектора, 694–96

копирующие конструкторы, 237, 680–82

почленная инициализация, 703–9, 925–30

ограничение возможности созданий объектов, 680

список инициализации членов, 696–703

контейнерные типы

определение, 256–61

контейнерные типы, 248–301

вопросы выделения памяти при копировании, 577

емкость, 253

связь с размером, 253–58

и итераторы, 261–65

инициализация, с помощью пары итераторов, 263

очереди с приоритетами, 315

параметры, 338–40, 350

преимущества, автоматическое управление памятью, 402

размер, 258

связь с емкостью, 253–56

требования к типам, с которыми конкретизируется контейнер, 259

копирование

вопросы выделения памяти, 577

использование ссылок для избежания, 330

как операция инициализации, 258

массивов, 115

сравнение со стоимостью произвольного доступа, 252

строк, 96

копирующий

конструктор, 43, 131

для динамического увеличения размера вектора, 255

оператор присваивания, реализация, 237

Л

лексикографическое упорядочение, 289

в обобщенных алгоритмах перестановок, 586

в обобщенныых алгоритмах сравнения, 586

при сортировке строк, 366–75

литеральные константы, 76–78

C-строки

сравнение с символьными литералами, 114

f суффикс, 77

U суффикс, 76

с плавающей точкой, 77

логические встроенные операторы, 145–48

оператор ИЛИ (||), 146

оператор НЕ (!), 147

логические объекты-функции

logical_and, 572

logical_not, 572

logical_or, 572

локализация

влияние глобального объекта на, 349

константной переменной или объекта, 100

локальность объявления, 190, 385

на уровне файла, использование безымянного пространства имен, 419

локальная область видимости, 376, 378–81

try-блок, 535

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.