Программирование. Принципы и практика использования C++ Исправленное издание - Бьёрн Страуструп
Б.5.6. Кучи
Куча — это структура данных, в вершине которой находится элемент с наибольшим значением. Алгоритмы над кучами позволяют программистам работать с последовательностями произвольного доступа.
Куча позволяет быстро добавлять элементы и обеспечивает быстрый доступ к элементу с наибольшим значением. В основном кучи используются при реализации очередей с приоритетами.
Б.5.7. Перестановки
Перестановки используются для генерирования комбинаций элементов последовательности. Например, перестановками последовательности abc являются последовательности abc, acb, bac, bca, cab и cba.
Если последовательность [b:e] уже содержит последнюю перестановку (в данном примере это перестановка cba), то алгоритм next_permutation возвращает значение x, равное false; в таком случае алгоритм создает первую перестановку (в данном примере это перестановка abc). Если последовательность [b:e] уже содержит первую перестановку (в данном примере это перестановка abc), то алгоритм prev_permutation возвращает значение x, равное false; в таком случае алгоритм создает последнюю перестановку (в данном примере это перестановка cba).
Б.5.8. Функции min и max
Сравнение значений полезно во многих случаях.
Б.6. Утилиты библиотеки STL
В стандартной библиотеке есть несколько инструментов для облегчения использования стандартных библиотечных алгоритмов.
Б.6.1. Вставки
Запись результатов в контейнер с помощью итератора подразумевает, что элементы, на которые указывает итератор, можно перезаписать. Это открывает возможность для переполнения и последующего повреждения памяти. Рассмотрим следующий пример:
void f(vector<int>& vi)
{
fill_n(vi.begin(),200,7); // присваиваем 7 элементам
// vi[0]..[199]
}
Если вектор vi содержит меньше 200 элементов, то возникает опасность. В заголовке <iterator> стандартная библиотека предусматривает три итератора, позволяющих решить эту проблему с помощью добавления (вставки) элементов в контейнер, а не перезаписи его старых элементов. Для генерирования этих трех итераторов вставки используются три функции.
Для правильной работы алгоритма inserter(c,p) необходимо, чтобы итератор p был корректным итератором для контейнера c. Естественно, каждый раз при записи очередного элемента с помощью итератора вставки контейнер увеличивается на один элемент. При записи алгоритм вставки добавляет новый элемент в последовательность с помощью функции push_back(x), c.push_front() или insert(), а не перезаписывает существующий элемент. Рассмотрим следующий пример:
void g(vector<int>& vi)
{
fill_n(back_inserter(vi),200,7); // добавляет 200 семерок
// в конец vi
}
Б.6.2. Объекты-функции
Многие стандартные алгоритмы принимают в качестве аргументов объекты-функции (или функции), чтобы уточнить способ решения задачи. Обычно эти функции используются в качестве критериев сравнения, предикатов (функций, возвращающих значения типа bool) и арифметических операций. Несколько самых общих объектов-функций описано в заголовке <functional> стандартной библиотеки.
Рассмотрим следующий пример:
vector<int> v;
// ...
sort(v.begin(),v.end(),greater<int>()); // сортировка v в убывающем
// порядке
Обратите внимание на то, что предикаты logical_and и logical_or всегда вычисляют оба свои аргумента (в то время как операторы && и || — нет).
Б.6.3. Класс pair
В заголовке <utility> стандартная библиотека содержит несколько вспомогательных компонентов, включая класс pair.
template <class T1,class T2>
struct pair {
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(); // конструктор по умолчанию
pair(const T1& x,const T2& y);
// копирующие операции:
template<class U,class V> pair(const pair<U,V>& p);
};
template <class T1, class T2>
pair<T1,T2> make_pair(T1 x, T2 y) { return pair<T1,T2>(x,y); }
Функция make_pair() упрощает использование пар. Например, рассмотрим схему функции, возвращающей значение и индикатор ошибки.
pair<double,error_indicator> my_fct(double d)
{
errno = 0; // очищаем индикатор ошибок в стиле языка C
// выполняем много вычислений, связанных с переменной d,
// и вычисляем x
error_indicator ee = errno;
errno = 0; // очищаем индикатор ошибок в стиле языка C
return make_pair(x,ee);
}
Этот пример является полезной идиомой. Его можно использовать следующим образом:
pair<int,error_indicator> res = my_fct(123.456);
if (res.second==0) {
// используем res.first
}
else {
// Ой: ошибка
}
Б.7. Потоки ввода-вывода
Библиотека потоков ввода-вывода содержит средства форматированного и неформатированного буферизованного ввода-вывода текста и числовых значений.
Определения потоков ввода-вывода находятся в заголовках <istream>, <ostream> и т.п. (см. раздел Б.1.1).
Объект класса ostream преобразовывает объекты, имеющие тип, в поток символов (байтов).
Объект класса istream преобразовывает поток символов (байтов) в объекты, имеющие тип.
Объект класса iostream — это поток, который может действовать и как объект класса istream, и как объект класса ostream. Буфера, изображенные на диаграмме, являются потоковыми буферами (streambuf). Если читателям потребуется перейти от потоков класса iostream к новым видам устройств, файлов или памяти, они смогут найти их описание в профессиональных учебниках.
Существуют три стандартных потока.
Б.7.1. Иерархия потоков ввода-вывода
Поток istream можно связать с устройством ввода (например, клавиатурой), файлом или объектом класса string. Аналогично поток ostream можно связать с устройством вывода (например, текстовым окном), файлом или объектом класса string. Потоки ввода-вывода образуют иерархию классов.
Поток можно открыть либо с помощью конструктора, либо вызова функции open().
Для файловых потоков имя файлов представляет собой строку в стиле языка С.
Открыть файл можно в одном из режимов, приведенных
