Алгоритм replace_copy()
template< class InputIterator, class InputIterator,
class Type >
OutputIterator
replace_copy( InputIterator first, InputIterator last,
class OutputIterator result,
const Type& old_value, const Type& new_value );
replace_copy() ведет себя так же, как replace(), только новая последовательность копируется в контейнер, начиная с result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность:
Christopher Robin Mr. Winnie the Pooh Piglet Tigger Eeyore
последовательность после применения replace():
Christopher Robin Pooh Piglet Tigger Eeyore
*/
int main()
{
string oldval( "Mr. Winnie the Pooh" );
string newval( "Pooh" );
ostream_iterator< string > ofile( cout, " " );
string sa[] = {
"Christopher Robin", "Mr. Winnie the Pooh",
"Piglet", "Tigger", "Eeyore"
};
vector< string, allocator > vec( sa, sa+5 );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
replace( vec.begin(), vec.end(), oldval, newval );
cout << "последовательность после применения replace():\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
vector< string, allocator > vec2;
replace_copy( vec.begin(), vec.end(),
inserter( vec2, vec2.begin() ),
newval, oldval );
cout << "последовательность после применения replace_copy():\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм replace_copy_if()
template< class ForwardIterator, class OutputIterator,
class Predicate, class Type >
OutputIterator
replace_copy_if( ForwardIterator first, ForwardIterator last,
class OutputIterator result,
Predicate pred, const Type& new_value );
replace_copy_if() ведет себя так же, как replace_if(), только новая последовательность копируется в контейнер, начиная с result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.
#include <algorithm>
#include <vector>
#include <iostream.h>
/*
исходная последовательность:
0 1 1 2 3 5 8 13 21 34
последовательность после применения replace_if < 10 с заменой на 0:
0 0 0 0 0 0 0 13 21 34
последовательность после применения replace_if четное с заменой на 0:
0 1 1 0 3 5 0 13 21 0
*/
class EvenValue {
public:
bool operator()( int value ) {
return value % 2 ? false : true; }
};
int main()
{
int new_value = 0;
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 };
vector< int, allocator > vec( ia, ia+10 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( ia, ia+10, ofile ); cout << '\n';
replace_if( &ia[0], &ia[10],
bind2nd(less<int>(),10), new_value );
cout << "последовательность после применения replace_if < 10 "
<< "с заменой на 0:\n";
copy( ia, ia+10, ofile ); cout << '\n';
replace_if( vec.begin(), vec.end(),
EvenValue(), new_value );
cout << "последовательность после применения replace_if четное"
<< "с заменой на 0:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм replace_if()
template< class ForwardIterator, class Predicate, class Type >
void
replace_if( ForwardIterator first, ForwardIterator last,
Predicate pred, const Type& new_value );
replace_if() заменяет значения всех элементов в диапазоне [first,last), для которых предикат pred равен true, на new_value.
Алгоритм reverse()
template< class BidirectionalIterator >
void
reverse( BidirectionalIterator first,
BidirectionalIterator last );
reverse() меняет порядок элементов контейнера в диапазоне [first,last) на противоположный. Например, если есть последовательность {0,1,1,2,3}, то после обращения получится {3,2,1,1,0}.
Алгоритм reverse_copy()
template< class BidirectionalIterator, class OutputIterator >
OutputIterator
reverse_copy( BidirectionalIterator first,
BidirectionalIterator last, OutputIterator result );
reverse_copy() ведет себя так же, как reverse(), только новая последовательность копируется в контейнер, начиная с result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.
#include <algorithm>
#include <list>
#include <string>
#include <iostream.h>
/* печатается:
Исходная последовательность строк:
Signature of all things I am here to
read seaspawn and seawrack that rusty boot
Последовательность строк после применения reverse():
boot rusty that seawrack and seaspawn read to
here am I things all of Signature
*/
class print_elements {
public:
void operator()( string elem ) {
cout << elem
<< ( _line_cnt++%8 ? " " : "\n\t" );
}
static void reset_line_cnt() { _line_cnt = 1; }
private:
static int _line_cnt;
};
int print_elements::_line_cnt = 1;
int main()
{
string sa[] = { "Signature", "of", "all", "things",
"I", "am", "here", "to", "read",
"seaspawn", "and", "seawrack", "that",
"rusty", "boot"
};
list< string, allocator > slist( sa, sa+15 );
cout << "Исходная последовательность строк:\n\t";
for_each( slist.begin(), slist.end(), print_elements() );
cout << "\n\n";
reverse( slist.begin(), slist.end() );
print_elements::reset_line_cnt();
cout << "Последовательность строк после применения reverse():\n\t";
for_each( slist.begin(), slist.end(), print_elements() ); cout << "\n";
list< string, allocator > slist_copy( slist.size() );
reverse_copy( slist.begin(), slist.end(),
slist_copy.begin() );
}
Алгоритм rotate()
template< class ForwardIterator >
void
rotate( ForwardIterator first,
ForwardIterator middle, ForwardIterator last );
rotate() перемещает элементы из диапазона [first,last) в конец контейнера. Элемент, на который указывает middle, становится первым. Например, для слова "hissboo" вращение вокруг буквы 'b' превращает слово в "boohiss".
Алгоритм rotate_copy()
template< class ForwardIterator, class OutputIterator >
OutputIterator
rotate_copy( ForwardIterator first, ForwardIterator middle,
ForwardIterator last, OutputIterator result );
rotate_copy() ведет себя так же, как rotate(), только новая последовательность копируется в контейнер, начиная с result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность:
1 3 5 7 9 0 2 4 6 8 10
вращение вокруг среднего элемента(0) ::
0 2 4 6 8 10 1 3 5 7 9
вращение вокруг предпоследнего элемента(8) ::
8 10 1 3 5 7 9 0 2 4 6
rotate_copy вокруг среднего элемента ::
7 9 0 2 4 6 8 10 1 3 5
*/
int main()
{
int ia[] = { 1, 3, 5, 7, 9, 0, 2, 4, 6, 8, 10 };
vector< int, allocator > vec( ia, ia+11 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
rotate( &ia[0], &ia[5], &ia[11] );
cout << "вращение вокруг среднего элемента(0) ::\n";
copy( ia, ia+11, ofile ); cout << '\n';
rotate( vec.begin(), vec.end()-2, vec.end() );
cout << "вращение вокруг предпоследнего элемента(8) ::\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
vector< int, allocator > vec_res( vec.size() );
rotate_copy( vec.begin(), vec.begin()+vec.size()/2,
vec.end(), vec_res.begin() );
cout << "rotate_copy вокруг среднего элемента ::\n";
copy( vec_res.begin(), vec_res.end(), ofile );
cout << '\n';
}
Алгоритм search()
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator
search( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2 );
template< class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate >
ForwardIterator
search( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred );
Если даны два диапазона, то search() возвращает итератор, указывающий на первую позицию в диапазоне [first1,last1), начиная с которой второй диапазон входит как подпоследовательность. Если подпоследовательность не найдена, возвращается last1. Например, в слове Mississippi подпоследовательность iss встречается дважды, и search() возвращает итератор, указывающий на начало первого вхождения. В первом варианте для сравнения элементов используется оператор равенства, во втором – указанная программистом операция сравнения.
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
Ожидаем найти подстроку 'ate': a t e
Ожидаем найти подстроку 'vat': v a t
*/
int main()
{
ostream_iterator< char > ofile( cout, " " );
char str[ 25 ] = "a fine and private place";
char substr[] = "ate";
char *found_str = search(str,str+25,substr,substr+3);
cout << "Ожидаем найти подстроку 'ate': ";
copy( found_str, found_str+3, ofile ); cout << '\n';
vector< char, allocator > vec( str, str+24 );
vector< char, allocator > subvec(3);
subvec[0]='v'; subvec[1]='a'; subvec[2]='t';
vector< char, allocator >::iterator iter;
iter = search( vec.begin(), vec.end(),
subvec.begin(), subvec.end(),
equal_to< char >() );
cout << "Ожидаем найти подстроку 'vat': ";
copy( iter, iter+3, ofile ); cout << '\n';
}
Алгоритм search_n()
template< class ForwardIterator, class Size, class Type >
ForwardIterator
search_n( ForwardIterator first, ForwardIterator last,
Size count, const Type &value );
template< class ForwardIterator, class Size,
class Type, class BinaryPredicate >
ForwardIterator
search_n( ForwardIterator first, ForwardIterator last,
Size count, const Type &value, BinaryPredicate pred );
search_n() ищет в последовательности [first,last) подпоследовательность, состоящую из count повторений значения value. Если она не найдена, возвращается last. Например, для поиска подстроки ss в строке Mississippi следует задать value равным 's', а count равным 2. Если же нужно найти две расположенные подряд подстроки ssi, то value задается равным "ssi", а count снова 2. search_n() возвращает итератор на первый элемент со значением value. В первом варианте для сравнения элементов используется оператор равенства, во втором – указанная программистом операция сравнения.
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
Ожидаем найти два вхождения 'o': o o
Ожидаем найти подстроку 'mou': m o u
*/
int main()
{
ostream_iterator< char > ofile( cout, " " );
const char blank = ' ';
const char oh = 'o';
char str[ 26 ] = "oh my a mouse ate a moose";
char *found_str = search_n( str, str+25, 2, oh );
cout << "Ожидаем найти два вхождения 'o': ";
copy( found_str, found_str+2, ofile ); cout << '\n';
vector< char, allocator > vec( str, str+25 );
// найти первую последовательность из трех символов,
// ни один из которых не равен пробелу: mou of mouse
vector< char, allocator >::iterator iter;
iter = search_n( vec.begin(), vec.end(), 3,
blank, not_equal_to< char >() );
cout << "Ожидаем найти подстроку 'mou': ";
copy( iter, iter+3, ofile ); cout << '\n';
}
Алгоритм set_difference()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
set_difference( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
set_difference( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
set_difference() строит отсортированную последовательность из элементов, имеющихся в первой последовательности [first1,last1), но отсутствующих во второй – [first2,last2). Например, разность последовательностей {0,1,2,3} и {0,2,4,6} равна {1,3}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора “меньше”, определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
Алгоритм set_intersection()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
set_intersection( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
set_intersection( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
set_intersection() строит отсортированную последовательность из элементов, встречающихся в обеих последовательностях – [first1,last1) и [first2,last2). Например, пересечение последовательностей {0,1,2,3} и {0,2,4,6} равно {0,2}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора “меньше”, определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
Алгоритм set_symmetric_difference()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
set_symmetric_difference(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
set_symmetric_difference(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
set_symmetric_difference() строит отсортированную последовательность из элементов, которые встречаются только в первой последовательности [first1,last1) или только во второй – [first2,last2). Например, симметрическая разность последовательностей {0,1,2,3} и {0,2,4,6} равна {1,3,4,6}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора “меньше”, определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
Алгоритм set_union()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
set_union() строит отсортированную последовательность из элементов, которые встречаются либо в первой последовательности [first1,last1), либо во второй – [first2,last2), либо в обеих. Например, объединение последовательностей {0,1,2,3} и {0,2,4,6} равно {0,1,2,3,4,6}. Если элемент присутствует в обеих последовательностях, то копируется экземпляр из первой. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора “меньше”, определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
#include <algorithm>
#include <set>
#include <string>
#include <iostream.h>
/* печатается:
элементы множества #1:
Иа-Иа Пух Пятачок Тигра
элементы множества #2:
Бука Пух Слонопотам
элементы set_union():
Бука Иа-Иа Пух Пятачок Слонопотам Тигра
элементы set_intersection():
Пух
элементы set_difference():
Иа-Иа Пятачок Тигра
элементы_symmetric_difference():
Бука Иа-Иа Пятачок Слонопотам Тигра
*/
int main()
{
string str1[] = { "Пух", "Пятачок", "Тигра", "Иа-Иа" };
string str2[] = { "Пух", "Слонопотам", "Бука" };
ostream_iterator< string > ofile( cout, " " );
ааааааааааааааааа
аааааааааа set<string,less<string>,allocator> set1( str1, str1+4 );
аааааааааа set<string,less<string>,allocator> set2( str2, str2+3 );
аааа cout << " ¤ыхьхэЄv ьэюцхёЄтр #1:\n\t";
аааа copy( set1.begin(), set1.end(), ofile ); cout << "\n\n";
аааа cout << "¤ыхьхэЄv ьэюцхёЄтр #2:\n\t";
аааа copy( set2.begin(), set2.end(), ofile ); cout << "\n\n";
аааааааааа set<string,less<string>,allocator> res;
аааааааааа set_union( set1.begin(), set1.end(),
ааааааааааааааа set2.begin(), set2.end(),
ааааааааааааааа inserter( res, res.begin() ));
аааа cout << "¤ыхьхэЄv set_union():\n\t";
аааа copy( res.begin(), res.end(), ofile ); cout << "\n\n";
аааааааааа res.clear();
аааааааааа set_intersection( set1.begin(), set1.end(),
аааааааааааааааааааааа set2.begin(), set2.end(),
аааааааааааааааааааааа inserter( res, res.begin() ));
аааа cout << "¤ыхьхэЄv set_intersection():\n\t";
аааа copy( res.begin(), res.end(), ofile ); cout << "\n\n";
аааа res.clear();
аааа set_difference( set1.begin(), set1.end(),
аааааааааааааааааааа set2.begin(), set2.end(),
аааааааааааааааааааа inserter( res, res.begin() ));
аааа cout << "¤ыхьхэЄv set_difference():\n\t";
аааа copy( res.begin(), res.end(), ofile ); cout << "\n\n";
а аааres.clear();
аааа set_symmetric_difference( set1.begin(), set1.end(),
аааааааааааааааааааааааааааааа set2.begin(), set2.end(),
аааааааааааааааааааааааааааааа inserter( res, res.begin() ));
аааа cout << "¤ыхьхэЄv set_symmetric_difference():\n\t";
аааа copy( res.begin(), res.end(), ofile ); cout << "\n\n";
}
Алгоритм sort()
template< class RandomAccessIterator >
void
sort( RandomAccessIterator first,
RandomAccessIterator last );
template< class RandomAccessIterator, class Compare >
void
sort( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
sort() переупорядочивает элементы в диапазоне [first,last) по возрастанию, используя оператор “меньше”, определенный для типа элементов контейнера. Во втором варианте порядок устанавливается операцией сравнения comp. (Для сохранения относительного порядка равных элементов пользуйтесь алгоритмом stable_sort().) Мы не приводим пример, специально иллюстрирующий применение алгоритма sort(), поскольку его можно найти во многих других программах, в частности в binary_search(), equal_range() и inplace_merge().
Алгоритм 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";
}
Алгоритм stable_partition()
template< class BidirectionalIterator, class Predicate >
BidirectionalIterator
stable_partition( BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred );
stable_partition() ведет себя так же, как partition(), но гарантированно сохраняет относительный порядок элементов контейнера. Вот та же программа, что и для алгоритма partition(), но с использованием stable_partition().
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность:
29 23 20 22 17 15 26 51 19 12 35 40
устойчивое разбиение по четным элементам:
20 22 26 12 40 29 23 17 15 51 19
устойчивое разбиение по элементам, меньшим 25:
23 20 22 17 15 19 12 29 26 51 35 40
*/
class even_elem {
public:
bool operator()( int elem ) {
return elem%2 ? false : true;
}
};
int main()
{
int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
vector< int, allocator > vec( ia, ia+12 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
stable_partition( &ia[0], &ia[12], even_elem() );
cout << "устойчивое разбиение по четным элементам:\n";
copy( ia, ia+11, ofile ); cout << '\n';
stable_partition( vec.begin(), vec.end(),
bind2nd(less<int>(),25) );
cout << "устойчивое разбиение по элементам, меньшим 25:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм stable_sort()
template< class RandomAccessIterator >
void
stable_sort( RandomAccessIterator first,
RandomAccessIterator last );
template< class RandomAccessIterator, class Compare >
void
stable_sort( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
stable_sort() ведет себя так же, как sort(), но гарантированно сохраняет относительный порядок равных элементов контейнера. Второй вариант упорядочивает элементы на основе заданной программистом операции сравнения comp.
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность:
29 23 20 22 12 17 15 26 51 19 12 23 35 40
устойчивая сортировка - по умолчанию в порядке возрастания:
12 12 15 17 19 20 22 23 23 26 29 35 40 51
устойчивая сортировка: в порядке убывания:
51 40 35 29 26 23 23 22 20 19 17 15 12 12
*/
int main()
{
int ia[] = { 29,23,20,22,12,17,15,26,51,19,12,23,35,40 };
vector< int, allocator > vec( ia, ia+14 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
stable_sort( &ia[0], &ia[14] );
cout << "устойчивая сортировка - по умолчанию "
<< "в порядке возрастания:\n";
copy( ia, ia+14, ofile ); cout << '\n';
stable_sort( vec.begin(), vec.end(), greater<int>() );
cout << "устойчивая сортировка: в порядке убывания:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм swap()
template< class Type >
void
swap ( Type &ob1, Type &ob2 );
swap() обменивает значения объектов ob1 и ob2.
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность:
3 4 5 0 1 2
после применения swap() в процедуре пузырьковой сортировки:
0 1 2 3 4 5
*/
int main()
{
int ia[] = { 3, 4, 5, 0, 1, 2 };
vector< int, allocator > vec( ia, ia+6 );
for ( int ix = 0; ix < 6; ++ix )
for ( int iy = ix; iy < 6; ++iy ) {
if ( vec[iy] < vec[ ix ] )
swap( vec[iy], vec[ix] );
}
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( ia, ia+6, ofile ); cout << '\n';
cout << "после применения swap() в процедуре "
<< "пузырьковой сортировки:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм swap_ranges()
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator2
swap_ranges( ForwardIterator1 first1, ForwardIterator1 last,
ForwardIterator2 first2 );
swap_ranges() обменивает элементы из диапазона [first1,last) с элементами другого диапазона, начиная с first2. Эти последовательности могут находиться в одном контейнере или в разных. Поведение программы не определено, если они находятся в одном контейнере и при этом частично перекрываются, а также в случае, когда вторая последовательность короче первой. Алгоритм возвращает итератор, указывающий на элемент за последним переставленным.
#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
исходная последовательность элементов первого контейнера:
0 1 2 3 4 5 6 7 8 9
исходная последовательность элементов второго контейнера:
5 6 7 8 9
массив после перестановки двух половин:
5 6 7 8 9 0 1 2 3 4
первый контейнер после перестановки двух векторов:
5 6 7 8 9 5 6 7 8 9
второй контейнер после перестановки двух векторов:
0 1 2 3 4
*/
int main()
{
int ia[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int ia2[] = { 5, 6, 7, 8, 9 };
vector< int, allocator > vec( ia, ia+10 );
vector< int, allocator > vec2( ia2, ia2+5 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность элементов первого контейнера:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
cout << "исходная последовательность элементов второго контейнера:\n";
copy( vec2.begin(), vec2.end(), ofile ); cout << '\n';
// перестановка внутри одного контейнера
swap_ranges( &ia[0], &ia[5], &ia[5] );
cout << "массив после перестановки двух половин:\n";
copy( ia, ia+10, ofile ); cout << '\n';
// перестановка разных контейнеров
vector< int, allocator >::iterator last =
find( vec.begin(), vec.end(), 5 );
swap_ranges( vec.begin(), last, vec2.begin() );
cout << "первый контейнер после перестановки двух векторов:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
cout << "второй контейнер после перестановки двух векторов:\n";
copy( vec2.begin(), vec2.end(), ofile ); cout << '\n';
}
Алгоритм transform()
template< class InputIterator, class OutputIterator,
class UnaryOperation >
OutputIterator
transform( InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryOperation >
OutputIterator
transform( InputIterator1 first1, InputIterator1 last,
InputIterator2 first2, OutputIterator result,
BinaryOperation bop );
Первый вариант transform() генерирует новую последовательность, применяя операцию op к каждому элементу из диапазона [first,last). Например, если есть последовательность {0,1,1,2,3,5} и объект-функция Double, удваивающий свой аргумент, то в результате получим {0,2,2,4,6,10}.
Второй вариант генерирует новую последовательность, применяя бинарную операцию bop к паре элементов, один из которых взят из диапазона [first1,last1), а второй – из последовательности, начинающейся с first2. Поведение программы не определено, если во второй последовательности меньше элементов, чем в первой. Например, для двух последовательностей {1,3,5,9} и {2,4,6,8} и объекта-функции AddAndDouble, которая складывает два элемента и удваивает их сумму, результатом будет {6,14,22,34}.
Оба варианта transform() помещают результирующую последовательность в контейнер с элемента, на который указывает итератор result. Этот итератор может адресовать и элемент любого из входных контейнеров, в таком случае исходные элементы будут заменены на результат выполнения transform(). Выходной итератор указывает на элемент за последним помещенным в результирующий контейнер.
#include <algorithm>
#include <vector>
#include <math.h>
#include <iostream.h>
/*
* печатается:
исходный массив: 3 5 8 13 21
преобразование элементов путем удваивания: 6 10 16 26 42
преобразование элементов путем взятия разности: 3 5 8 13 21
*/
int double_val( int val ) { return val + val; }
int difference( int val1, int val2 ) {
return abs( val1 - val2 ); }
int main()
{
int ia[] = { 3, 5, 8, 13, 21 };
vector<int, allocator> vec( 5 );
ostream_iterator<int> outfile( cout, " " );
cout << "исходный массив: ";
copy( ia, ia+5, outfile ); cout << endl;
cout << "преобразование элементов путем удваивания: ";
transform( ia, ia+5, vec.begin(), double_val );
copy( vec.begin(), vec.end(), outfile ); cout << endl;
cout << "преобразование элементов путем взятия разности: ";
transform( ia, ia+5, vec.begin(), outfile, difference );
cout << endl;
}
Алгоритм unique()
template< class ForwardIterator >
ForwardIterator
unique( ForwardIterator first,
ForwardIterator last );
template< class ForwardIterator, class BinaryPredicate >
ForwardIterator
unique( ForwardIterator first,
ForwardIterator last, BinaryPredicate pred );
Все группы равных соседних элементов заменяются одним. В первом варианте при сравнении используется оператор равенства, определенный для типа элементов в контейнере. Во втором варианте два элемента равны, если бинарный предикат pred для них возвращает true. Таким образом, слово mississippi будет преобразовано в misisipi. Обратите внимание, что три буквы 'i' не являются соседними, поэтому они не заменяются одной, как и две пары несоседних 's'. Если нужно, чтобы все одинаковые элементы были заменены одним, придется сначала отсортировать контейнер.
На самом деле поведение unique() интуитивно не совсем очевидно и напоминает remove(). В обоих случаях размер контейнера не изменяется: каждый уникальный элемент помещается в очередную позицию, начиная с first.
В нашем примере физически будет получено слово misisipippi, где ppi – остаток, “отходы” алгоритма. Возвращаемый итератор указывает на начало этого остатка и обычно передается алгоритму erase() для удаления ненужных элементов. (Поскольку для встроенного массива операция erase() не поддерживается, то лучше воспользоваться алгоритмом unique_copy().)
Алгоритм unique_copy()
template< class InputIterator, class OutputIterator >
OutputIterator
unique_copy( InputIterator first, InputIterator last,
OutputIterator result );
template< class InputIterator, class OutputIterator,
class BinaryPredicate >
OutputIterator
unique_copy( InputIterator first, InputIterator last,
OutputIterator result, BinaryPredicate pred );
unique_copy() копирует входной контейнер в выходной, заменяя группы одинаковых соседних элементов на один элемент с тем же значением. О том, что понимается под равными элементами, говорилось при описании алгоритма unique(). Чтобы все дубликаты были гарантированно удалены, входной контейнер необходимо предварительно отсортировать. Возвращаемый итератор указывает на элемент за последним скопированным.
#include <algorithm>
#include <vector>
#include <string>
#include <iterator>
#include <assert.h>
template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
void (*pfi)( int ) = print_elements;
void (*pfs)( string ) = print_elements;
int main()
{
int ia[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5 };
vector<int,allocator> vec( ia, ia+10 );
vector<int,allocator>::iterator vec_iter;
// последовательность не изменяется: нули не стоят рядом
// печатается: 0 1 0 2 0 3 0 4 0 5
vec_iter = unique( vec.begin(), vec.end() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
// отсортировать вектор, затем применить unique: модифицируется
// печатается: 0 1 2 3 4 5 2 3 4 5
sort( vec.begin(), vec.end() );
vec_iter = unique( vec.begin(), vec.end() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
// удалить из контейнера ненужные элементы
// печатается: 0 1 2 3 4 5
vec.erase( vec_iter, vec.end() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
string sa[] = { "enough", "is", "enough",
"enough", "is", "good" };
vector<string,allocator> svec( sa, sa+6 );
vector<string,allocator> vec_result( svec.size() );
vector<string,allocator>::iterator svec_iter;
sort( svec.begin(), svec.end() );
svec_iter = unique_copy( svec.begin(), svec.end(),
vec_result.begin() );
// печатается: enough good is
for_each( vec_result.begin(), svec_iter, pfs );
cout << "\n\n";
}
Алгоритм upper_bound()
template< class ForwardIterator, class Type >
ForwardIterator
upper_bound( ForwardIterator first,
ForwardIterator last, const Type &value );
template< class ForwardIterator, class Type, class Compare >
ForwardIterator
upper_bound( ForwardIterator first,
ForwardIterator last, const Type &value,
Compare comp );
upper_bound() возвращает итератор, указывающий на последнюю позицию в отсортированной последовательности [first,last), в которую еще можно вставить значение value, не нарушая упорядоченности. Значения всех элементов, начиная с этой позиции и далее, будут больше, чем value. Например, если дана последовательность:
int ia[] = {12,15,17,19,20,22,23,26,29,35,40,51};
то обращение к upper_bound() с value=21 вернет итератор, указывающий на значение 22, а обращение с value=22 – на значение 23. В первом варианте для сравнения используется оператор “меньше”, определенный для типа элементов контейнера; во втором – заданная программистом операция comp.
#include <algorithm>
#include <vector>
#include <assert.h>
#include <iostream.h>
template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
void (*pfi)( int ) = print_elements;
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,ia+12);
int *iter = upper_bound(ia,ia+12,19);
assert( *iter == 20 );
sort( vec.begin(), vec.end(), greater<int>() );
vector<int,allocator>::iterator iter_vec;
iter_vec = upper_bound( vec.begin(), vec.end(),
27, greater<int>() );
assert( *iter_vec == 26 );
// печатается: 51 40 35 29 27 26 23 22 20 19 17 15 12
vec.insert( iter_vec, 27 );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
}
Алгоритмы для работы с хипом
В стандартной библиотеке используется макс-хип. Макс-хип– это представленное в виде массива двоичное дерево, для которого значение ключа в каждом узле больше либо равно значению ключа в каждом из узлов-потомков. (Подробное обсуждение макс-хипа можно найти в [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(), так как они требуют изменения размера контейнера. Мы опишем все четыре алгоритма, а затем проиллюстрируем их работу на примере небольшой программы.
Алгоритмы генерирования и модификации
Шесть алгоритмов генерирования и модификации либо создают и заполняют новую последовательность, либо изменяют значения в существующей.
fill(), fill_n(), for_each(), generate(),generate_n(), transform()
Алгоритмы перестановки
Рассмотрим последовательность из трех символов: {a,b,c}. Для нее существует шесть различных перестановок: abc, acb, bac, bca, cab и cba, лексикографически упорядоченных на основе оператора “меньше”. Таким образом, abc– это первая перестановка, потому что каждый элемент меньше последующего. Следующая перестановка – acb, поскольку в начале все еще находится a – наименьший элемент последовательности. Соответственно перестановки, начинающиеся с b, предшествуют тем, которые начинаются с с. Из bac и bca меньшей является bac, так как последовательность ac лексикографически меньше, чем ca. Если дана перестановка bca, то можно сказать, что предшествующей для нее будет bac, а последующей – cab. Для перестановки abc нет предшествующей, а для cba – последующей.
next_permutation(), prev_permutation()
Алгоритмы поиска
Тринадцать алгоритмов поиска предоставляют различные способы нахождения определенного значения в контейнере. Три алгоритма equal_range(), lower_bound() и upper_bound() выполняют ту или иную форму двоичного поиска. Они показывают, в какое место контейнера можно вставить новое значение, не нарушая порядка сортировки.
adjacent_find(), binary_search(), count(),count_if(), equal_range(),
find(), find_end(), find_first_of(), find_if(), lower_bound(),
upper_bound(), search(), search_n()
Алгоритмы работы с хипом
Хип (heap) – это разновидность двоичного дерева, представленного в массиве. Стандартная библиотека предоставляет такую реализацию хипа, в которой значение ключа в любом узле больше либо равно значению ключа в любом потомке этого узла.
make_heap(), pop_heap(), push_heap(), sort_heap()
Алгоритмы работы с множествами
Четыре алгоритма этой категории реализуют теоретико-множественные операции над любым контейнерным типом. При объединении создается отсортированная последовательность элементов, принадлежащих хотя бы одному контейнеру, при пересечении– обоим контейнерам, а при взятии разности – принадлежащих первому контейнеру, но не принадлежащих второму. Наконец, симметрическая разность – это отсортированная последовательность элементов, принадлежащих одному из контейнеров, но не обоим.
set_union(), set_intersection(), set_difference(),
set_symmetric_difference()
Алгоритмы сортировки и упорядочения
Четырнадцать алгоритмов сортировки и упорядочения предлагают различные способы упорядочения элементов контейнера. Разбиение (partition)– это разделение элементов контейнера на две группы: удовлетворяющие и не удовлетворяющие некоторому условию. Так, можно разбить контейнер по признаку четности/нечетности чисел или в зависимости от того, начинается слово с заглавной или со строчной буквы. Устойчивый (stable) алгоритм сохраняет относительный порядок элементов с одинаковыми значениями или удовлетворяющих одному и тому же условию. Например, если дана последовательность:
{ "pshew", "honey", "Tigger", "Pooh" }
то устойчивое разбиение по наличию/отсутствию заглавной буквы в начале слова генерирует последовательность, в которой относительный порядок слов в каждой категории сохранен:
{ "Tigger", "Pooh", "pshew", "honey" }
При использовании неустойчивой версии алгоритма сохранение порядка не гарантируется. (Отметим, что алгоритмы сортировки нельзя применять к списку и ассоциативным контейнерам, таким, как множество (set) или отображение (map).)
inplace_merge(), merge(), nth_element(), partial_sort(),
partial_sort_copy(), partition(), random_shuffle(), reverse(),
reverse_copy(), rotate(), rotate_copy(), sort(), stable_sort(),
stable_partition()
Алгоритмы сравнения
Семь алгоритмов дают разные способы сравнения одного контейнера с другим (алгоритмы min() и max() сравнивают два элемента). Алгоритм lexicographical_compare() выполняет лексикографическое (словарное) упорядочение (см. также обсуждение перестановок и Приложение).
equal(), includes(), lexicographical_compare(), max(), max_element(),
min(), min_element(), mismatch()
Алгоритмы удаления и подстановки
Пятнадцать алгоритмов удаления и подстановки предоставляют различные способы замены или исключения одного элемента или целого диапазона. unique() удаляет одинаковые соседние элементы. iter_swap() обменивает значения элементов, адресованных парой итераторов, но не модифицирует сами итераторы.
copy(), copy_backwards(), iter_swap(), remove(), remove_copy(),
remove_if(),remove_if_copy(), replace(), replace_copy(),
replace_if(), replace_copy_if(), swap(), swap_range(), unique(),
unique_copy()
Альтернативная иерархия классов
Хотя наша иерархия классов Query представляется вполне приемлемой, она вовсе не является единственно возможной. Например, AndQuery и OrQuery связаны с бинарной операцией, поэтому они в какой-то степени дублируют друг друга. Можно вынести все данные и функции-члены, общие для них, в абстрактный базовый класс BinaryQuery. Поддерево новой иерархии Query изображено на рисунке 17.2:
Query
BinaryQuery
AndQuery OrQuery
Рис. 17.2. Альтернативная иерархия классов
Класс BinaryQuery – это тоже абстрактный базовый класс, следовательно, его фактические объекты в приложении не появляются. Разумной реализации eval() для него предложить нельзя, поэтому чисто виртуальная функция, объявленная в Query, в классе BinaryQuery останется чисто виртуальной. (Подробнее о таких функциях мы поговорим в разделе 17.5.)
Две функции-члена для доступа – lop() и rop(), общие для обоих классов, переносятся выше, в BinaryQuery, и определяются как нестатические встроенные. Аналогично два члена _lop и _rop, объявленные в обоих классах, также переносятся в BinaryQuery и становятся нестатическими и защищенными. Открытые конструкторы обоих производных классов объединяются в один защищенный конструктор BinaryQuery:
class BinaryQuery : public Query {
public:
const Query *lop() { return _lop; }
const Query *rop() { return _rop; }
protected:
BinaryQuery( Query *lop, Query *rop )
: _lop( lop ), _rop( rop )
{}
Query *_lop;
Query *_rop;
};
Складывается впечатление, что теперь оба производных класса должны предоставить лишь подходящие реализации eval():
// увы! эти определения классов некорректны
class OrQuery : public BinaryQuery {
public:
virtual void eval();
};
class AndQuery : public BinaryQuery {
public:
virtual void eval();
};
Однако в том виде, в котором мы их определили, эти классы неполны. При компиляции самих определений ошибок не возникает, но если мы попытаемся определить фактический объект:
// ошибка: отсутствует конструктор класса AndQuery
AndQuery proust( new NameQuery( "marcel" ),
new NameQuery( "proust " ));
то компилятор выдаст сообщение об ошибке: в классе AndQuery нет конструктора, готового принять два аргумента.
Мы предположили, что AndQuery и OrQuery наследуют конструктор BinaryQuery точно так же, как они наследуют функции-члены lop() и rop(). Однако производный класс не наследует конструкторов базового. (Это могло бы привести к ошибкам, связанным с неинициализированными членами производного класса. Представьте, что будет, если в AndQuery добавить пару членов, не являющихся объектами классов: унаследованный конструктор базового класса для инициализации объекта производного AndQuery применять уже нельзя. Однако программист может этого не осознавать. Ошибка проявится не при конструировании объекта AndQuery, а позже, при его использовании. Кстати говоря, перегруженные операторы new и delete наследуются, что иногда приводит к аналогичным проблемам.)
Каждый производный класс должен предоставлять собственный набор конструкторов. В случае классов AndQuery и OrQuery единственная цель конструкторов – обеспечить интерфейс для передачи двух своих операндов конструктору BinaryQuery. Так выглядит исправленная реализация:
// правильно: эти определения классов корректны
class OrQuery : public BinaryQuery {
public:
OrQuery( Query *lop, Query *rop )
: BinaryQuery( lop, rop ) {}
virtual void eval();
};
class AndQuery : public BinaryQuery {
public:
AndQuery( Query *lop, Query *rop )
: BinaryQuery( lop, rop ) {}
virtual void eval();
};
Если мы еще раз взглянем на рис. 17.2, то увидим, что BinaryQuery – непосредственный базовый класс для AndQuery и OrQuery, а Query –для BinaryQuery. Таким образом, Query не является непосредственным базовым классом для AndQuery и OrQuery.
Конструктору производного класса разрешается напрямую вызывать только конструктор своего непосредственного предшественника в иерархии (виртуальное наследование является исключением из этого правила, да и из многих других тоже: см. раздел 18.5). Например, попытка включить конструктор Query в список инициализации членов объекта AndQuery приведет к ошибке.
При определении объектов классов AndQuery и OrQuery теперь вызываются три конструктора: для базового Query, для непосредственного базового класса BinaryQuery и для производного AndQuery или OrQuery. (Порядок вызова конструкторов базовых классов отражает обход дерева иерархии наследования в глубину.) Дополнительный уровень иерархии, связанный с BinaryQuery, практически не влияет на производительность, поскольку мы определили его конструкторы как встроенные.
Так как модифицированная иерархия сохраняет открытый интерфейс исходного проекта, то все эти изменения не сказываются на коде, который был написан в расчете на старую иерархию. Хотя модифицировать пользовательский код не нужно, перекомпилировать его все же придется, что может отвратить некоторых пользователей от перехода на новую версию.
Аргументы шаблона для параметров-констант
Параметр шаблона класса может и не быть типом. На аргументы, подставляемые вместо таких параметров, накладываются некоторые ограничения. В следующем примере мы изменяем определение класса Screen (см. главу 13) на шаблон, параметризованный высотой и шириной:
template <int hi, int wid>
class Screen {
public:
Screen() : _height( hi ), _width( wid ), _cursor ( 0 ),
_screen( hi * wid, '#' )
{ }
// ...
private:
string _screen;
string::size_type _cursor;
short _height;
short _width;
};
typedef Screen<24,80> termScreen;
termScreen hp2621;
Screen<8,24> ancientScreen;
Выражение, с которым связан параметр, не являющийся типом, должно быть константным, т.е. вычисляемым во время компиляции. В примере выше typedef termScreen ссылается на экземпляр шаблона Screen<24,80>, где аргумент шаблона для hi равен 24, а для wid – 80. В обоих случаях аргумент – это константное выражение.
Однако для шаблона BufPtr конкретизация приводит к ошибке, так как значение указателя, получающееся при вызове оператора new(), становится известно только во время выполнения:
template <int *ptr> class BufPtr { ... };
// ошибка: аргумент шаблона нельзя вычислить во время компиляции
BufPtr< new int[24] > bp;
Не является константным выражением и значение неконстантного объекта. Его нельзя использовать в качестве аргумента для параметра-константы шаблона. Однако адрес любого объекта в области видимости пространства имен, в отличие от адреса локального объекта, является константным выражением (даже если спецификатор const отсутствует), поэтому его можно применять в качестве аргумента для параметра-константы. Константным выражением будет и значение оператора sizeof:
template <int size> Buf { ... };
template <int *ptr> class BufPtr { ... };
int size_val = 1024;
const int c_size_val = 1024;
Buf< 1024 > buf0; // правильно
преобразования целых типов:
template <unsigned int size> Buf{ ... };
Buf< 1024 > bpObj; // преобразование из int в unsigned int
(Более подробно они описаны в разделе 9.3.)
Рассмотрим следующие объявления:
extern void foo( char * );
extern void bar( void * );
typedef void (*PFV)( void * );
const unsigned int x = 1024;
template <class Type,
unsigned int size,
PFV handler> class Array { ... };
Array<int, 1024U, bar> a0; // правильно: преобразование не нужно
Array<int, 1024U, foo> a1; // ошибка: foo != PFV
Array<int, 1024, bar> a2; // правильно: 1024 преобразуется в unsigned int
Array<int, 1024, bar> a3; // ошибка: foo != PFV
Array<int, x, bar> a4; // правильно: преобразование не нужно
Array<int, x, foo> a5; // ошибка: foo != PFV
Объекты a0 и a4 класса Array определены правильно, так как аргументы шаблона точно соответствуют типам параметров. Объект a2 также определен правильно, потому что аргумент 1024 типа int приводится к типу unsigned int параметра-константы size с помощью преобразования целых типов. Объявления a1, a3 и a5 ошибочны, так как не существует преобразования между любыми двумя типами функций.
Приведение значения 0 целого типа к типу указателя недопустимо:
template <int *ptr>
class BufPtr { ... };
// ошибка: 0 имеет тип int
// неявное преобразование в нулевой указатель не применяется
BufPtr< 0 > nil;
Упражнение 16.3
Укажите, какие из данных конкретизированных шаблонов действительно приводят к конкретизации:
template < class Type >
class Stack { };
void f1( Stack< char > ); // (a)
class Exercise {
// ...
Stack< double > &rsd; // (b)
Stack< int > si; // (c)
};
int main() {
Stack< char > *sc; // (d)
f1( *sc ); // (e)
int iObj = sizeof( Stack< string > ); // (f)
}
Упражнение 16.4
Какие из следующих конкретизаций шаблонов корректны? Почему?
template < int *ptr > class Ptr ( ... };
template < class Type, int size > class Fixed_Array { ... };
template < int hi, int wid > class Screen { ... };
(a) const int size = 1024;
Ptr< &size > bp1;
(b) int arr[10];
Ptr< arr > bp2;
(c) Ptr < 0 > bp3;
(d) const int hi = 40;
const int wi = 80;
Screen< hi, wi+32 > sObj;
(e) const int size_val = 1024;
Fixed_Array< string, size_val > fa1;
(f) unsigned int fasize = 255;
Fixed_Array< int, fasize > fa2;
(g) const double db = 3.1415;
Fixed_Array< double, db > fa3;
Аргументы со значениями по умолчанию
Наличие аргументов со значениями по умолчанию способно расширить множество устоявших функций. Устоявшими являются функции, которые вызываются с данным списком фактических аргументов. Но такая функция может иметь больше формальных параметров, чем задано фактических аргументов, в том случае, когда для каждого неуказанного параметра есть некое значение по умолчанию:
extern void ff( int );
extern void ff( long, int = 0 );
int main() {
ff( 2L ); // соответствует ff( long, 0 );
ff( 0, 0 ); // соответствует ff( long, int );
ff( 0 ); // соответствует ff( int );
ff( 3.14 ); // ошибка: неоднозначность
}
Для первого и третьего вызовов функция ff() является устоявшей, хотя передан всего один фактический аргумент. Это обусловлено следующими причинами:
1. для второго формального параметра есть значение по умолчанию;
2. первый параметр типа long точно соответствует фактическому аргументу в первом вызове и может быть приведен к типу аргумента в третьем вызове за счет последовательности, имеющей ранг стандартного преобразования.
Последний вызов является неоднозначным, поскольку обе устоявших функции могут быть выбраны, если применить стандартное преобразование к первому аргументу. Функции ff(int) не отдается предпочтение только потому, что у нее один параметр.
Упражнение 9.9
Объясните, что происходит при разрешении перегрузки для вызова функции compute() внутри main(). Какие функции являются кандидатами? Какие из них устоят после первого шага? Какие последовательности преобразований надо применить к фактическому аргументу, чтобы он соответствовал формальному параметру для каждой устоявшей функции? Какая функция будет наилучшей из устоявших?
namespace primerLib {
void compute();
void compute( const void * );
}
using primerLib::compute;
void compute( int );
void compute( double, double = 3.4 );
void compute( char*, char* = 0 );
int main() {
compute( 0 );
return 0;
}
Что будет, если using-объявление поместить внутрь main() перед вызовом compute()? Ответьте на те же вопросы.
Арифметические объекты-функции
Предопределенные арифметические объекты-функции поддерживают операции сложения, вычитания, умножения, деления, взятия остатка и вычисления противоположного по знаку значения. Вызываемый оператор – это экземпляр, ассоциированный с типом Type. Если тип является классом, предоставляющим перегруженную реализацию оператора, то именно эта реализация и вызывается.
Сложение: plus<Type>
plus<string> stringAdd;
// вызывается string::operator+()
sres = stringAdd( sval1, sval2 );
dres = BinaryFunc( plus<double>(), dval1, dval2 );
Вычитание: minus<Type>
minus<int> intSub;
ires = intSub( ival1, ival2 );
dres = BinaryFunc( minus<double>(), dval1, dval2 );
Умножение: multiplies<Type>
multiplies<complex> complexMultiplies;
cres = complexMultiplies( cval1, cval2 );
dres = BinaryFunc( multiplies<double>(), dval1, dval2 );
Деление: divides<Type>
divides<int> intDivides;
ires = intDivides( ival1, ival2 );
dres = BinaryFunc( divides<double>(), dval1, dval2 );
Взятие остатка: modulus<Type>
modulus<Int> IntModulus;
Ires = IntModulus( Ival1, Ival2 );
ires = BinaryFunc( modulus<int>(), ival1, ival2 );
Вычисление противоположного значения: negate<Type>
negate<int> intNegate;
ires = intNegate( ires );
Ires = UnaryFunc( negate<Int>(), Ival1 );
Арифметические операции
Таблица 4.1. Арифметические операции
| Символ операции | Значение | Использование | |||
| * | Умножение | expr * expr | |||
| / | Деление | expr / expr | |||
| % | Остаток от деления | expr % expr | |||
| + | Сложение | expr + expr | |||
| - | Вычитание | expr – expr |
Деление целых чисел дает в результате целое число. Дробная часть результата, если она есть, отбрасывается:
int ivall = 21 / 6;
int iva12 = 21 / 7;
И ival1, и ival2 в итоге получат значение 3.
Операция остаток
(%), называемая также делением по модулю, возвращает остаток от деления первого операнда на второй, но применяется только к операндам целого типа (char, short, int, long). Результат положителен, если оба операнда положительны. Если же один или оба операнда отрицательны, результат зависит от реализации, то есть машинно-зависим. Вот примеры правильного и неправильного использования деления по модулю:
3.14 % 3; // ошибка: операнд типа double
21 % 6; // правильно: 3
21 % 7; // правильно: 0
21 % -5; // машинно-зависимо: -1 или 1
int iva1 = 1024;
double dval = 3.14159;
iva1 % 12; // правильно:
iva1 % dval; // ошибка: операнд типа double
Иногда результат вычисления арифметического выражения может быть неправильным либо не определенным. В этих случаях говорят об арифметических исключениях (хотя они не вызывают возбуждения исключения в программе). Арифметические исключения могут иметь чисто математическую природу (скажем, деление на 0) или происходить от представления чисел в компьютере – как переполнение (когда значение превышает величину, которая может быть выражена объектом данного типа). Например, тип char содержит 8 бит и способен хранить значения от 0 до 255 либо от -128 до 127 в зависимости от того, знаковый он или беззнаковый. В следующем примере попытка присвоить объекту типа char значение 256 вызывает переполнение:
#include <iostream>
int main() {
char byte_value = 32;
int ival = 8;
// переполнение памяти, отведенной под byte_value
byte_value = ival * byte_value;
cout << "byte_value: " <<static_cast<int>(byte_value) << endl;
}
Для представления числа 256 необходимы 9 бит. Переменная byte_value получает некоторое неопределенное (машинно-зависимое) значение. Допустим, на нашей рабочей станции SGI мы получили 0. Первая попытка напечатать это значение с помощью:
cout << "byte_va1ue: " << byte_va1ue << endl;
привела к результату:
byte_value:
После некоторого замешательства мы поняли, что значение 0 – это нулевой символ ASCII, который не имеет представления при печати. Чтобы напечатать не представление символа, а его значение, нам пришлось использовать весьма странно выглядящее выражение:
static_cast<int>(byte_value)
которое называется явным приведением типа. Оно преобразует тип объекта или выражения в другой тип, явно заданный программистом. В нашем случае мы изменили byte_value на int. Теперь программа выдает более осмысленный результат:
byte_value: 0
На самом деле нужно было изменить не значение, соответствующее byte_value, а поведение операции вывода, которая действует по-разному для разных типов. Объекты типа char представляются ASCII-символами (а не кодами), в то время как для объектов типа int мы увидим содержащиеся в них значения. (Преобразования типов рассмотрены в разделе 4.14.)
Это небольшое отступление от темы – обсуждение проблем преобразования типов – вызвано обнаруженной нами погрешностью в работе нашей программы и в каком-то смысле напоминает реальный процесс программирования, когда аномальное поведение программы заставляет на время забыть о том, ради достижения какой, собственно, цели она пишется, и сосредоточиться на несущественных, казалось бы, деталях. Такая мелочь, как недостаточно продуманный выбор типа данных, приводящий к переполнению, может стать причиной трудно обнаруживаемой ошибки: из соображений эффективности проверка на переполнение не производится во время выполнения программы.
Стандартная библиотека С++ имеет заголовочный файл limits, содержащий различную информацию о встроенных типах данных, в том числе и диапазоны значений для каждого типа. Заголовочные файлы climits и cfloat также содержат эту информацию. (Об использовании этих заголовочных файлов для того, чтобы избежать переполнения и потери значимости, см. главы 4 и 6 [PLAUGER92]).
Арифметика вещественных чисел создает еще одну проблему, связанную с округлением. Вещественное число представляется фиксированным количеством разрядов (разным для разных типов – float, double и long double), и точность значения зависит от используемого типа данных. Но даже самый точный тип long double не может устранить ошибку округления. Вещественная величина в любом случае представляется с некоторой ограниченной точностью. (См. [SHAMPINE97] о проблемах округления вещественных чисел.)
Упражнение 4.1
В чем разница между приведенными выражениями с операцией деления?
double dvall = 10.0, dva12 = 3.0;
int ivall = 10, iva12 = 3;
dvall / dva12;
ivall / iva12;
Упражнение 4.2
Напишите выражение, определяющее, четным или нечетным является данное целое число.
Упражнение 4.3
Найдите заголовочные файлы limits, climits и cfloat и посмотрите, что они содержат.
Арифметические преобразования типов
Арифметические преобразования приводят оба операнда бинарного арифметического выражения к одному типу, который и будет типом результата выражения. Два общих правила таковы:
типы всегда приводятся к тому из типов, который способен обеспечить наибольший диапазон значений при наибольшей точности. Это помогает уменьшить потери точности при преобразовании;
любое арифметическое выражение, включающее в себя целые операнды типов, меньших чем int, перед вычислением всегда преобразует их в int.
Мы рассмотрим иерархию правил преобразований, начиная с наибольшего типа long double.
Если один из операндов имеет тип long double, второй приводится к этому же типу в любом случае. Например, в следующем выражении символьная константа 'a' трансформируется в long double (значение 97 для представления ASCII) и затем прибавляется к литералу того же типа: 3.14159L + 'a'.
Если в выражении нет операндов long double, но есть операнд double, все преобразуется к этому типу. Например:
int iva1;
float fval;
double dval;
// fva1 и iva1 преобразуются к double перед сложением
dval + fva1 + ival;
В том случае, если нет операндов типа double и long double, но есть операнд float, тип остальных операндов меняется на float:
char cvat;
int iva1;
float fva1;
// iva1 и cval преобразуются к float перед сложением
cvat + fva1 + iva1;
Если у нас нет вещественных операндов , значит, все они представляют собой целые типы. Прежде чем определить тип результата, производится преобразование, называемое приведением к целому: все операнды с типом меньше, чем int, заменяются на int.
При приведении к целому типы char, signed char, unsigned char и short int преобразуются в int. Тип unsigned short int трансформируется в int, если этот тип достаточен для представления всего диапазона значений unsigned short int (обычно это происходит в системах, отводящих полслова под short и целое слово под int), в противном случае unsigned short int заменяется на unsigned int.
Тип wchar_t и перечисления приводятся к наименьшему целому типу, способному представить все их значения. Например, в перечислении
enum status { bad, ok };
значения элементов равны 0 и 1. Оба эти значения могут быть представлены типом char, значит char и станет типом внутреннего представления данного перечисления. Приведение к целому преобразует char в int.
В следующем выражении
char cval;
bool found;
enum mumble { ml, m2, m3 } mval;
unsigned long ulong;
cval + ulong; ulong + found; mval + ulong;
перед определением типа результата cval, found и mval преобразуются в int.
После приведения к целому сравниваются получившиеся типы операндов. Если один из них имеет тип unsigned long, то остальные будут того же типа. В нашем примере все три объекта, прибавляемые к ulong, приводятся к типу unsigned long.
Если в выражении нет объектов unsigned long, но есть объекты типа long, тип остальных операндов меняется на long. Например:
char cval;
long lval;
// cval и 1024 преобразуются в long перед сложением
cval + 1024 + lval;
Из этого правила есть одно исключение: преобразование unsigned int в long происходит только в том случае, если тип long способен вместить весь диапазон значений unsigned int. (Обычно это не так в 32-битных системах, где и long, и int представляются одним машинным словом.) Если же тип long не способен представить весь диапазон unsigned int, оба операнда приводятся к unsigned long.
В случае отсутствия операндов типов unsigned long и long, используется тип unsigned int. Если же нет операндов и этого типа, то к int.
Может быть, данное объяснение преобразований типов несколько смутило вас. Запомните основную идею: арифметическое преобразование типов ставит своей целью сохранить точность при вычислении. Это достигается приведением типов всех операндов к типу, способному вместить любое значение любого из присутствующих в выражении операндов.
Автоматические объекты
Автоматический объект размещается в памяти во время вызова функции, в которой он определен. Память для него отводится из программного стека в записи активации функции. Говорят, что такие объекты имеют автоматическую продолжительность хранения, или автоматическую протяженность. Неинициализированный автоматический объект содержит случайное, или неопределенное, значение, оставшееся от предыдущего использования области памяти. После завершения функции ее запись активации выталкивается из программного стека, т.е. память, ассоциированная с локальным объектом, освобождается. Время жизни такого объекта заканчивается с завершением работы функции, и его значение теряется.
Поскольку память, отведенная локальному объекту, освобождается при завершении работы функции, адрес автоматического объекта следует использовать с осторожностью. Например, этот адрес не может быть возвращаемым значением, так как после выполнения функции будет относиться к несуществующему объекту:
#include "Matrix.h"
Matrix* trouble( Matrix *pm )
{
Matrix res;
// какие-то действия
// результат присвоим res
return &res; // плохо!
}
int main()
{
Matrix m1;
// ...
Matrix *mainResult = trouble( &m1 );
// ...
}
mainResult получает значение адреса автоматического объекта res. К несчастью, память, отведенная под res, освобождается по завершении функции trouble(). После возврата в main() mainResult указывает на область памяти, не отведенную никакому объекту. (В данном примере эта область все еще может содержать правильное значение, поскольку мы не вызывали других функций после trouble() и запись ее активации, вероятно, еще не затерта.) Подобные ошибки обнаружить весьма трудно. Дальнейшее использование mainResult в программе скорее всего даст неверные результаты.
Передача в функцию trouble() адреса m1 автоматического объекта функции main() безопасна. Память, отведенная main(), во время вызова trouble()находится в стеке, так что m1 остается доступной внутри trouble().
Если адрес автоматического объекта сохраняется в указателе, время жизни которого больше, чем самого объекта, такой указатель называют висячим. Работа с ним – это серьезная ошибка, поскольку содержимое адресуемой области памяти непредсказуемо. Если комбинация бит по этому адресу оказывается в какой-то степени допустимой (не приводит к нарушению защиты памяти), то программа будет выполняться, но результаты ее будут неправильными.
Безопасное связывание *
При использовании перегрузки складывается впечатление, что в программе можно иметь несколько одноименных функций с разными списками параметров. Однако это лексическое удобство существует только на уровне исходного текста. В большинстве систем компиляции программы, обрабатывающие этот текст для получения исполняемого кода, требуют, чтобы все имена были различны. Редакторы связей, как правило, разрешают внешние ссылки лексически. Если такой редактор встречает имя print два или более раз, он не может различить их путем анализа типов (к этому моменту информация о типах обычно уже потеряна). Поэтому он просто печатает сообщение о повторно определенном символе print и завершает работу.
Чтобы разрешить эту проблему, имя функции вместе с ее списком параметров декорируется
так, чтобы получилось уникальное внутреннее имя. Вызываемые после компилятора программы видят только это внутреннее имя. Как именно производится такое преобразование имен, зависит от реализации. Общая идея заключается в том, чтобы представить число и типы параметров в виде строки символов и дописать ее к имени функции.
Как было сказано в разделе 8.2, такое кодирование гарантирует, в частности, что два объявления одноименных функций с разными списками параметров, находящиеся в разных файлах, не воспринимаются редактором связей как объявления одной и той же функции. Поскольку этот способ помогает различить перегруженные функции на фазе редактирования связей, мы говорим о безопасном связывании.
Декорирование имен не применяется к функциям, объявленным с помощью директивы extern "C", так как лишь одна из множества перегруженных функций может быть написана на чистом С. Две функции с различными списками параметров, объявленные как extern "C", редактор связей воспринимает как один и тот же символ.
Упражнение 9.1
Зачем может понадобиться объявлять перегруженные функции?
Упражнение 9.2
Как нужно объявить перегруженные варианты функции error(), чтобы были корректны следующие вызовы:
int index;
int upperBound;
char selectVal;
// ...
error( "Array out of bounds: ", index, upperBound );
error( "Division by zero" );
error( "Invalid selection", selectVal );
Упражнение 9.3
Объясните, к какому эффекту приводит второе объявление в каждом из приведенных примеров:
(a) int calc( int, int );
int calc( const int, const int );
(b) int get();
double get();
(c) int *reset( int * );
double *reset( double * ):
(d) extern "C" int compute( int *, int );
extern "C" double compute( double *, double );
Упражнение 9.4
Какая из следующих инициализаций приводит к ошибке? Почему?
(a) void reset( int * );
void (*pf)( void * ) = reset;
(b) int calc( int, int );
int (*pf1)( int, int ) = calc;
(c) extern "C" int compute( int *, int );
int (*pf3)( int*, int ) = compute;
(d) void (*pf4)( const matrix & ) = 0;
Безымянные пространства имен
Может возникнуть необходимость определить объект, функцию, класс или любую другую сущность так, чтобы она была видимой только в небольшом участке программы. Это еще один способ решения проблемы засорения глобального пространства имен. Поскольку мы уверены, что эта сущность используется ограниченно, можно не тратить время на выдумывание уникального имени. Если мы объявляем объект внутри функции или блока, его имя видимо только в этом блоке. А как сделать некоторую сущность доступной нескольким функциям, но не всей программе?
Предположим, мы хотим реализовать набор функций для сортировки вектора типа double:
// ----- SortLib.h -----
void quickSort( double *, double * );
void bubbleSort( double *, double * );
void mergeSort( double *, double * );
void heapSort( double *, double * );
Все они используют одну и ту же функцию swap() для того, чтобы менять местами элементы вектора. Однако она не должна быть видна во всей программе, поскольку нужна только четырем названным функциям. Локализуем ее в файле SortLib.C. Приведенный код не дает желаемого результата. Как вы думаете, почему?
// ----- SortLib.C -----
void swap( double *dl, double *d2 ) { /* ... */ }
// только эти функции используют swap()
void quickSort( double *d1, double *d2 ) { /* ... */ }
void bubbleSort( double *d1, double *d2 ) { /* ... */ }
void mergeSort( double *d1, double *d2 ) { /* ... */ }
void heapSort( double *d1, double *d2 ) { /* ... */ }
Хотя функция swap() определена в файле SortLib.C и не появляется в заголовочном файле SortLib.h, где содержится описание интерфейса библиотеки сортировки, она объявлена в глобальной области видимости. Следовательно, это имя является глобальным, при этом сохраняется возможность конфликта с другими именами.
Язык С++ предоставляет возможность использования безымянного пространства имен
для объявления сущности, локальной по отношению к файлу. Определение такого пространства начинается ключевым словом namespace. Очевидно, что никакого имени за этим словом нет, а сразу же идет блок в фигурных скобках, содержащий различные объявления. Например:
// ----- SortLib.C -----
namespace {
void swap( double *dl, double *d2 ) { /* ... */ }
}
// определения функций сортировки не изменяются
Функция swap() видна только в файле SortLib.C. Если в другом файле в безымянном пространстве имен содержится определение swap(), то это другая функция. Наличие двух функций swap() не является ошибкой, поскольку они различны. Безымянные пространства имен отличаются от прочих: определение такого пространства локально для одного файла и не может размещаться в нескольких.
Имя swap() может употребляться в неквалифицированной форме в файле SortLib.C после определения безымянного пространства. Оператор разрешения области видимости для ссылки на его члены не нужен.
void quickSort( double *d1, double *d2 ) {
// ...
double* elem = d1;
// ...
// ссылка на член безымянного пространства имен swap()
swap( d1, elem );
// ...
}
Члены безымянного пространства имен относятся к сущностям программы. Поэтому функция swap() может быть вызвана во время выполнения. Однако имена этих членов видны только внутри одного файла.
До того как в стандарте С++ появилось понятие пространства имен, наиболее удачным решением проблемы локализации было использование ключевого слова static, унаследованного из С. Член безымянного пространства имеет свойства, аналогичные глобальной сущности, объявленной как static. В языке С такая сущность невидима вне файла, в котором объявлена. Например, текст из SortLib.C можно переписать на С, сохранив свойства swap():
// SortLib.C
// swap() невидима для других файлов программы
static void swap( double *d1, double *d2 ) { /* ... */ }
// определения функций сортировки такие же, как и раньше
Во многих программах на С++ используются объявления с ключевым словом static. Предполагается, что они должны быть заменены безымянными пространствами имен по мере того, как все большее число компиляторов начнет поддерживать это понятие.
Упражнение 8.11
Зачем нужно определять собственное пространство имен в программе?
Упражнение 8.12
Имеется следующее объявление operator*(), члена вложенного пространства имен cplusplus_primer::MatrixLib:
namespace cplusplus_primer {
namespace MatrixLib {
class matrix { /*...*/ };
matrix operator* ( const matrix &, const matrix & );
// ...
}
}
Как определить эту функцию в глобальной области видимости? Напишите только прототип.
Упражнение 8.13
Объясните, зачем нужны безымянные пространства имен.
Библиотека iostream
Частью стандартной библиотеки C++ является библиотека iostream– объектно-ориентированная иерархия классов, где используется и множественное, и виртуальное наследование. В ней реализована поддержка для файлового ввода/вывода данных встроенных типов. Кроме того, разработчики классов могут расширять эту библиотеку для чтения и записи новых типов данных.
Для использования библиотеки iostream в программе необходимо включить заголовочный файл
#include <iostream>
Операции ввода/вывода выполняются с помощью классов istream (потоковый ввод) и ostream (потоковый вывод). Третий класс, iostream, является производным от них и поддерживает двунаправленный ввод/вывод. Для удобства в библиотеке определены три стандартных объекта-потока:
cin – объект класса istream, соответствующий стандартному вводу. В общем случае он позволяет читать данные с терминала пользователя;
cout – объект класса ostream, соответствующий стандартному выводу. В общем случае он позволяет выводить данные на терминал пользователя;
cerr – объект класса ostream, соответствующий стандартному выводу для ошибок. В этот поток мы направляем сообщения об ошибках программы.
Вывод осуществляется, как правило, с помощью перегруженного оператора сдвига влево (<<), а ввод – с помощью оператора сдвига вправо (>>):
#include <iostream>
#include <string>
int main()
{
string in_string;
// вывести литерал на терминал пользователя
cout << "Введите свое имя, пожалуйста: ";
// прочитать ответ пользователя в in_string
cin >> in_string;
if ( in_string.empty() )
// вывести сообщение об ошибке на терминал пользователя
cerr << "ошибка: введенная строка пуста!\n";
else cout << "Привет, " << in_string << "!\n";
}
Назначение операторов легче запомнить, если считать, что каждый “указывает” в сторону перемещения данных. Например,
>> x
перемещает данные в x, а
<< x
перемещает данные из x. (В разделе 20. 1 мы покажем, как библиотека iostream поддерживает ввод данных, а в разделе 20.5 – как расширить ее для ввода данных новых типов. Аналогично раздел 20.2 посвящен поддержке вывода, а раздел 20.4 – расширению для вывода данных определенных пользователем типов.)
Помимо чтения с терминала и записи на него, библиотека iostream поддерживает чтение и запись в файлы. Для этого предназначены следующие классы:
ifstream, производный от istream, связывает ввод программы с файлом;
ofstream, производный от ostream, связывает вывод программы с файлом;
fstream, производный от iostream, связывает как ввод, так и вывод программы с файлом.
Чтобы использовать часть библиотеки iostream, связанную с файловым вводом/выводом, необходимо включить в программу заголовочный файл
#include <fstream>
(Файл fstream уже включает iostream, так что включать оба файла необязательно.) Файловый ввод/вывод поддерживается теми же операторами:
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
int main()
{
string ifile;
cout << "Введите имя файла для сортировки: ";
cin >> ifile;
// сконструировать объект класса ifstream для ввода из файла
ifstream infile( ifile.c_str() );
if ( ! infile ) {
cerr << "ошибка: не могу открыть входной файл: "
<< ifile << endl;
return -1;
}
string ofile = ifile + ".sort";
// сконструировать объект класса ofstream для вывода в файл
ofstream outfile( ofile.c_str() );
if ( ! outfile) {
cerr << "ошибка: не могу открыть выходной файл: "
<< ofile << endl;
return -2;
}
string buffer;
vector< string, allocator > text;
int cnt = 1;
while ( infile >> buffer ) {
text.push_back( buffer );
cout << buffer << (cnt++ % 8 ? " " : "\n" );
}
sort( text.begin(), text.end() );
// выводим отсортированное множество слов в файл
vector< string >::iterator iter = text.begin();
for ( cnt = 1; iter != text.end(); ++iter, ++cnt )
outfile << *iter
<< (cnt % 8 ? " " : "\n" );
return 0;
}
Вот пример сеанса работы с этой программой. Нас просят ввести файл для сортировки. Мы набираем alice_emma (набранные на клавиатуре символы напечатаны полужирным шрифтом). Затем программа направляет на стандартный вывод все, что прочитала из файла:
Введите имя файла для сортировки: alice_emma
Alice Emma has long flowing red hair. Her
Daddy says when the wind blows through her
hair, it looks almost alive, like a fiery
bird in flight. A beautiful fiery bird, he
tells her, magical but untamed. "Daddy, shush, there
is no such creature," she tells him, at
the same time wanting him to tell her
more. Shyly, she asks, "I mean, Daddy, is
there?"
Далее программа выводит в файл outfile отсортированную последовательность строк. Конечно, на порядок слов влияют знаки препинания; в следующем разделе мы это исправим:
"Daddy, "I A Alice Daddy Daddy, Emma Her
Shyly, a alive, almost asks, at beautiful bird
bird, blows but creature," fiery fiery flight. flowing
hair, hair. has he her her her, him
him, in is is it like long looks
magical mean, more. no red same says she
she shush, such tell tells tells the the
there there?" through time to untamed. wanting when
wind
(В разделе 20.6 мы познакомимся с файловым вводом/выводом более подробно.)
Библиотека iostream поддерживает также ввод/вывод в область памяти, при этом поток связывается со строкой в памяти программы. С помощью потоковых операторов ввода/вывода мы можем записывать данные в эту строку и читать их оттуда. Объект для строкового ввода/вывода определяется как экземпляр одного из следующих классов:
istringstream, производный от istream, читает из строки;
ostringstream, производный от ostream, пишет в строку;
stringstream, производный от iostream, выполняет как чтение, так и запись.
Для использования любого из этих классов в программу нужно включить заголовочный файл
#include <sstream>
(Файл sstream уже включает iostream, так что включать оба файла необязательно.) В следующем фрагменте объект класса ostringstream используется для форматирования сообщения об ошибке, которое возвращается вызывающей программе.
#include <sstream>
string program_name( "our_program" );
string version( 0.01 );
// ...
string mumble( int *array, int size )
{
if ( ! array ) {
ostringstream out_message;
out_message << "ошибка: "
<< program_name << "--" << version
<< ": " << __FILE__ << ": " << __LINE__
<< " -- указатель равен 0; "
<< " а должен адресовать массив.\n";
// возвращаем строку, в которой находится сообщение
return out_message.str();
}
// ...
}
(В разделе 20.8 мы познакомимся со строковым вводом/выводом более подробно.)
Потоки ввода/вывода поддерживают два предопределенных типа: char и wchar_t. В этой главе мы расскажем только о чтении и записи в потоки данных типа char. Помимо них, в библиотеке iostream имеется набор классов и объектов для работы с типом wchar_t. Они отличаются от соответствующих классов, использующих тип char, наличием префикса ‘w’. Так, объект стандартного ввода называется wcin, стандартного вывода – wcout, стандартного вывода для ошибок – wcerr. Но набор заголовочных файлов для char и wchar_t один и тот же.
Классы для ввода/вывода данных типа wchar_t называются wostream, wistream, wiostream, для файлового ввода/вывода – wofstream, wifstream, wfstream, а для строкового – wostringstream, wistringstream, wstringstream.
Битовое поле– член, экономящий память
Для хранения заданного числа битов можно объявить член класса специального вида, называемый битовым полем. Он должен иметь целый тип данных, со знаком или без знака:
class File {
// ...
unsigned int modified : 1; // битовое поле
};
После идентификатора битового поля следует двоеточие, а за ним – константное выражение, задающее число битов. К примеру, modified – это поле из одного бита.
Битовые поля, определенные в теле класса подряд, по возможности упаковываются в соседние биты одного целого числа, делая хранение объекта более компактным. Так, в следующем объявлении пять битовых полей будут содержаться в одном числе типа unsigned int, ассоциированном с первым полем mode:
typedef unsigned int Bit;
class File {
public:
Bit mode: 2;
Bit modified: 1;
Bit prot_owner: 3;
Bit prot_group: 3;
Bit prot_world: 3;
// ...
};
Доступ к битовому полю осуществляется так же, как к прочим членам класса. Скажем, к битовому полю, являющемуся закрытым членом класса, можно обратиться лишь из функций-членов и друзей этого класса:
void File::write()
{
modified = 1;
// ...
}
void File::close()
{
if ( modified )
// ... сохранить содержимое
}
Вот простой пример использования битового поля длиной больше 1 (примененные здесь побитовые операции рассматривались в разделе 4.11):
enum { READ = 01, WRITE = 02 }; // режимы открытия файла
int main() {
File myFile;
myFile.mode |= READ;
if ( myFile.mode & READ )
cout << "myFile.mode is set to READ\n";
}
Обычно для проверки значения битового поля-члена определяются встроенные функции-члены. Допустим, в классе File можно ввести члены isRead() и isWrite():
inline int File::isRead() { return mode & READ; }
inline int File::isWrite() { return mode & WRITE; }
if ( myFile.isRead() ) /* ... */
С помощью таких функций-членов битовые поля можно сделать закрытыми членами класса File.
К битовому полю нельзя применять оператор взятия адреса (&), поэтому не может быть и указателя на подобные поля-члены. Кроме того, полю запрещено быть статическим членом.
В стандартной библиотеке C++ имеется шаблон класса bitset, который облегчает манипуляции с битовыми множествами. Мы рекомендуем использовать его вместо битовых полей. (Шаблон класса bitset и определенные в нем операции рассматривались в разделе 4.12.)
Упражнение 13.17
Перепишите примеры из этого подраздела так, чтобы в классе File вместо объявления и прямого манипулирования битовыми полями использовался класс bitset и его операторы.
Благодарности
Особые благодарности, как обычно, мы выражаем Бьерну Страуструпу за прекрасный язык, который он подарил нам, и за то внимание, которое он оказывал ему все эти годы. Особые благодарности членам комитета по стандартизации С++ за их самоотверженность и упорную работу (часто безвозмездную) и за огромный вклад в появление Стандарта С++.
На разных стадиях работы над рукописью многие люди вносили различные полезные замечания: Пол Эбрахамс (Paul Abrahams), Майкл Болл (Michael Ball), Стивен Эдвардс (Stephen Edwards), Кэй Хорстманн (Cay Horstmann), Брайан Керниган (Brian Kernighan), Том Лайонс (Tom Lyons), Роберт Мюррей (Robert Murray), Эд Шейбель (Ed Scheibel), Рой Тэрнер (Roy Turner), Йон Вада (Jon Wada). Особо нам хочется поблагодарить Майкла Болла за важные комментарии и поддержку. Мы благодарим Кловис Тондо (Clovis Tondo) и Брюса Леюнга (Bruce Leung) за вдумчивую рецензию.
Стен выражает особо теплую благодарность Ши-Чюань Хуань (Shyh-Chyuan Huang) и Джинко Гото (Jinko Gotoh) за их помощь в работе над рассказом о Жар-Птице (Firebird), Иона Ваду и, конечно, Джози.
Джози благодарит Габби Зильберман (Gabby Silbermarr), Карен Беннет (Karen Bennet), а также команду Центра углубленных исследований (Centre for Advanced Studies) за поддержку во время написания книги. И выражает огромную благодарность Стену за привлечение к работе над книгой.
Мы оба хотим поблагодарить замечательный редакторский коллектив за их упорную работу и безграничное терпение: Дебби Лафферти (Debbie Lafferty), которая не оставляла вниманием эту книгу с самого первого издания, Майка Хендриксона (Mike Hendrickson) и Джона Фуллера (John Fuller). Компания Big Purple Company проделала замечательную работу по набору книги. Иллюстрация в разделе 6.1 принадлежит Елене Дрискилл (Elena Driskill). Мы благодарим ее за разрешение перепечатки.
Благодарности во втором издании
Эта книга явилась результатом работы множества остающихся за сценой людей, помогавших автору. Наиболее сердечные благодарности мы приносим Барбаре Му (Barbara Moo). Ее поддержка, советы, внимательное чтение бесчисленных черновиков книги просто неоценимы. Особые благодарности Бьярну Страуструпу за постоянную помощь и поддержку и за прекрасный язык, который он подарил нам, а также Стивену Дьюхерсту (Stephen Dewhurst), который так много помогал мне при освоении С++, и Ненси Уилкинсон (Nancy Wilkinson)– коллеге по работе над cfront.
Дэг Брюк (Dag Bruck), Мартин Кэрролл (Martin Carroll), Уильям Хопкинс (William Hopkins), Брайан Керниган (Brian Kernighan), Эндрю Кениг (Andrew Koenig), Алексис Лейтон (Alexis Layton) и Барбара Му (Barbara Moo) помогали нам особо ценными замечаниями. Их рецензии значительно улучшили качество книги. Энди Бейли (Andy Baily), Фил Браун (Phil Brown), Джеймс Коплиен (James Coplien), Элизабет Флэнаган (Elizabeth Flanagan), Дэвид Джордан (David Jordan), Дон Кретч (Don Kretsch), Крейг Рубин (Craig Rubin), Джонатан Шопиро (Jonathan Shopiro), Джуди Уорд (Judy Ward), Ненси Уилкинсон (Nancy Wilkinson) и Клей Уилсон (Clay Wilson) просмотрели множество черновиков книги и дали много полезных комментариев. Дэвид Проссер (David Prosser) прояснил множество вопросов, касающихся ANSI C.
Джерри Шварц (Jerry Schwarz), автор библиотеки iostream, обеспечил нас оригинальной документацией, которая легла в основу Приложения А (глава 20 в третьем издании). Мы высоко оцениваем его замечания к этому Приложению. Мы благодарим всех остальных членов команды, работавшей на версией 3.0: Лауру Ивс (Laura Eaves), Джорджа Логотетиса (George Logothetis), Джуди Уорд (Judy Ward) и Ненси Уилкинсон (Nancy Wilkinson).
Джеймс Эдкок (James Adcock), Стивен Белловин (Steven Bellovin), Йон Форрест (Jon Forrest), Морис Эрлих (Maurice Herlihy), Норман Керт (Norman Kerth), Даррелл Лонг (Darrell Long), Виктор Миленкович (Victor Milenkovic) и Джастин Смит (Justin Smith) рецензировали книгу для издательства Addison-Wesley.
Дэвид Беккердорф (David Beckedorff), Дэг Брюк (Dag Bruck), Джон Элбридж (John Eldridge), Джим Хьюмелсин (Jim Humelsine), Дэйв Джордан (Dave Jordan), Эми Клейнман (Ami Kleinman), Эндрю Кениг (Andrew Koenig), Тим О'Конски (Tim O'Konski), Кловис Тондо (Clovis Tondo) и Стив Виноски (Steve Vinoski) указали на ошибки в первом издании.
Я выражаю глубокую благодарность Брайану Кернигану (Brian Kernighan) и Эндрю Кенигу (Andrew Koenig) за программные средства для типографского набора текста.
Будущее С++
Во время публикации книги комитет по стандартизации С++ ISO/ANSI закончил техническую работу по подготовке первого международного стандарта С++. Стандарт опубликован Международным комитетом по стандартизации (ISO) летом 1998 года.
Реализации С++, поддерживающие стандарт, должны появиться вскоре после его публикации. Есть надежда, что после публикации стандарта изменения в С++ перестанут быть столь радикальными. Такая стабильность позволит создать сложные библиотеки, написанные на стандартном С++ и направленные на решение различных промышленных задач. Таким образом, основной рост в мире С++ ожидается в сфере создания библиотек.
После публикации стандарта комиссия тем не менее продолжает свою работу, хотя и не так интенсивно. Разбираются поступающие от пользователей вопросы по интерпретации тех или иных особенностей языка. Это приводит к небольшим исправлениям и уточнениям стандарта С++. При необходимости международный стандарт будет пересматриваться каждые пять лет, чтобы учесть изменения в технологиях и нужды отрасли.
Что будет через пять лет после публикации стандарта, пока неизвестно. Возможно, новые компоненты из прикладных библиотек войдут в стандартную библиотеку С++. Но сейчас, после окончания работы комиссии, судьба С++ оказывается в руках его пользователей.
Частичные специализации шаблонов классов *
Если у шаблона класса есть несколько параметров, то можно специализировать его только для одного или нескольких аргументов, оставляя другие неспециализированными. Иными словами, допустимо написать шаблон, соответствующий общему во всем, кроме тех параметров, вместо которых подставлены фактические типы или значения. Такой механизм носит название частичной специализации шаблона класса. Она может понадобиться при определении реализации, более подходящей для конкретного набора аргументов.
Рассмотрим шаблон класса Screen, введенный в разделе 16.2. Частичная специализации Screen<hi,80> дает более эффективную реализацию для экранов с 80 столбцами:
template <int hi, int wid>
class Screen {
// ...
};
// частичная специализация шаблона класса Screen
template <int hi>
class Screen<hi, 80> {
public:
Screen();
// ...
private:
string _screen;
string::size_type _cursor;
short _height;
// для экранов с 80 колонками используются специальные алгоритмы
};
Частичная специализация шаблона класса – это шаблон, и ее определение похоже на определение шаблона. Оно начинается с ключевого слова template, за которым следует список параметров, заключенный в угловые скобки. Список параметров здесь отличается от соответствующего списка параметров общего шаблона. Для частичной специализации шаблона Screen есть только один параметр-константа hi, поскольку значение второго аргумента равно 80, т.е. в данном списке представлены только те параметры, для которых фактические аргументы еще неизвестны.
Имя частичной специализации совпадает с именем того общего шаблона, которому она соответствует, в нашем случае Screen. Однако за ее именем всегда следует список аргументов. В примере выше этот список выглядит как <hi,80>. Поскольку значение аргумента для первого параметра шаблона неизвестно, то на этом месте в списке стоит имя параметра шаблона; вторым же аргументом является значение 80, которым частично специализирован шаблон.
Частичная специализация шаблона класса неявно конкретизируется при использовании в программе. В следующем примере частичная специализация конкретизируется аргументом шаблона 24 вместо hi:Screen<24,80> hp2621;
Обратите внимание, что экземпляр Screen<24,80> может быть конкретизирован не только из частично специализированного, но и из общего шаблона. Почему же тогда компилятор остановился именно на частичной специализации? Если для шаблона класса объявлены частичные специализации, компилятор выбирает то определение, которое является наиболее специализированным для заданных аргументов. Если же ни одно из них не подходит, используется общее определение шаблона. Например, при конкретизации экземпляра Screen<40,132> соответствующей аргументам шаблона специализации нет. Наш вариант применяется только для конкретизации типа Screen с 80 колонками.
Определение частичной специализации не связано с определением общего шаблона. У него может быть совершенно другой набор членов, а также собственные определения функций-членов, статических членов и вложенных типов. Содержащиеся в общем шаблоне определения членов никогда не употребляются для конкретизации членов его частичной специализации. Например, для частичной специализации Screen<hi,80> должен быть определен свой конструктор:
// конструктор для частичной специализации Screen<hi,80>
template <int hi>
Screen<hi,80>::Screen() : _height( hi ), _cursor( 0 ),
_screen( hi * 80, bk )
{ }
Если для конкретизации некоторого класса применяется частичная специализация, то определение конструктора из общего шаблона не используется даже тогда, когда определение конструктора Screen<hi,80> отсутствует.
Численные алгоритмы
Следующие четыре алгоритма реализуют численные операции с контейнером. Для их использования необходимо включить заголовочный файл <numeric>.
accumulate(), partial_sum(), inner_product(), adjacent_difference()
Чисто виртуальные функции
С точки зрения кодирования основная задача, стоящая перед нами в связи с поддержкой пользовательских запросов,– это реализация зависимых от типа операций для каждого из возможных операторов. Для этого мы определили четыре конкретных типа классов: AndQuery, OrQuery и т.д. Однако с точки зрения проектирования наша цель – инкапсулировать обработку каждого вида запроса, спрятать за не зависящим от типа интерфейсом. Это позволит построить ядро приложения, которое не потребует изменений при добавлении или удалении типов.
Чтобы добиться этого, определим абстрактный тип класса Query. При этом мы не будем программировать разные типы пользовательских запросов, а лишь абстрактные операции, применимые к ним:
void doit_and_bedone( vector< Query* > *pvec )
{
vector<Query*>::iterator
it = pvec->begin(),
end_it = pvec->end();
for ( ; it != end_it; ++it )
{
Query *pq = *it;
cout << "обрабатывается " << *pq << endl;
pq->eval();
pq->display();
delete pq;
}
}
Такое определение позволяет добавлять неограниченное число типов запросов без необходимости изменять или даже перекомпилировать ядро системы, но при условии, что открытый интерфейс нашего абстрактного базового класса Query достаточен для поддержки новых запросов.
Проектируя открытый интерфейс Query, мы определим множество операций, достаточное для поддержки всех существующих и будущих типов запросов, хотя на практике нам вряд ли удастся это гарантировать. Предоставление общего интерфейса для тех запросов, о которых мы уже знаем, – вполне реальная задача, но любое заявление, претендующее на более широкую поддержку, следует рассматривать с долей скептицизма.
Поскольку Query – абстрактный класс, объекты которого в приложении не создаются, то никакой разумной реализации виртуальных функций в нем самом мы предложить не можем. Это лишь названия, которые должны быть замещены в производных классах. Напрямую вызывать их мы не будем.
Язык обладает синтаксической конструкцией, обозначающей, что некоторая виртуальная функция предоставляет интерфейс, который должен быть замещен в производных подтипах, но вызываться непосредственно не может. Это чисто виртуальные функции. Объявляются они следующим образом:
class Query {
public:
// объявляется чисто виртуальная функция
virtual ostream& print( ostream&=cout ) const = 0;
// ...
};
Заметьте, что за объявлением функции следует присваивание нуля.
Класс, содержащий (или наследующий) одну или несколько таких функций, распознается компилятором как абстрактный базовый класс. Попытка создать независимый объект абстрактного класса приводит к ошибке компиляции. (Ошибкой является также вызов чисто виртуальной функции с помощью механизма виртуализации.) Например:
// В классе Query объявлены одна или несколько виртуальных функций,
// поэтому программист не может создавать независимые объекты
// класса Query
// правильно: подобъект Query в составе NameQuery
Query *pq = new NameQuery( "Nostromo" );
// ошибка: оператор new создает объект класса Query
Query *pq2 = new Query;
Абстрактный базовый класс может существовать только как подобъект в составе объекта некоторого производного от него класса. Это именно та семантика, которая нужна нам для базового Query.
