<< Пред. стр. 104 (из 121) След. >>
Список литературы по разделу
*noshowpos Не печатать + для неотрицательных чисел
Манипулятор Назначение
*skipws Пропускать пробельные символы в операторах ввода
noskipws Не пропускать пробельные символы в операторах ввода
uppercase Печатать 0X при выводе в шестнадцатеричной системе счисления; E – при выводе в научной нотации
*nouppercase Печатать 0x при выводе в шестнадцатеричной системе счисления; e – при выводе в научной нотации
*dec Печатать в десятичной системе
hex Печатать в шестнадцатеричной системе
oct Печатать в восьмеричной системе
left Добавлять символ заполнения справа от значения
right Добавлять символ заполнения слева от значения
internal Добавлять символ заполнения между знаком и значением
*fixed Отображать число с плавающей точкой в десятичной нотации
scientific Отображать число с плавающей точкой в научной нотации
flush Сбросить буфер ostream
ends Вставить нулевой символ, затем сбросить буфер ostream
endl Вставить символ новой строки, затем сбросить буфер ostream
ws Пропускать пробельные символы
// для этих манипуляторов требуется #include
setfill( ch) Заполнять пустое место символом ch
Setprecision( n ) Установить точность вывода числа с плавающей точкой равной n
setw( w ) Установить ширину поля ввода или вывода равной w
setbase( b ) Выводить целые числа по основанию b
* обозначает состояние потока по умолчанию
20.10. Сильно типизированная библиотека
Библиотека iostream сильно типизирована. Например, попытка прочитать из объекта класса ostream или записать в объект класса istream помечается компилятором как нарушение типизации. Так, если имеется набор объявлений:
#include
#include
class Screen;
extern istream& operator>>( istream&, const Screen& );
extern void print( ostream& );
ifstream inFile;
то следующие две инструкции приводят к нарушению типизации, обнаруживаемому во время компиляции:
int main()
{
Screen myScreen;
// ошибка: ожидается ostream&
print( cin >> myScreen );
// ошибка: ожидается оператор >>
inFile << "ошибка: оператор вывода";
Средства ввода/вывода включены в состав стандартной библиотеки C++. В главе 20 библиотека iostream описана не полностью, в частности вопрос о создании определенных пользователем манипуляторов и буферных классов остался за рамками введения в язык. Мы сосредоточили внимание лишь на той части библиотеки iostream, которая имеет основополагающее значение для программного ввода/вывода.
Приложение
21. Обобщенные алгоритмы в алфавитном порядке
В этом приложении мы рассмотрим все алгоритмы. Мы решили расположить их в алфавитном порядке (за небольшими исключениями), чтобы проще было найти нужный. Каждый алгоритм представлен в следующем виде: сначала описывается прототип функции, затем сам алгоритм, причем особое внимание уделяется интуитивно неочевидным особенностям, и, наконец, приводится пример программы, показывающий, как можно данный алгоритм использовать.
Первыми двумя аргументами всех обобщенных алгоритмов (естественно, не без исключений) является пара итераторов, обычно first и last, обозначающих диапазон элементов внутри контейнера или встроенного массива, над которым работает алгоритм. Этот диапазон (часто называемый интервалом с включенной левой границей), как правило, записывается в виде:
// следует читать: включая first и все последующие
// элементы до last, но не включая сам last
[ first, last )
Это означает, что диапазон начинается с first и заканчивается last, однако сам элемент last не включается. Если
first == last
то говорят, что диапазон пуст.
К паре итераторов предъявляется такое требование: last должен быть достижим, если начать с first и последовательно применять оператор инкремента. Однако компилятор не может проверить выполнение данного ограничения. Если требование не будет выполнено, поведение программы не определено; обычно это заканчивается ее крахом и дампом памяти.
В объявлении каждого алгоритма подразумевается минимальная поддержка, которую должны обеспечить итераторы (краткое обсуждение пяти категорий итераторов см. в разделе 12.4). Например, алгоритм find(), реализующий однопроходный обход контейнера и выполняющий только чтение, требует итератора чтения InputIterator. Ему также можно передать одно- или двунаправленный итератор или итератор с произвольным доступом. Однако передача итератора записи приведет к ошибке. Не гарантируется, что подобные ошибки (при передаче итератора неподходящей категории) будут обнаружены компилятором, поскольку категории итераторов – это не сами типы, а лишь параметры, которыми конкретизируется шаблон функции.
Некоторые алгоритмы существуют в нескольких вариантах: в одном используется тот или иной встроенный оператор, а в другом – объект-функция или указатель на функцию, реализующие альтернативу этому оператору. Например, алгоритм unique() по умолчанию сравнивает соседние элементы контейнера с помощью оператора равенства, определенного в классе, к которому данные элементы принадлежат. Но если в этом классе нет оператора равенства или мы хотим сравнивать элементы иным способом, то можем передать объект-функцию или указатель на функцию, поддерживающую нужную семантику. Есть и такие алгоритмы, которые выполняют похожие действия, но имеют различные имена. Так, имена предикатных версий алгоритмов всегда заканчиваются на _if, скажем find_if(). Например, есть вариант алгоритма replace(), где используется встроенный оператор равенства, и вариант с именем replace_if(), которому передается предикатный объект-функция или указатель на функцию-предикат.
Алгоритмы, модифицирующие контейнер, обычно также существуют в двух вариантах: один осуществляет модификацию по месту, а второй возвращает копию с внесенными изменениями. Так, есть алгоритмы replace() и replace_copy(). Однако вариант с копированием (его имя всегда содержит слово _copy) имеется не для каждого алгоритма, модифицирующего контейнер. К примеру, для алгоритмов sort() его нет. В таких случаях, если нужно, чтобы алгоритм работал с копией, мы должны создать ее самостоятельно и передать в качестве аргумента.
Для использования любого обобщенного алгоритма в программу необходимо включить заголовочный файл
#include
Для употребления любого из четырех численных алгоритмов: adjacent_difference(), accumulate(), inner_product() и partial_sum() – нужно включить также файл
#include
Приведенные в этом Приложении примеры программ, в которых используются алгоритмы и различные контейнерные типы, отражают существующую на момент написания книги реализацию. Применение библиотеки ввода/вывода iostream следует соглашениям, установленным до принятия стандарта; скажем, в программу включается заголовочный файл iostream.h, а не iostream. Шаблоны не поддерживают аргументы по умолчанию. Чтобы программа работала на системе, имеющейся у вас, возможно, придется изменить некоторые объявления.
Другое, более подробное, чем в этой книге, описание обобщенных алгоритмов можно найти в работе [MUSSER96], правда, оно несколько отстает от окончательного варианта стандартной библиотеки C++.
Алгоритм accumulate()
template < class InputIterator, class Type >
Type accumulate(
InputIterator first, InputIterator last,
Type init );
template < class InputIterator, class Type,
class BinaryOperation >
Type accumulate(
InputIterator first, InputIterator last,
Type init, BinaryOperation op );
Первый вариант accumulate() вычисляет сумму значений элементов последовательности из диапазона, ограниченного парой итераторов [first,last), с начальным значением, которое задано параметром init. Например, если дана последовательность {1,1,2,3,5,8} и начальное значение 0, то результатом работы алгоритма будет 20. Во втором варианте вместо оператора сложения к элементам применяется переданная бинарная операция. Если бы мы передали алгоритму accumulate() объект-функцию times и начальное значение 1, то получили бы результат 240. accumulate() – это один из численных алгоритмов; для его использования в программу необходимо включить заголовочный файл .
#include
#include
#include
#include
/*
* выход:
* accumulate()
* работает с последовательностью {1,2,3,4}
* результат для сложения по умолчанию: 10
* результат для объекта-функции plus: 10
*/
int main()
{
int ia[] = { 1, 2, 3, 4 };
list ilist( ia, ia+4 );
int ia_result = accumulate(&ia[0], &ia[4], 0);
int ilist_res = accumulate(
ilist.begin(), ilist.end(), 0, plus() );
cout << "accumulate()\n\t"
<< "работает с последовательностью {1,2,3,4}\n\t"
<< "результат для сложения по умолчанию: "
<< ia_result << "\n\t"
<< "результат для объекта-функции plus: "
<< ilist_res
<< endl;
return 0;
}
Алгоритм adjacent_difference()
template < class InputIterator, class OutputIterator >
OutputIterator adjacent_difference(
InputIterator first, InputIterator last,
OutputIterator result );
template < class InputIterator, class OutputIterator >
class BinaryOperation >
OutputIterator adjacent_difference(
InputIterator first, InputIterator last,
OutputIterator result, BinaryOperation op );
Первый вариант adjacent_difference() создает новую последовательность, в которой значение каждого элемента, кроме первого, равно разности между текущим и предыдущим элементами исходной последовательности. Например, если дано {0,1,1,2,3,5,8}, то первым элементом новой последовательности будет копия: 0. Вторым – разность первых двух элементов исходной последовательности: 1. Третий элемент равен разности третьего и второго элементов: 1?1=0, и т.д. В результате мы получим последовательность {0,1,0,1,1,2,3}.
Во втором варианте разность соседних элементов вычисляется с помощью указанной бинарной операции. Возьмем ту же исходную последовательность и передадим объект-функцию times. Как и раньше, первый элемент просто копируется. Второй элемент – это произведение первого и второго элементов исходной последовательности; он тоже равен 0. Третий элемент – произведение второго и третьего элементов исходной последовательности: 1 * 1 = 1, и т.д. Результат – {0,1,2,6,15,40}.
В обоих вариантах итератор OutputIterator указывает на элемент, расположенный за последним элементом новой последовательности. adjacent_difference() – это один из численных алгоритмов, для его использования в программу необходимо включить заголовочный файл .
#include
#include
#include
#include
#include
int main()
{
int ia[] = { 1, 1, 2, 3, 5, 8 };
list ilist(ia, ia+6);
list ilist_result(ilist.size());
adjacent_difference(ilist.begin(), ilist.end(),
ilist_result.begin() );
// на выходе печатается:
// 1 0 1 1 2 3
copy( ilist_result.begin(), ilist_result.end(),
ostream_iterator(cout," "));
cout << endl;
adjacent_difference(ilist.begin(), ilist.end(),
ilist_result.begin(), times() );
// на выходе печатается:
// 1 1 2 6 15 40
copy( ilist_result.begin(), ilist_result.end(),
ostream_iterator(cout," "));
cout << endl;
}
Алгоритм adjacent_find()
template < class ForwardIterator >
ForwardIterator
adjacent_find( ForwardIterator first, ForwardIterator last );
template < class ForwardIterator, class BinaryPredicate >
ForwardIterator
adjacent_find( ForwardIterator first,
ForwardIterator last, Predicate pred );
adjacent_find() ищет первую пару одинаковых соседних элементов в диапазоне, ограниченном итераторами [first,last). Если соседние дубликаты найдены, то алгоритм возвращает однонаправленный итератор, указывающий на первый элемент пары, в противном случае возвращается last. Например, если дана последовательность {0,1,1,2,2,4}, то будет найдена пара [1,1] и возвращен итератор, указывающий на первую единицу.
#include
#include
#include
#include
class TwiceOver {
public:
bool operator() ( int val1, int val2 )
{ return val1 == val2/2 ? true : false; }
};
int main()
{
int ia[] = { 1, 4, 4, 8 };
vector< int, allocator > vec( ia, ia+4 );
int *piter;
vector< int, allocator >::iterator iter;
// piter указывает на ia[1]
piter = adjacent_find( ia, ia+4 );
assert( *piter == ia[ 1 ] );
// iter указывает на vec[2]
iter = adjacent_find( vec.begin(), vec.end(), TwiceOver() );
assert( *iter == vec[ 2 ] );
// пришли сюда: все хорошо
cout << "ok: adjacent-find() завершился успешно!\n";
return 0;
}
Алгоритм binary_search()
template < class ForwardIterator, class Type >
bool
binary_search( ForwardIterator first,
ForwardIterator last, const Type &value );
template < class ForwardIterator, class Type >
bool
binary_search( ForwardIterator first,
ForwardIterator last, const Type &value,
Compare comp );
binary_search() ищет значение value в отсортированной последовательности, ограниченной парой итераторов [first,last). Если это значение найдено, возвращается true, иначе – false. В первом варианте предполагается, что контейнер отсортирован с помощью оператора “меньше”. Во втором варианте порядок определяется указанным объектом-функцией.
#include
#include
#include
int main()
{
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
vector< int, allocator > vec( ia, ia+12 );
sort( &ia[0], &ia[12] );
bool found_it = binary_search( &ia[0], &ia[12], 18 );
assert( found_it == false );
vector< int > vec( ia, ia+12 );
sort( vec.begin(), vec.end(), greater() );
found_it = binary_search( vec.begin(), vec.end(),
26, greater() );
assert( found_it == true );
}
Алгоритм copy()
template < class InputIterator, class OutputIterator >
OutputIterator
copy( InputIterator first1, InputIterator last,
OutputIterator first2 )
copy() копирует последовательность элементов, ограниченную парой итераторов [first,last), в другой контейнер, начиная с позиции, на которую указывает first2. Алгоритм возвращает итератор, указывающий на элемент второго контейнера, следующий за последним вставленным. Например, если дана последовательность {0,1,2,3,4,5}, мы можем сдвинуть элементы на один влево с помощью такого вызова:
int ia[] = {0, 1, 2, 3, 4, 5 };
// сдвинуть элементы влево на один, получится {1,2,3,4,5,5}
copy( ia+1, ia+6, ia );
copy() начинает копирование со второго элемента ia, копируя 1 в первую позицию, и так далее, пока каждый элемент не окажется в позиции на одну левее исходной.
#include
#include
#include
#include
/* печатается:
0 1 1 3 5 8 13
сдвиг массива влево на 1:
1 1 3 5 8 13 13
сдвиг вектора влево на 2:
1 3 5 8 13 8 13
*/
int main()
{
int ia[] = { 0, 1, 1, 3, 5, 8, 13 };
vector< int, allocator > vec( ia, ia+7 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность элементов:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
// сдвиг влево на один элемент
copy( ia+1, ia+7, ia );
cout << "сдвиг массива влево на 1:\n";
copy( ia, ia+7, ofile ); cout << '\n';
// сдвиг влево на два элемента
copy( vec.begin()+2, vec.end(), vec.begin() );
cout << "сдвиг вектора влево на 2:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм copy_backward()
template < class BidirectionalIterator1,
class BidirectionalIterator2 >
BidirectionalIterator2
copy_backward( BidirectionalIterator1 first,
BidirectionalIterator1 last1,
BidirectionalIterator2 last2 )
copy_backward() ведет себя так же, как copy(), только элементы копируются в обратном порядке: копирование начинается с last1-1 и продолжается до first. Кроме того, элементы помещаются в целевой контейнер с конца, от позиции last2-1, пока не будет скопировано last1-first элементов.
Например, если дана последовательность {0,1,2,3,4,5}, мы можем скопировать последние три элемента (3,4,5) на место первых трех (0,1,2), установив first равным адресу значения 0, last1 – адресу значения 3, а last2 – адресу значения 5. Тогда элемент 5 попадает на место элемента 2, элемент 4 – на место 1, а элемент 3 – на место 0. В результате получим последовательность {3,4,5,3,4,5}.
#include
#include
#include
#include
class print_elements {
public:
void operator()( string elem ) {
cout << elem
<< ( _line_cnt++%8 ? " " : "\n\t" );
}
static void reset_line_cnt() { _line_cnt = 1; }
private:
<< Пред. стр. 104 (из 121) След. >>
Список литературы по разделу