Абстрактные контейнерные типы
В этой главе мы продолжим рассмотрение типов данных, начатое в главе 3, представим дополнительную информацию о классах vector и string и познакомимся с другими контейнерными типами, входящими в состав стандартной библиотеки С++. Мы также расскажем об операторах и выражениях, упомянутых в главе 4, сосредоточив внимание на тех операциях, которые поддерживаются объектами контейнерных типов.
Последовательный контейнер содержит упорядоченный набор элементов одного типа. Можно выделить два основных типа контейнеров – вектор (vector) и список (list). (Третий последовательный контейнер – двусторонняя очередь (deque) – обеспечивает ту же функциональность, что и vector, но особенно эффективно реализует операции вставки и удаления первого элемента. deque
следует применять, например, при реализации очереди, из которой извлекается только первый элемент. Все сказанное ниже относительно вектора применимо также и к deque.)
Ассоциативный контейнер эффективно реализует операции проверки существования и извлечения элемента. Два основных ассоциативных контейнера – это отображение (map) и множество (set). map
состоит из пар ключ/значение, причем ключ используется для поиска элемента, а значение содержит хранимую информацию. Телефонный справочник хорошо иллюстрирует понятие отображения: ключом является фамилия и имя абонента, а значением – его телефонный номер.
Элемент контейнера set
содержит только ключ, поэтому set эффективно реализует операцию проверки его существования. Этот контейнер можно применить, например, при реализации системы текстового поиска для хранения списка так называемых стоп-слов – слов, не используемых при поиске, таких, как и, или, не, так и тому подобных. Программа обработки текста считывает каждое слово и проверяет, есть ли оно в указанном списке. Если нет, то слово добавляется в базу данных.
В контейнерах map и set не может быть дубликатов – повторяющихся ключей. Для поддержки дубликатов существуют контейнеры multimap и multiset. Например, multimap
можно использовать при реализации такого телефонного справочника, в котором содержится несколько номеров одного абонента.
В последующих разделах мы детально рассмотрим контейнерные типы и разработаем небольшую программу текстового поиска.
Абстрактные контейнерные типы в качестве параметров
Абстрактные контейнерные типы, представленные в главе 6, также используются для объявления параметров функции. Например, можно определить putValues() как имеющую параметр типа vector<int>
вместо встроенного типа массива.
Контейнерный тип является классом и обеспечивает значительно большую функциональность, чем встроенные массивы. Так, vector<int>
“знает” собственный размер. В предыдущем подразделе мы видели, что размер параметра-массива неизвестен функции и для его передачи приходится задавать дополнительный параметр. Использование vector<int>
позволяет обойти это ограничение. Например, можно изменить определение нашей putValues() на такое:
|
#include <iostream> #include <vector> const lineLength =12; // количество элементов в строке void putValues( vector<int> vec ) { cout << "( " << vec.size() << " )< "; for ( int i = 0; i < vec.size(); ++1 ) { if ( i % lineLength == 0 && i ) cout << "\n\t"; // строка заполнена cout << vec[ i ]; // разделитель, печатаемый после каждого элемента, // кроме последнего if ( 1 % lineLength != lineLength-1 && i != vec.size()-1 ) cout << ", "; } cout << " >\n"; |
}
Функция main(), вызывающая нашу новую функцию putValues(), выглядит так:
|
void putValues( vector<int> ); int main() { int i, j[ 2 ]; // присвоить i и j некоторые значения vector<int> vec1(1); // создадим вектор из 1 элемента vecl[0] = i; putValues( vecl ); vector<int> vec2; // создадим пустой вектор // добавим элементы к vec2 for ( int ix = 0; ix < sizeof( j ) / sizeof( j[0] ); ++ix ) // vec2[ix] == j [ix] vec2.push_back( j[ix] ); putValues( vec2 ); return 0; |
}
Заметим, что параметр putValues()передается по значению. В подобных случаях контейнер со всеми своими элементами всегда копируется в стек вызванной функции. Поскольку операция копирования весьма неэффективна, такие параметры лучше объявлять как ссылки.
Как бы вы изменили объявление putValues()?
Вспомним, что если функция не модифицирует значение своего параметра, то предпочтительнее, чтобы он был ссылкой на константный тип:
void putValues( const vector<int> & ) { ...
Адаптеры функций для объектов-функций
В стандартной библиотеке имеется также ряд адаптеров функций, предназначенных для специализации и расширения как унарных, так и бинарных объектов-функций. Адаптеры– это специальные классы, разбитые на следующие две категории:
· связыватели (binders). Это адаптеры, преобразующие бинарный объект-функцию в унарный объект, связывая один из аргументов с конкретным значением. Например, для подсчета в контейнере всех элементов, которые меньше или равны 10, следует передать алгоритму count_if()
объект-функцию less_equal, один из аргументов которого равен 10. В следующем разделе мы покажем, как это сделать;
· отрицатели (negators). Это адаптеры, изменяющие значение истинности объекта-функции на противоположное. Например, для подсчета всех элементов внутри контейнера, которые больше 10, мы могли бы передать алгоритму count_if()
отрицатель объекта-функции less_equal, один из аргументов которого равен 10. Конечно, в данном случае проще передать связыватель объекта-функции greater, ограничив один из аргументов со значением 10.
В стандартную библиотеку входит два предопределенных адаптера-связывателя: bind1st и bind2nd, причем bind1st
связывает некоторое значение с первым аргументом бинарного объекта-функции, а bind2nd – со вторым. Например, для подсчета внутри контейнера всех элементов, которые меньше или равны 10, мы могли бы передать алгоритму count_if() следующее:
|
count_if( vec.begin(), vec.end(), |
bind2nd( less_equal<int>(), 10 ));
В стандартной библиотеке также есть два предопределенных адаптера-отрицателя: not1 и not2. not1 инвертирует значение истинности унарного предиката, являющегося объектом-функцией, а not2 – значение бинарного предиката. Для отрицания рассмотренного выше связывателя объекта-функции less_equal
можно написать следующее:
|
count_if( vec.begin(), vec.end(), |
not1( bind2nd( less_equal<int>(), 10 )));
Другие примеры использования связывателей и отрицателей приведены в Приложении, вместе с примерами использования каждого алгоритма.
Алгоритм accumulate()
|
template < class InputIterator, class Type > Type accumulate( InputIterator first, InputIterator last, Type init ); template < class InputIterator, class Type, class BinaryOperation > Type accumulate( InputIterator first, InputIterator last, |
Type init, BinaryOperation op );
Первый вариант accumulate()
вычисляет сумму значений элементов последовательности из диапазона, ограниченного парой итераторов [first,last), с начальным значением, которое задано параметром init. Например, если дана последовательность {1,1,2,3,5,8} и начальное значение 0, то результатом работы алгоритма будет 20. Во втором варианте вместо оператора сложения к элементам применяется переданная бинарная операция. Если бы мы передали алгоритму accumulate()
объект-функцию times<int> и начальное значение 1, то получили бы результат 240. accumulate() – это один из численных алгоритмов; для его использования в программу необходимо включить заголовочный файл <numeric>.
|
#include <numeric> #include <list> #include <functional> #include <iostream.h> /* * выход: * accumulate() * работает с последовательностью {1,2,3,4} * результат для сложения по умолчанию: 10 * результат для объекта-функции plus<int>: 10 */ int main() { int ia[] = { 1, 2, 3, 4 }; list<int,allocator> ilist( ia, ia+4 );
int ia_result = accumulate(&ia[0], &ia[4], 0); int ilist_res = accumulate( ilist.begin(), ilist.end(), 0, plus<int>() ); cout << "accumulate()\n\t" << "работает с последовательностью {1,2,3,4}\n\t" << "результат для сложения по умолчанию: " << ia_result << "\n\t" << "результат для объекта-функции plus<int>: " << ilist_res << endl;
return 0; |
}
Алгоритм adjacent_difference()
|
template < class InputIterator, class OutputIterator > OutputIterator adjacent_difference( InputIterator first, InputIterator last, OutputIterator result ); template < class InputIterator, class OutputIterator > class BinaryOperation > OutputIterator adjacent_difference( InputIterator first, InputIterator last, |
OutputIterator result, BinaryOperation op );
Первый вариант adjacent_difference()
создает новую последовательность, в которой значение каждого элемента, кроме первого, равно разности между текущим и предыдущим элементами исходной последовательности. Например, если дано {0,1,1,2,3,5,8}, то первым элементом новой последовательности будет копия: 0. Вторым – разность первых двух элементов исходной последовательности: 1. Третий элемент равен разности третьего и второго элементов: 1?1=0, и т.д. В результате мы получим последовательность {0,1,0,1,1,2,3}.
Во втором варианте разность соседних элементов вычисляется с помощью указанной бинарной операции. Возьмем ту же исходную последовательность и передадим объект-функцию times<int>. Как и раньше, первый элемент просто копируется. Второй элемент – это произведение первого и второго элементов исходной последовательности; он тоже равен 0. Третий элемент – произведение второго и третьего элементов исходной последовательности: 1 * 1 = 1, и т.д. Результат – {0,1,2,6,15,40}.
В обоих вариантах итератор OutputIterator
указывает на элемент, расположенный за последним элементом новой последовательности. adjacent_difference() – это один из численных алгоритмов, для его использования в программу необходимо включить заголовочный файл <numeric>.
|
#include <numeric> #include <list> #include <functional> #include <iterator> #include <iostream.h> int main() { int ia[] = { 1, 1, 2, 3, 5, 8 }; list<int,allocator> ilist(ia, ia+6); list<int,allocator> ilist_result(ilist.size()); adjacent_difference(ilist.begin(), ilist.end(), ilist_result.begin() );
// на выходе печатается: // 1 0 1 1 2 3 copy( ilist_result.begin(), ilist_result.end(), ostream_iterator<int>(cout," ")); cout << endl; adjacent_difference(ilist.begin(), ilist.end(), ilist_result.begin(), times<int>() ); // на выходе печатается: // 1 1 2 6 15 40 copy( ilist_result.begin(), ilist_result.end(), ostream_iterator<int>(cout," ")); cout << endl; |
}
Алгоритм adjacent_find()
|
template < class ForwardIterator > ForwardIterator adjacent_find( ForwardIterator first, ForwardIterator last ); template < class ForwardIterator, class BinaryPredicate > ForwardIterator adjacent_find( ForwardIterator first, |
ForwardIterator last, Predicate pred );
adjacent_find()
ищет первую пару одинаковых соседних элементов в диапазоне, ограниченном итераторами [first,last). Если соседние дубликаты найдены, то алгоритм возвращает однонаправленный итератор, указывающий на первый элемент пары, в противном случае возвращается last.
Например, если дана последовательность {0,1,1,2,2,4}, то будет найдена пара [1,1] и возвращен итератор, указывающий на первую единицу.
|
#include <algorithm> #include <vector> #include <iostream.h> #include <assert.h>
class TwiceOver { public: bool operator() ( int val1, int val2 ) { return val1 == val2/2 ? true : false; } };
int main() { int ia[] = { 1, 4, 4, 8 }; vector< int, allocator > vec( ia, ia+4 ); int *piter; vector< int, allocator >::iterator iter;
// piter указывает на ia[1] piter = adjacent_find( ia, ia+4 ); assert( *piter == ia[ 1 ] );
// iter указывает на vec[2] iter = adjacent_find( vec.begin(), vec.end(), TwiceOver() ); assert( *iter == vec[ 2 ] ); // пришли сюда: все хорошо cout << "ok: adjacent-find() завершился успешно!\n";
return 0; |
}
Алгоритм binary_search()
|
template < class ForwardIterator, class Type > bool binary_search( ForwardIterator first, ForwardIterator last, const Type &value ); template < class ForwardIterator, class Type > bool binary_search( ForwardIterator first, ForwardIterator last, const Type &value, |
Compare comp );
binary_search()
ищет значение value в отсортированной последовательности, ограниченной парой итераторов [first,last). Если это значение найдено, возвращается true, иначе – false. В первом варианте предполагается, что контейнер отсортирован с помощью оператора “меньше”. Во втором варианте порядок определяется указанным объектом-функцией.
|
#include <algorithm> #include <vector> #include <assert.h> int main() { int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40}; vector< int, allocator > vec( ia, ia+12 ); sort( &ia[0], &ia[12] ); bool found_it = binary_search( &ia[0], &ia[12], 18 ); assert( found_it == false ); vector< int > vec( ia, ia+12 ); sort( vec.begin(), vec.end(), greater<int>() ); found_it = binary_search( vec.begin(), vec.end(), 26, greater<int>() ); assert( found_it == true ); |
}
Алгоритм copy()
|
template < class InputIterator, class OutputIterator > OutputIterator copy( InputIterator first1, InputIterator last, |
OutputIterator first2 )
copy()
копирует последовательность элементов, ограниченную парой итераторов [first,last), в другой контейнер, начиная с позиции, на которую указывает first2. Алгоритм возвращает итератор, указывающий на элемент второго контейнера, следующий за последним вставленным. Например, если дана последовательность {0,1,2,3,4,5}, мы можем сдвинуть элементы на один влево с помощью такого вызова:
|
int ia[] = {0, 1, 2, 3, 4, 5 }; // сдвинуть элементы влево на один, получится {1,2,3,4,5,5} |
copy( ia+1, ia+6, ia );
copy()
начинает копирование со второго элемента ia, копируя 1 в первую позицию, и так далее, пока каждый элемент не окажется в позиции на одну левее исходной.
|
#include <algorithm> #include <vector> #include <iterator> #include <iostream.h> /* печатается: 0 1 1 3 5 8 13 сдвиг массива влево на 1: 1 1 3 5 8 13 13 сдвиг вектора влево на 2: 1 3 5 8 13 8 13 */ int main() { int ia[] = { 0, 1, 1, 3, 5, 8, 13 }; vector< int, allocator > vec( ia, ia+7 ); ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность элементов:\n"; copy( vec.begin(), vec.end(), ofile ); cout << '\n'; // сдвиг влево на один элемент copy( ia+1, ia+7, ia ); cout << "сдвиг массива влево на 1:\n"; copy( ia, ia+7, ofile ); cout << '\n'; // сдвиг влево на два элемента copy( vec.begin()+2, vec.end(), vec.begin() );
cout << "сдвиг вектора влево на 2:\n"; copy( vec.begin(), vec.end(), ofile ); cout << '\n'; |
}
Алгоритм copy_backward()
|
template < class BidirectionalIterator1, class BidirectionalIterator2 > BidirectionalIterator2 copy_backward( BidirectionalIterator1 first, BidirectionalIterator1 last1, |
BidirectionalIterator2 last2 )
copy_backward()
ведет себя так же, как copy(), только элементы копируются в обратном порядке: копирование начинается с last1-1 и продолжается до first. Кроме того, элементы помещаются в целевой контейнер с конца, от позиции last2-1, пока не будет скопировано last1-first элементов.
Например, если дана последовательность {0,1,2,3,4,5}, мы можем скопировать последние три элемента (3,4,5) на место первых трех (0,1,2), установив first
равным адресу значения 0, last1– адресу значения 3, а last2 – адресу значения 5. Тогда элемент 5 попадает на место элемента 2, элемент 4 – на место 1, а элемент 3 – на место 0. В результате получим последовательность {3,4,5,3,4,5}.
|
#include <algorithm> #include <vector> #include <iterator> #include <iostream.h> 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; /* печатается: исходный список строк: The light untonsured hair grained and hued like pale oak после copy_backward( begin+1, end-3, end ): The light untonsured hair light untonsured hair grained and hued */ int main() { string sa[] = { "The", "light", "untonsured", "hair", "grained", "and", "hued", "like", "pale", "oak" }; vector< string, allocator > svec( sa, sa+10 ); cout << "исходный список строк:\n\t"; for_each( svec.begin(), svec.end(), print_elements() ); cout << "\n\n"; copy_backward( svec.begin()+1, svec.end()-3, svec.end() ); print_elements::reset_line_cnt(); cout << "после copy_backward( begin+1, end-3, end ):\n"; for_each( svec.begin(), svec.end(), print_elements() ); cout << "\n"; |
}
Алгоритм count()
|
template < class InputIterator, class Type > iterator_traits<InputIterator>::distance_type count( InputIterator first, |
InputIterator last, const Type& value );
count()
сравнивает каждый элемент со значением value в диапазоне, ограниченном парой итераторов [first,last), с помощью оператора равенства. Алгоритм возвращает число элементов, равных value. (Отметим, что в имеющейся у нас реализации стандартной библиотеки поддерживается более ранняя спецификация count().)
|
#include <algorithm> #include <string> #include <list> #include <iterator> #include <assert.h> #include <iostream.h> #include <fstream.h> /*********************************************************************** * прочитанный текст: 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 thing," she tells him, at the same time wanting him to tell her more. Shyly, she asks, "I mean, Daddy, is there?" ************************************************************************ * программа выводит: * count(): fiery встречается 2 раз(а) ************************************************************************ */ int main() { ifstream infile( "alice_emma" ); assert ( infile != 0 ); list<string,allocator> textlines; typedef list<string,allocator>::difference_type diff_type; istream_iterator< string, diff_type > instream( infile ), eos; copy( instream, eos, back_inserter( textlines )); string search_item( "fiery" ); /********************************************************************* * примечание: ниже показан интерфейс count(), принятый в * стандартной библиотеке. В текущей реализации библиотеки * от RogueWave поддерживается более ранняя версия, в которой * типа distance_type еще не было, так что count() * возвращала результат в последнем аргументе * * вот как должен выглядеть вызов: * * typedef iterator_traits<InputIterator>:: * distance_type dis_type; * * dis_type elem_count; * elem_count = count( textlines.begin(), textlines.end(), * search_item ); ***********************************************************************
int elem_count = 0; list<string,allocator>::iterator ibegin = textlines.begin(), iend = textlines.end(); // устаревшая форма count() count( ibegin, iend, search_item, elem_count ); cout << "count(): " << search_item << " встречается " << elem_count << " раз(а)\n"; |
}
Алгоритм count_if()
|
template < class InputIterator, class Predicate > iterator_traits<InputIterator>::distance_type count_if( InputIterator first, |
InputIterator last, Predicate pred );
count_if()
применяет предикат pred к каждому элементу из диапазона, ограниченного парой итераторов [first,last). Алгоритм сообщает, сколько раз предикат оказался равным true.
|
#include <algorithm> #include <list> #include <iostream.h>
class Even { public: bool operator()( int val ) { return val%2 ? false : true; } };
int main() { int ia[] = {0,1,1,2,3,5,8,13,21,34}; list< int,allocator > ilist( ia, ia+10 ); /* * не поддерживается в текущей реализации ***************************************************** typedef iterator_traits<InputIterator>::distance_type distance_type;
distance_type ia_count, list_count;
// счетчик четных элементов: 4 ia_count = count_if( &ia[0], &ia[10], Even() ); list_count = count_if( ilist.begin(), ilist_end(), bind2nd(less<int>(),10) ); ****************************************************** */ int ia_count = 0; count_if( &ia[0], &ia[10], Even(), ia_count ); // печатается: // count_if(): есть 4 четных элемент(а). cout << "count_if(): есть " << ia_count << " четных элемент(а).\n"; int list_count = 0; count_if( ilist.begin(), ilist.end(), bind2nd(less<int>(),10), list_count ); // печатается: // count_if(): есть 7 элемент(ов), меньших 10. cout << "count_if(): есть " << list_count << " элемент(ов), меньших 10.\n"; |
}
Алгоритм equal()
|
template< class InputIterator1, class InputIterator2 > bool equal( InputIterator1 first1, InputIterator1 last, InputIterator2 first2 ); template< class InputIterator1, class InputIterator2, class BinaryPredicate > bool equal( InputIterator1 first1, InputIterator1 last, |
InputIterator2 first2, BinaryPredicate pred );
equal()
возвращает true, если обе последовательности одинаковы в диапазоне, ограниченном парой итераторов [first,last). Если вторая последовательность содержит дополнительные элементы, они игнорируются. Чтобы убедиться в тождественности данных последовательностей, необходимо написать:
|
if ( vec1.size() == vec2.size() && |
equal( vec1.begin(), vec1.end(), vec2.begin() );
или воспользоваться оператором равенства, определенном в классе самого контейнера: vec1 == vec2. Если второй контейнер содержит меньше элементов, чем первый, и алгоритму приходится просматривать элементы за концом контейнера, то поведение программы не определено. По умолчанию для сравнения применяется оператор равенства в классе элементов контейнера, а во втором варианте алгоритма – указанный предикат pred.
|
#include <algorithm> #include <list> #include <iostream.h>
class equal_and_odd{ public: bool operator()( int val1, int val2 ) { return ( val1 == val2 && ( val1 == 0 || val1 % 2 )) ? true : false; } }; int main() { int ia[] = { 0,1,1,2,3,5,8,13 }; int ia2[] = { 0,1,1,2,3,5,8,13,21,34 }; bool res;
// true: обе последовательности совпадают до длины ia // печатается: int ia[7] равно int ia2[9]? Да. res = equal( &ia[0], &ia[7], &ia2[0] ); cout << "int ia[7] равно int ia2[9]? " << ( res ? "Да" : "Нет" ) << ".\n";
list< int, allocator > ilist( ia, ia+7 ); list< int, allocator > ilist2( ia2, ia2+9 );
// печатается: список ilist равен ilist2? Да. res = equal( ilist.begin(), ilist.end(), ilist2.begin() ); cout << "список ilist равен ilist2? " << ( res ? "Да" : "Нет" ) << ".\n"; // false: 0, 2, 8 не являются равными и нечетными // печатается: список ilist equal_and_odd() ilist2? Нет. res = equal( ilist.begin(), ilist.end(), ilist2.begin(), equal_and_odd() ); cout << "список ilist equal_and_odd() ilist2? " << ( res ? "Да" : "Нет" ) << ".\n";
return 0; |
}
Алгоритм equal_range()
|
template< class ForwardIterator, class Type > pair< ForwardIterator, ForwardIterator > equal_range( ForwardIterator first, ForwardIterator last, const Type &value ); template< class ForwardIterator, class Type, class Compare > pair< ForwardIterator, ForwardIterator > equal_range( ForwardIterator first, ForwardIterator last, const Type &value, |
Compare comp );
equal_range()
возвращает пару итераторов: первый представляет значение итератора, возвращаемое алгоритмом lower_bound(), второй – алгоритмом upper_bound(). (О семантике этих алгоритмов рассказано в их описаниях.) Например, дана последовательность:
int ia[] = {12,15,17,19,20,22,23,26,29,35,40,51};
Обращение к equal_range() со значением 21
возвращает пару итераторов, в которой оба указывают на значение 22. Обращение же со значением 22 возвращает пару итераторов, где first
указывает на 22, а second – на 23. В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера; во втором – предикат comp.
|
#include <algorithm> #include <vector> #include <utility> #include <iostream.h> /* печатается: последовательность элементов массива после сортировки: 12 15 17 19 20 22 23 26 29 35 40 51 результат equal_range при поиске значения 23: *ia_iter.first: 23 *ia_iter.second: 26 результат equal_range при поиске отсутствующего значения 21: *ia_iter.first: 22 *ia_iter.second: 22 последовательность элементов вектора после сортировки: 51 40 35 29 26 23 22 20 19 17 15 12 результат equal_range при поиске значения 26: *ivec_iter.first: 26 *ivec_iter.second: 23 результат equal_range при поиске отсутствующего значения 21: *ivec_iter.first: 20 *ivec_iter.second: 20 */ int main() { int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 }; vector< int, allocator > ivec( ia, ia+12 ); ostream_iterator< int > ofile( cout, " " ); sort( &ia[0], &ia[12] ); cout << "последовательность элементов массива после сортировки:\n"; copy( ia, ia+12, ofile ); cout << "\n\n"; pair< int*,int* > ia_iter; ia_iter = equal_range( &ia[0], &ia[12], 23 ); cout << "результат equal_range при поиске значения 23:\n\t" << "*ia_iter.first: " << *ia_iter.first << "\t" << "*ia_iter.second: " << *ia_iter.second << "\n\n";
ia_iter = equal_range( &ia[0], &ia[12], 21 ); cout << "результат equal_range при поиске " << "отсутствующего значения 21:\n\t" << "*ia_iter.first: " << *ia_iter.first << "\t" << "*ia_iter.second: " << *ia_iter.second << "\n\n";
sort( ivec.begin(), ivec.end(), greater<int>() ); cout << "последовательность элементов вектора после сортировки:\n"; copy( ivec.begin(), ivec.end(), ofile ); cout << "\n\n";
typedef vector< int, allocator >::iterator iter_ivec; pair< iter_ivec, iter_ivec > ivec_iter; ivec_iter = equal_range( ivec.begin(), ivec.end(), 26, greater<int>() );
cout << "результат equal_range при поиске значения 26:\n\t" << "*ivec_iter.first: " << *ivec_iter.first << "\t" << "*ivec_iter.second: " << *ivec_iter.second << "\n\n"; ivec_iter = equal_range( ivec.begin(), ivec.end(), 21, greater<int>() ); cout << "результат equal_range при поиске отсутствующего значения 21:\n\t" << "*ivec_iter.first: " << *ivec_iter.first << "\t" << "*ivec_iter.second: " << *ivec_iter.second << "\n\n"; |
}
Алгоритм fill()
|
template< class ForwardIterator, class Type > void fill( ForwardIterator first, |
ForwardIterator last, const Type& value );
fill()
помещает копию значения value в каждый элемент диапазона, ограниченного парой итераторов [first,last).
|
#include <algorithm> #include <list> #include <string> #include <iostream.h> /* печатается: исходная последовательность элементов массива: 0 1 1 2 3 5 8 массив после fill(ia+1,ia+6): 0 9 9 9 9 9 8 исходная последовательность элементов списка: c eiffel java ada perl список после fill(++ibegin,--iend): c c++ c++ c++ perl */
int main() { const int value = 9; int ia[] = { 0, 1, 1, 2, 3, 5, 8 }; ostream_iterator< int > ofile( cout, " " ); cout << "исходная последовательность элементов массива:\n"; copy( ia, ia+7, ofile ); cout << "\n\n";
fill( ia+1, ia+6, value ); cout << "массив после fill(ia+1,ia+6):\n"; copy( ia, ia+7, ofile ); cout << "\n\n"; string the_lang( "c++" ); string langs[5] = { "c", "eiffel", "java", "ada", "perl" }; list< string, allocator > il( langs, langs+5 ); ostream_iterator< string > sofile( cout, " " ); cout << "исходная последовательность элементов списка:\n"; copy( il.begin(), il.end(), sofile ); cout << "\n\n"; typedef list<string,allocator>::iterator iterator; iterator ibegin = il.begin(), iend = il.end(); fill( ++ibegin, --iend, the_lang ); cout << "список после fill(++ibegin,--iend):\n"; copy( il.begin(), il.end(), sofile ); cout << "\n\n"; |
}
Алгоритм fill_n()
|
template< class ForwardIterator, class Size, class Type > void fill_n( ForwardIterator first, |
Size n, const Type& value );
fill_n()
присваивает count
элементам из диапазона [first,first+count)
значение value.
|
#include <algorithm> #include <vector> #include <string> #include <iostream.h> 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; /* печатается: исходная последовательность элементов массива: 0 1 1 2 3 5 8 массив после fill_n( ia+2, 3, 9 ): 0 1 9 9 9 5 8 исходная последовательность строк: Stephen closed his eyes to hear his boots crush crackling wrack and shells последовательность после применения fill_n(): Stephen closed his xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx crackling wrack and shells */ int main() { int value = 9; int count = 3; int ia[] = { 0, 1, 1, 2, 3, 5, 8 }; ostream_iterator< int > iofile( cout, " " );
cout << "исходная последовательность элементов массива:\n"; copy( ia, ia+7, iofile ); cout << "\n\n"; fill_n( ia+2, count, value ); cout << "массив после fill_n( ia+2, 3, 9 ):\n"; copy( ia, ia+7, iofile ); cout << "\n\n"; string replacement( "xxxxx" ); string sa[] = { "Stephen", "closed", "his", "eyes", "to", "hear", "his", "boots", "crush", "crackling", "wrack", "and", "shells" }; vector< string, allocator > svec( sa, sa+13 ); cout << "исходная последовательность строк:\n\t"; for_each( svec.begin(), svec.end(), print_elements() ); cout << "\n\n"; fill_n( svec.begin()+3, count*2, replacement );
print_elements::reset_line_cnt(); cout << "последовательность после применения fill_n():\n\t"; for_each( svec.begin(), svec.end(), print_elements() ); cout << "\n"; |
}
Алгоритм find()
|
template< class InputIterator, class T > InputIterator find( InputIterator first, |
InputIterator last, const T &value );
Элементы из диапазона, ограниченного парой итераторов [first,last), сравниваются со значением value с помощью оператора равенства, определенного для типа элементов контейнера. Как только соответствие найдено, поиск прекращается. find()
возвращает итератор типа InputIterator, указывающий на найденный элемент; в противном случае возвращается last.
|
#include <algorithm> #include <iostream.h> #include <list> #include <string>
int main() { int array[ 17 ] = { 7,3,3,7,6,5,8,7,2,1,3,8,7,3,8,4,3 };
int elem = array[ 9 ]; int *found_it;
found_it = find( &array[0], &array[17], elem ); // печатается: поиск первого вхождения 1 найдено! cout << "поиск первого вхождения " << elem << "\t" << ( found_it ? "найдено!\n" : "не найдено!\n" ); string beethoven[] = { "Sonata31", "Sonata32", "Quartet14", "Quartet15", "Archduke", "Symphony7" }; string s_elem( beethoven[ 1 ] ); list< string, allocator > slist( beethoven, beethoven+6 ); list< string, allocator >::iterator iter; iter = find( slist.begin(), slist.end(), s_elem ); // печатается: поиск первого вхождения Sonata32 найдено! cout << "поиск первого вхождения " << s_elem << "\t" << ( found_it ? "найдено!\n" : "не найдено!\n" ); |
}
Алгоритм find_end()
|
template< class ForwardIterator1, class ForwardIterator2 > ForwardIterator1 find_end( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 ); template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > ForwardIterator1 find_end( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, |
BinaryPredicate pred );
В последовательности, ограниченной итераторами [first1,last1), ведется поиск последнего вхождения последовательности, ограниченной парой [first2,last2). Например, если первая последовательность – это Mississippi, а вторая – ss, то find_end()
возвращает итератор, указывающий на первую s во втором вхождении ss. Если вторая последовательность не входит в первую, то возвращается last1. В первом варианте используется оператор равенства, определенный для типа элементов контейнера, а во втором – бинарный предикат, переданный пользователем.
|
#include <algorithm> #include <vector> #include <iostream.h> #include <assert.h>
int main() { int array[ 17 ] = { 7,3,3,7,6,5,8,7,2,1,3,7,6,3,8,4,3 }; int subarray[ 3 ] = { 3, 7, 6 };
int *found_it; // find найти последнее вхождение последовательности 3,7,6 // в массив и вернуть адрес первого ее элемента ... found_it = find_end( &array[0], &array[17], &subarray[0], &subarray[3] );
assert( found_it == &array[10] );
vector< int, allocator > ivec( array, array+17 ); vector< int, allocator > subvec( subarray, subarray+3 ); vector< int, allocator >::iterator found_it2; found_it2 = find_end( ivec.begin(), ivec.end(), subvec.begin(), subvec.end(), equal_to<int>() );
assert( found_it2 == ivec.begin()+10 ); cout << "ok: find_end правильно вернула начало " << "последнего вхождения последовательности: 3,7,6!\n"; |
}
Алгоритм find_first_of()
|
template< class ForwardIterator1, class ForwardIterator2 > ForwardIterator1 find_first_of( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 ); template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > ForwardIterator1 find_first_of( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, |
BinaryPredicate pred );
Последовательность, ограниченная парой [first2,last2), содержит элементы, поиск которых ведется в последовательности, ограниченной итераторами [first1,last1). Допустим, нужно найти первую гласную в последовательности символов synesthesia. Для этого определим вторую последовательность как aeiou. find_first_of()
возвращает итератор, указывающий на первое вхождение любого элемента последовательности гласных букв, в данном случае e. Если же первая последовательность не содержит ни одного элемента из второй, то возвращается last1. В первом варианте используется оператор равенства, определенный для типа элементов контейнера, а во втором – бинарный предикат pred.
|
#include <algorithm> #include <vector> #include <string> #include <iostream.h> int main() { string s_array[] = { "Ee", "eE", "ee", "Oo", "oo", "ee" }; // возвращает первое вхождение "ee" -- &s_array[2] string to_find[] = { "oo", "gg", "ee" };
string *found_it = find_first_of( s_array, s_array+6, to_find, to_find+3 ); // печатается: // найдено: ee // &s_array[2]: 0x7fff2dac // &found_it: 0x7fff2dac if ( found_it != &s_array[6] ) cout << "найдено: " << *found_it << "\n\t" << "&s_array[2]:\t" << &s_array[2] << "\n\t" << "&found_it:\t" << found_it << "\n\n";
vector< string, allocator > svec( s_array, s_array+6); vector< string, allocator > svec_find( to_find, to_find+2 );
// возвращает вхождение "oo" -- svec.end()-2 vector< string, allocator >::iterator found_it2; found_it2 = find_first_of( svec.begin(), svec.end(), svec_find.begin(), svec_find.end(), equal_to<string>() ); // печатает: // тоже найдено: oo // &svec.end()-2: 0x100067b0 // &found_it2: 0x100067b0 if ( found_it2 != svec.end() ) cout << "тоже найдено: " << *found_it2 << "\n\t" << "&svec.end()-2:\t" << svec.end()-2 << "\n\t" << "&found_it2:\t" << found_it2 << "\n"; |
}
Алгоритм find_if()
|
template< class InputIterator, class Predicate > InputIterator find_if( InputIterator first, |
InputIterator last, Predicate pred );
К каждому элементу из диапазона [first,last)
последовательно применяется предикат pred. Если он возвращает true, поиск прекращается. find_if()
возвращает итератор типа InputIterator, указывающий на найденный элемент; в противном случае возвращается last.
|
#include <algorithm> #include <list> #include <set> #include <string> #include <iostream.h> // альтернатива оператору равенства // возвращает true, если строка содержится в объекте-члене FriendSet class OurFriends { // наши друзья public: bool operator()( const string& str ) { return ( friendset.count( str )); }
static void FriendSet( const string *fs, int count ) { copy( fs, fs+count, inserter( friendset, friendset.end() )); }
private: static set< string, less<string>, allocator > friendset; };
set< string, less<string>, allocator > OurFriends::friendset; int main() { string Pooh_friends[] = { "Пятачок", "Тигра", "Иа-Иа" }; string more_friends[] = { "Квазимодо", "Чип", "Пятачок" }; list<string,allocator> lf( more_friends, more_friends+3 ); // заполнить список друзей Пуха OurFriends::FriendSet( Pooh_friends, 3 );
list<string,allocator>::iterator our_mutual_friend; our_mutual_friend = find_if( lf.begin(), lf.end(), OurFriends());
// печатается: // Представьте-ка, наш друг Пятачок - также друг Пуха. if ( our_mutual_friend != lf.end() ) cout << "Представьте-ка, наш друг " << *our_mutual_friend << " также друг Пуха.\n";
return 0; |
}
Алгоритм for_each()
|
template< class InputIterator, class Function > Function for_each( InputIterator first, |
InputIterator last, Function func );
for_each()
применяет объект-функцию func к каждому элементу в диапазоне [first,last). func не может изменять элементы, поскольку итератор записи не гарантирует поддержки присваивания. Если же модификация необходима, следует воспользоваться алгоритмом transform(). func
может возвращать значение, но оно игнорируется.
|
#include <algorithm> #include <vector> #include <iostream.h> template <class Type> void print_elements( Type elem ) { cout << elem << " "; }
int main() { vector< int, allocator > ivec; for ( int ix = 0; ix < 10; ix++ ) ivec.push_back( ix );
void (*pfi)( int ) = print_elements; for_each( ivec.begin(), ivec.end(), pfi );
return 0; |
}
Алгоритм generate()
|
template< class ForwardIterator, class Generator > void generate( ForwardIterator first, |
ForwardIterator last, Generator gen );
generate()
заполняет диапазон, ограниченный парой итераторов [first,last), путем последовательного вызова gen, который может быть объектом-функцией или указателем на функцию.
|
#include <algorithm> #include <list> #include <iostream.h>
int odd_by_twos() { static int seed = -1; return seed += 2; } template <class Type> void print_elements( Type elem ) { cout << elem << " "; }
int main() { list< int, allocator > ilist( 10 ); void (*pfi)( int ) = print_elements;
generate( ilist.begin(), ilist.end(), odd_by_twos ); // печатается: // элементы в списке, первый вызов: // 1 3 5 7 9 11 13 15 17 19 cout << "элементы в списке, первый вызов:\n"; for_each( ilist.begin(), ilist.end(), pfi ); generate( ilist.begin(), ilist.end(), odd_by_twos ); // печатается: // элементы в списке, второй вызов: // 21 23 25 27 29 31 33 35 37 39 cout << "\n\nэлементы в списке, второй вызов:\n"; for_each( ilist.begin(), ilist.end(), pfi );
return 0; |
}
Алгоритм generate_n()
|
template< class OutputIterator, class Size, class Generator > void |
generate_n( OutputIterator first, Size n, Generator gen );
generate_n()
заполняет последовательность, начиная с first, n раз вызывая gen, который может быть объектом-функцией или указателем на функцию.
|
#include <algorithm> #include <iostream.h> #include <list>
class even_by_twos { public: even_by_twos( int seed = 0 ) : _seed( seed ){} int operator()() { return _seed += 2; } private: int _seed; }; template <class Type> void print_elements( Type elem ) { cout << elem << " "; } int main() { list< int, allocator > ilist( 10 ); void (*pfi)( int ) = print_elements; generate_n( ilist.begin(), ilist.size(), even_by_twos() ); // печатается: // generate_n с even_by_twos(): // 2 4 6 8 10 12 14 16 18 20 cout << "generate_n с even_by_twos():\n"; for_each( ilist.begin(), ilist.end(), pfi ); cout << "\n"; generate_n( ilist.begin(), ilist.size(), even_by_twos( 100 ) ); // печатается: // generate_n с even_by_twos( 100 ): // 102 104 106 108 110 112 114 116 118 120 cout << "generate_n с even_by_twos( 100 ):\n"; for_each( ilist.begin(), ilist.end(), pfi ); |
}
Алгоритм includes()
|
template< class InputIterator1, class InputIterator2 > bool includes( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2 ); template< class InputIterator1, class InputIterator2, class Compare > bool includes( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, |
Compare comp );
includes()
проверяет, каждый ли элемент последовательности [first1,last1)
входит в последовательность [first2,last2). Первый вариант предполагает, что последовательности отсортированы в порядке, определяемом оператором “меньше”; второй – что порядок задается параметром-типом comp.
|
#include <algorithm> #include <vector> #include <iostream.h>
int main() { int ia1[] = { 13, 1, 21, 2, 0, 34, 5, 1, 8, 3, 21, 34 }; int ia2[] = { 21, 2, 8, 3, 5, 1 };
// алгоритму includes следует передавать отсортированные контейнеры sort( ia1, ia1+12 ); sort( ia2, ia2+6 ); // печатает: каждый элемент ia2 входит в ia1? Да bool res = includes( ia1, ia1+12, ia2, ia2+6 ); cout << "каждый элемент ia2 входит в ia1? " << (res ? "Да" : "Нет") << endl; vector< int, allocator > ivect1( ia1, ia1+12 ); vector< int, allocator > ivect2( ia2, ia2+6 ); // отсортирован в порядке убывания sort( ivect1.begin(), ivect1.end(), greater<int>() ); sort( ivect2.begin(), ivect2.end(), greater<int>() );
res = includes( ivect1.begin(), ivect1.end(), ivect2.begin(), ivect2.end(), greater<int>() ); // печатает: каждый элемент ivect2 входит в ivect1? Да cout << "каждый элемент ivect2 входит в ivect1? " << (res ? "Да" : "Нет") << endl; |
}
Алгоритм inner_product()
|
template< class InputIterator1, class InputIterator2 class Type > Type inner_product( InputIterator1 first1, InputIterator1 last, InputIterator2 first2, Type init ); template< class InputIterator1, class InputIterator2 class Type, class BinaryOperation1, class BinaryOperation2 > Type inner_product( InputIterator1 first1, InputIterator1 last, InputIterator2 first2, Type init, |
BinaryOperation1 op1, BinaryOperation2 op2 );
Первый вариант суммирует произведения соответственных членов обеих последовательностей и прибавляет результат к начальному значению init. Первая последовательность ограничена итераторами [first1,last1), вторая начинается с first2 и обходится синхронно с первой. Например, если даны последовательности {2,3,5,8} и {1,2,3,4}, то результат вычисляется следующим образом:
2*1 + 3*2 + 5*3 + 8*4
Если начальное значение равно 0, алгоритм вернет 55.
Во втором варианте вместо сложения используется бинарная операция op1, а вместо умножения – бинарная операция op1. Например, если для приведенных выше последовательностей применить вычитание в качестве op1 и сложение в качестве op2, то результат будет вычисляться так:
(2+1) - (3+2) - (5+3) - (8+4)
inner_product() – это один из численных алгоритмов. Для его использования в программу необходимо включить заголовочный файл <numeric>.
|
#include <numeric> #include <vector> #include <iostream.h>
int main() { int ia[] = { 2, 3, 5, 8 }; int ia2[] = { 1, 2, 3, 4 }; // перемножить пары элементов из обоих массивов, // сложить и добавить начальное значение: 0 int res = inner_product( &ia[0], &ia[4], &ia2[0], 0 ); // печатает: скалярное произведение массивов: 55 cout << "скалярное произведение массивов: " << res << endl;
vector<int, allocator> vec( ia, ia+4 ); vector<int, allocator> vec2( ia2, ia2+4 ); // сложить пары элементов из обоих векторов, // вычесть из начального значения: 0 res = inner_product( vec.begin(), vec.end(), vec2.begin(), 0, minus<int>(), plus<int>() ); // печатает: скалярное произведение векторов: -28 cout << "скалярное произведение векторов: " << res << endl;
return 0; |
}
Алгоритм inplace_merge()
|
template< class BidirectionalIterator > void inplace_merge( BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last ); template< class BidirectionalIterator, class Compare > void inplace_merge( BidirectionalIterator first, BidirectionalIterator middle, |
BidirectionalIterator last, Compare comp );
inplace_merge()
объединяет две соседние отсортированные последовательности, ограниченные парами итераторов [first,middle) и [middle,last). Результирующая последовательность затирает исходные, начиная с позиции first. В первом варианте для упорядочения элементов используется оператор “меньше”, определенный для типа элементов контейнера, во втором – операция сравнения, переданная программистом.
|
#include <algorithm> #include <vector> #include <iostream.h>
template <class Type> void print_elements( Type elem ) { cout << elem << " "; } /* * печатает: ia разбит на два отсортированных подмассива: 12 15 17 20 23 26 29 35 40 51 10 16 21 41 44 54 62 65 71 74 ia inplace_merge: 10 12 15 16 17 20 21 23 26 29 35 40 41 44 51 54 62 65 71 74 ivec разбит на два отсортированных подвектора: 51 40 35 29 26 23 20 17 15 12 74 71 65 62 54 44 41 21 16 10 ivec inplace_merge: 74 71 65 62 54 51 44 41 40 35 29 26 23 21 20 17 16 15 12 10 */ int main() { int ia[] = { 29,23,20,17,15,26,51,12,35,40, 74,16,54,21,44,62,10,41,65,71 }; vector< int, allocator > ivec( ia, ia+20 ); void (*pfi)( int ) = print_elements; // отсортировать обе подпоследовательности sort( &ia[0], &ia[10] ); sort( &ia[10], &ia[20] );
cout << "ia разбит на два отсортированных подмассива: \n"; for_each( ia, ia+20, pfi ); cout << "\n\n"; inplace_merge( ia, ia+10, ia+20 );
cout << "ia inplace_merge:\n"; for_each( ia, ia+20, pfi ); cout << "\n\n"; sort( ivec.begin(), ivec.begin()+10, greater<int>() ); sort( ivec.begin()+10, ivec.end(), greater<int>() );
cout << "ivec разбит на два отсортированных подвектора: \n"; for_each( ivec.begin(), ivec.end(), pfi ); cout << "\n\n"; inplace_merge( ivec.begin(), ivec.begin()+10, ivec.end(), greater<int>() );
cout << "ivec inplace_merge:\n"; for_each( ivec.begin(), ivec.end(), pfi ); cout << endl; |
}
Алгоритм iter_swap()
|
template< class ForwardIterator1, class ForwardIterator2 > void |
iter_swap( ForwardIterator1 a, ForwardIterator2 b );
iter_swap()
обменивает значения элементов, на которые указывают итераторы a и b.
|
#include <algorithm> #include <list> #include <iostream.h>
int main() { int ia[] = { 5, 4, 3, 2, 1, 0 }; list< int,allocator > ilist( ia, ia+6 );
typedef list< int, allocator >::iterator iterator; iterator iter1 = ilist.begin(),iter2, iter_end = ilist.end(); // отсортировать список "пузырьком" ... for ( ; iter1 != iter_end; ++iter1 ) for ( iter2 = iter1; iter2 != iter_end; ++iter2 ) if ( *iter2 < *iter1 ) iter_swap( iter1, iter2 );
// печатается: // ilist после сортировки "пузырьком" с помощью iter_swap(): // { 0 1 2 3 4 5 } cout << "ilist после сортировки "пузырьком" с помощью iter_swap(): { "; for ( iter1 = ilist.begin(); iter1 != iter_end; ++iter1 ) cout << *iter1 << " "; cout << "}\n"; return 0; |
}
Алгоритм lexicographical_compare()
|
template< class InputIterator1, class InputIterator2 > bool lexicographical_compare( InputIterator1 first1, InputIterator1 last1, InputIterator1 first2, InputIterator2 last2 ); template< class InputIterator1, class InputIterator2, class Compare > bool lexicographical_compare( InputIterator1 first1, InputIterator1 last1, InputIterator1 first2, InputIterator2 last2, |
Compare comp );
lexicographical_compare()
сравнивает соответственные пары элементов из двух последовательностей, ограниченных диапазонами [first1,last1) и [first2,last2). Сравнение продолжается, пока не будет найдена первая пара различных элементов, не достигнута пара [last1,last2] или хотя бы один из элементов last1 или last2
(если последовательности имеют разные длины). При обнаружении первой пары различных элементов алгоритм возвращает:
· если меньше элемент первой последовательности, то true, иначе false;
· если last1
достигнут, а last2
нет, то true;
· если last2
достигнут, а last1
нет, то false;
· если достигнуты и last1, и last2
(т.е. все элементы одинаковы), то false. Иными словами, первая последовательность лексикографически не меньше второй.
Например, даны такие последовательности:
|
string arr1[] = { "Piglet", "Pooh", "Tigger" }; |
string arr2[] = { "Piglet", "Pooch", "Eeyore" };
В них первая пара элементов одинакова, а вторая различна. Pooh считается больше, чем Pooch, так как c
лексикографически меньше h (такой способ сравнения применяется при составлении словарей). В этом месте алгоритм заканчивается (третья пара элементов не сравнивается). Результатом сравнения будет false.
Tю тЄюЁюь трЁшрэЄх рыуюЁшЄьр тьхёЄю юяхЁрЄюЁр ёЁртэхэш шёяюы№чєхЄё яЁхфшърЄэvщ юс·хъЄ:
#include <algorithm> #include <list> #include <string> #include <assert.h> #include <iostream.h> аааааааааа class size_compare { public: аааааааааа bool operator()( const string &a, const string &b ) { аааааааааа аааа return a.length() <= b.length(); аааааааааа } }; аааааааааа int main() { аааааааааа string arr1[] = { "Piglet", "Pooh", "Tigger" }; аааааааааа string arr2[] = { "Piglet", "Pooch", "Eeyore" }; ааааааааааааааааа аааааааааа bool res; ааааааааааааааааа аааааааааа // эр тЄюЁюь ¤ыхьхэЄх яюыєўрхь false аааааааааа // Pooch ьхэ№°х Pooh аааааааааа // эр ЄЁхЄ№хь ¤ыхьхэЄх Єюцх яюыєўшыш сv false аааааааааа res = lexicographical_compare( arr1, arr1+3, ааааааааааааааааааааааааааааааааааа arr2, arr2+3 ); аааааааааа assert( res == false ); ааааааааааааааааа аааааааааа // яюыєўрхь true: фышэр ърцфюую ¤ыхьхэЄр ilist2 аааааааааа // ьхэ№°х ышсю Ёртэр фышэх ёююЄтхЄёЄтхээюую аааааааааа // ¤ыхьхэЄр ilist1 аааааааааа list< string, allocator > ilist1( arr1, arr1+3 ); аааааааааа list< string, allocator > ilist2( arr2, arr2+3 ); ааааааааааааааааа аааааааааа res = lexicographical_compare( аааааааааа аааааааа ilist1.begin(), ilist1.end(), аааааааааа аааааааа ilist2.begin(), ilist2.end(), size_compare() ); ааааааааааааааааа аааааааааа assert( res == true ); аааааааааа аааааааааа cout << "ok: lexicographical_compare чртхЁ°шыё єёях°эю!\n"; |
Алгоритм lower_bound()
|
template< class ForwardIterator, class Type > ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const Type &value ); template< class ForwardIterator, class Type, class Compare > ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const Type &value, |
class Compare );
lower_bound()
возвращает итератор, указывающий на первую позицию в отсортированной последовательности, ограниченной диапазоном [first,last), в которую можно вставить значение value, не нарушая упорядоченности. В этой позиции находится значение, большее либо равное value. Например, если дана такая последовательность:
int ia = = {12,15,17,19,20,22,23,26,29,35,40,51};
то обращение к lower_bound() с аргументом value=21
возвращает итератор, указывающий на 23. Обращение с аргументом 22
возвращает тот же итератор. В первом варианте алгоритма используется оператор “меньше”, определенный для типа элементов контейнера, а во втором для упорядочения элементов применяется объект comp.
|
#include <algorithm> #include <vector> #include <iostream.h>
int main() { int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40}; sort( &ia[0], &ia[12] ); int search_value = 18; int *ptr = lower_bound( ia, ia+12, search_value ); // печатается: // Первый элемент, перед которым можно вставить 18, - это 19 // Предыдущее значение равно 17 cout << "Первый элемент, перед которым можно вставить " << search_value << ", – это " << *ptr << endl << "Предыдущее значение равно " << *(ptr-1) << endl;
vector< int, allocator > ivec( ia, ia+12 ); // отсортировать в порядке возрастания ... sort( ivec.begin(), ivec.end(), greater<int>() );
search_value = 26; vector< int, allocator >::iterator iter; // необходимо указать, как именно // осуществлялась сортировка ... iter = lower_bound( ivec.begin(), ivec.end(), search_value, greater<int>() ); // печатается: // Первый элемент, перед которым можно вставить 26, - это 26 // Предыдущее значение равно 29 cout << "Первый элемент, перед которым можно вставить " << search_value << ", - это " << *iter << endl << "Предыдущее значение равно " << *(iter-1) << endl;
return 0; |
}
Алгоритм make_heap()
|
template< class RandomAccessIterator > void make_heap( RandomAccessIterator first, RandomAccessIterator last ); template< class RandomAccessIterator, class Compare > void make_heap( RandomAccessIterator first, |
RandomAccessIterator last, Compare comp );
make_heap()
преобразует в хип последовательность, ограниченную диапазоном [first,last). В первом варианте для сравнения используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция comp.
Алгоритм max()
|
template< class Type > const Type& max( const Type &aval, const Type &bval ); template< class Type, class Compare > const Type& |
max( const Type &aval, const Type &bval, Compare comp );
max()
возвращает наибольшее из двух значений aval и bval. В первом варианте используется оператор “больше”, определенный в классе Type; во втором – операция сравнения comp.
Алгоритм max_element()
|
template< class ForwardIterator > ForwardIterator max_element( ForwardIterator first, ForwardIterator last ); template< class ForwardIterator, class Compare > ForwardIterator max_element( ForwardIterator first, |
ForwardIterator last, Compare comp );
max_element()
возвращает итератор, указывающий на элемент, который содержит наибольшее значение в последовательности, ограниченной диапазоном [first,last). В первом варианте используется оператор “больше”, определенный для типа элементов контейнера; во втором – операция сравнения comp.
Алгоритм merge()
|
template< class InputIterator1, class InputIterator2, class OutputIterator > OutputIterator merge( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result ); template< class InputIterator1, class InputIterator2, class OutputIterator, class Compare > OutputIterator merge( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, |
OutputIterator result, Compare comp );
merge()
объединяет две отсортированные последовательности, ограниченные диапазонами [first1,last1) и [first2,last2), в единую отсортированную последовательность, начинающуюся с позиции result. Результирующий итератор записи указывает на элемент за концом новой последовательности. В первом варианте для упорядочения используется оператор “меньше”, определенный для типа элементов контейнера; во втором – операция сравнения comp.
|
#include <algorithm> #include <vector> #include <list> #include <deque> #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}; int ia2[] = {74,16,39,54,21,44,62,10,27,41,65,71}; vector< int, allocator > vec1( ia, ia +12 ), vec2( ia2, ia2+12 ); int ia_result[24]; vector< int, allocator > vec_result(vec1.size()+vec2.size()); sort( ia, ia +12 ); sort( ia2, ia2+12 ); // печатается: // 10 12 15 16 17 19 20 21 22 23 26 27 29 35 // 39 40 41 44 51 54 62 65 71 74 merge( ia, ia+12, ia2, ia2+12, ia_result ); for_each( ia_result, ia_result+24, pfi ); cout << "\n\n"; sort( vec1.begin(), vec1.end(), greater<int>() ); sort( vec2.begin(), vec2.end(), greater<int>() ); merge( vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec_result.begin(), greater<int>() ); // печатается: 74 71 65 62 54 51 44 41 40 39 35 29 27 26 23 22 // 21 20 19 17 16 15 12 10 for_each( vec_result.begin(), vec_result.end(), pfi ); cout << "\n\n"; |
}
Алгоритм min()
|
template< class Type > const Type& min( const Type &aval, const Type &bval ); template< class Type, class Compare > const Type& |
min( const Type &aval, const Type &bval, Compare comp );
min()
возвращает меньшее из двух значений aval и bval. В первом варианте используется оператор “меньше”, определенный для типа Type; во втором – операция сравнения comp.
Алгоритм min_element()
|
template< class ForwardIterator > ForwardIterator min_element( ForwardIterator first, ForwardIterator last ); template< class ForwardIterator, class Compare > ForwardIterator min_element( ForwardIterator first, |
ForwardIterator last, Compare comp );
max_element()
возвращает итератор, указывающий на элемент, который содержит наименьшее значение последовательности, ограниченной диапазоном [first,last). В первом варианте используется оператор “меньше”, определенный для типа элементов контейнера; во втором – операция сравнения comp.
|
// иллюстрирует max(), min(), max_element(), min_element() #include <algorithm> #include <vector> #include <iostream.h>
int main() { int ia[] = { 7, 5, 2, 4, 3 }; const vector< int, allocator > ivec( ia, ia+5 );
int mval = max( max( max( max(ivec[4],ivec[3]), ivec[2]),ivec[1]),ivec[0]);
// вывод: результат вложенных вызовов max() равен: 7 cout << "результат вложенных вызовов max() равен: " << mval << endl; mval = min( min( min( min(ivec[4],ivec[3]), ivec[2]),ivec[1]),ivec[0]); // вывод: результат вложенных вызовов min() равен: 2 cout << "результат вложенных вызовов min() равен: " << mval << endl;
vector< int, allocator >::const_iterator iter; iter = max_element( ivec.begin(), ivec.end() ); // вывод: результат вложенных вызовов max_element() также равен: 7 cout << "результат вложенных вызовов max_element() также равен: " << *iter << endl;
iter = min_element( ivec.begin(), ivec.end() ); // вывод: результат вложенных вызовов min_element() также равен: 2 cout << "результат вложенных вызовов min_element() также равен: " << *iter << endl; |
}
Алгоритм mismatch()
|
template< class InputIterator1, class InputIterator2 > pair<InputIterator1, InputIterator2> mismatch( InputIterator1 first, InputIterator1 last, InputIterator2 first2 ); template< class InputIterator1, class InputIterator2, class BinaryPredicate > pair<InputIterator1, InputIterator2> mismatch( InputIterator1 first, InputIterator1 last, |
InputIterator2 first2, BinaryPredicate pred );
mismatch()
сравнивает две последовательности и находит первую позицию, где элементы различны. Возвращается пара итераторов, каждый из которых указывает на эту позицию в соответствующей последовательности. Если все элементы одинаковы, то каждый итератор в паре указывает на элемент last в своем контейнере. Так, если даны последовательности meet и meat, то оба итератора указывают на третий элемент. В первом варианте для сравнения элементов применяется оператор равенства, а во втором – операция сравнения, заданная пользователем. Если вторая последовательность длиннее первой, “лишние” элементы игнорируются; если же она короче, то поведение программы не определено.
|
#include <algorithm> #include <list> #include <utility> #include <iostream.h>
class equal_and_odd{ public: bool operator()( int ival1, int ival2 ) { // оба значения равны друг другу? // оба равны нулю? оба нечетны? return ( ival1 == ival2 && ( ival1 == 0 || ival1%2 )); } };
int main() { int ia[] = { 0,1,1,2,3,5,8,13 }; int ia2[] = { 0,1,1,2,4,6,10 };
pair<int*,int*> pair_ia = mismatch( ia, ia+7, ia2 ); // печатается: первая пара неодинаковых: ia: 3 и ia2: 4 cout << "первая пара неодинаковых: ia: " << *pair_ia.first << " и ia2: " << *pair_ia.second << endl;
list<int,allocator> ilist( ia, ia+7 ); list<int,allocator> ilist2( ia2, ia2+7 );
typedef list<int,allocator>::iterator iter; pair<iter,iter> pair_ilist = mismatch( ilist.begin(), ilist.end(), ilist2.begin(), equal_and_odd() ); // печатается: первая пара неодинаковых: либо не равны, либо не нечетны: // ilist: 2 и ilist2: 2 cout << "первая пара неодинаковых: либо не равны, " << "либо не нечетны: \n\tilist: " << *pair_ilist.first << " и ilist2: " << *pair_ilist.second << endl; |
}
Алгоритм next_permutation()
|
template < class BidirectionalIterator > bool next_permutation( BidirectionalIterator first, BidirectionalIterator last ); template < class BidirectionalIterator, class Compare > bool next_permutation( BidirectionalIterator first, |
BidirectionalIterator last, class Compare );
next_permutation()
берет последовательность, ограниченную диапазоном [first,last), и, считая ее перестановкой, возвращает следующую за ней (о том, как упорядочиваются перестановки, говорилось в разделе 12.5). Если следующей перестановки не существует, алгоритм возвращает false, иначе – true. В первом варианте для определения следующей перестановки используется оператор “меньше” в классе элементов контейнера, а во втором – операция сравнения comp. Последовательные обращения к next_permutation()
генерируют все возможные перестановки только в том случае, когда исходная последовательность отсортирована. Если бы в показанной ниже программе мы предварительно не отсортировали строку musil, получив ilmsu, то не удалось бы сгенерировать все перестановки.
|
#include <algorithm> #include <vector> #include <iostream.h>
void print_char( char elem ) { cout << elem ; } void (*ppc)( char ) = print_char; /* печатается: ilmsu ilmus ilsmu ilsum ilums ilusm imlsu imlus imslu imsul imuls imusl islmu islum ismlu ismul isulm isuml iulms iulsm iumls iumsl iuslm iusml limsu limus lismu lisum liums liusm lmisu lmius lmsiu lmsui lmuis lmusi lsimu lsium lsmiu lsmui lsuim lsumi luims luism lumis lumsi lusim lusmi milsu milus mislu misul miuls miusl mlisu mlius mlsiu mlsui mluis mlusi msilu msiul msliu mslui msuil msuli muils muisl mulis mulsi musil musli silmu silum simlu simul siulm siuml slimu slium slmiu slmui sluim slumi smilu smiul smliu smlui smuil smuli suilm suiml sulim sulmi sumil sumli uilms uilsm uimls uimsl uislm uisml ulims ulism ulmis ulmsi ulsim ulsmi umils umisl umlis umlsi umsil umsli usilm usiml uslim uslmi usmil usmli */ int main() { vector<char,allocator> vec(5);
// последовательность символов: musil vec[0] = 'm'; vec[1] = 'u'; vec[2] = 's'; vec[3] = 'i'; vec[4] = 'l';
int cnt = 2; sort( vec.begin(), vec.end() ); for_each( vec.begin(), vec.end(), ppc ); cout << "\t";
// генерируются все перестановки строки "musil" while( next_permutation( vec.begin(), vec.end())) { for_each( vec.begin(), vec.end(), ppc ); cout << "\t";
if ( ! ( cnt++ % 8 )) { cout << "\n"; cnt = 1; } }
cout << "\n\n"; return 0; |
}
Алгоритм nth_element()
|
template < class RandomAccessIterator > void nth_element( RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last ); template < class RandomAccessIterator, class Compare > void nth_element( RandomAccessIterator first, RandomAccessIterator nth, |
RandomAccessIterator last, Compare comp );
nth_element()
переупорядочивает последовательность, ограниченную диапазоном [first,last), так что все элементы, меньшие чем тот, на который указывает итератор nth, оказываются перед ним, а все большие элементы – после. Например, если есть массив
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
то вызов nth_element(), в котором nth
указывает на седьмой элемент (его значение равно 26):
nth_element( &ia[0], &ia[6], &ia[2] );
генерирует последовательность, в которой семь элементов, меньших 26, оказываются слева от 26, а четыре элемента, больших 26, справа:
{23,20,22,17,15,19,12,26,51,35,40,29}
При этом не гарантируется, что элементы, расположенные по обе стороны от nth, упорядочены. В первом варианте для сравнения используется оператор “меньше”, определенный для типа элементов контейнера, во втором – бинарная операция сравнения, заданная программистом.
|
#include <algorithm> #include <vector> #include <iostream.h>
/* печатается: исходный вектор: 29 23 20 22 17 15 26 51 19 12 35 40 вектор, отсортированный относительно элемента 26 12 15 17 19 20 22 23 26 51 29 35 40 вектор, отсортированный по убыванию относительно элемента 23 40 35 29 51 26 23 22 20 19 17 15 12 */ 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> out( cout," " ); cout << "исходный вектор: "; copy( vec.begin(), vec.end(), out ); cout << endl;
cout << "вектор, отсортированный относительно элемента " << *( vec.begin()+6 ) << endl; nth_element( vec.begin(), vec.begin()+6, vec.end() ); copy( vec.begin(), vec.end(), out ); cout << endl;
cout << " вектор, отсортированный по убыванию " << "относительно элемента " << *( vec.begin()+6 ) << endl; nth_element( vec.begin(), vec.begin()+6, vec.end(), greater<int>() ); copy( vec.begin(), vec.end(), out ); cout << endl; |
}
Алгоритм partial_sort()
|
template < class RandomAccessIterator > void partial_sort( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last ); template < class RandomAccessIterator, class Compare > void partial_sort( RandomAccessIterator first, RandomAccessIterator middle, |
RandomAccessIterator last, Compare comp );
partial_sort()
сортирует часть последовательности, укладывающуюся в диапазон [first,middle). Элементы в диапазоне [middle,last)
остаются неотсортированными. Например, если дан массив
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
то вызов partial_sort(),где middle
указывает на шестой элемент:
partial_sort( &ia[0], &ia[5], &ia[12] );
генерирует последовательность, в которой наименьшие пять (т.е. middle-first) элементов отсортированы:
{12,15,17,19,20,29,23,22,26,51,35,40}.
Элементы от middle до last-1 не расположены в каком-то определенном порядке, хотя значения каждого из них лежат вне отсортированной последовательности. В первом варианте для сравнения используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция сравнения comp.
Алгоритм partial_sort_copy()
|
template < class InputIterator, class RandomAccessIterator > RandomAccessIterator partial_sort_copy( InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last ); template < class InputIterator, class RandomAccessIterator, class Compare > RandomAccessIterator partial_sort_copy( InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, |
Compare comp );
partial_sort_copy()
ведет себя так же, как partial_sort(), только частично упорядоченная последовательность копируется в контейнер, ограниченный диапазоном [result_first,result_last]
(если мы задаем отдельный контейнер для копирования результата, то в нем оказывается упорядоченная последовательность). Например, даны два массива:
|
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40}; |
int ia2[5];
Тогда обращение к partial_sort_copy(), где в качестве middle
указан восьмой элемент:
|
partial_sort_copy( &ia[0], &ia[7], &ia[12], |
&ia2[0], &ia2[5] );
заполняет массив ia2
пятью отсортированными элементами: {12,15,17,19,20}. Оставшиеся два элемента отсортированы не будут.
|
#include <algorithm> #include <vector> #include <iostream.h> /* * печатается: исходный вектор: 69 23 80 42 17 15 26 51 19 12 35 8 результат применения partial_sort() к вектору: семь элементов 8 12 15 17 19 23 26 80 69 51 42 35 результат применения partial_sort_copy() к первым семи элементам вектора в порядке убывания 26 23 19 17 15 12 8 */
int main() { int ia[] = { 69,23,80,42,17,15,26,51,19,12,35,8 }; vector< int,allocator > vec( ia, ia+12 ); ostream_iterator<int> out( cout," " );
cout << "исходный вектор: "; copy( vec.begin(), vec.end(), out ); cout << endl; cout << "результат применения partial_sort() к вектору: " << "семь элементов \n"; partial_sort( vec.begin(), vec.begin()+7, vec.end() ); copy( vec.begin(), vec.end(), out ); cout << endl; vector< int, allocator > res(7); cout << " результат применения partial_sort_copy() к первым семи \n\t" << "элементам вектора в порядке убывания \n"; partial_sort_copy( vec.begin(), vec.begin()+7, res.begin(), res.end(), greater<int>() ); copy( res.begin(), res.end(), out ); cout << endl; |
}
Алгоритм partial_sum()
|
template < class InputIterator, class OutputIterator > OutputIterator partial_sum( InputIterator first, InputIterator last, OutputIterator result ); template < class InputIterator, class OutputIterator, class BinaryOperation > OutputIterator partial_sum( InputIterator first, InputIterator last, |
OutputIterator result, BinaryOperation op );
Первый вариант partial_sum()
создает из последовательности, ограниченной диапазоном [first,last), новую последовательность, в которой значение каждого элемента равно сумме всех предыдущих, включая и данный. Так, из последовательности {0,1,1,2,3,5,8} будет создана {0,1,2,4,7,12,20}, где, например, четвертый элемент равен сумме трех предыдущих (0,1,1) и его самого (2), что дает значение 4.
Во втором варианте вместо оператора сложения используется бинарная операция, заданная программистом. Предположим, мы задали последовательность {1,2,3,4} и объект-функцию times<int>. Результатом будет {1,2,6,24}. В обоих случаях итератор записи OutputIterator
указывает на элемент за последним элементом новой последовательности.
partial_sum() – это один из численных алгоритмов. Для его использования необходимо включить в программу стандартный заголовочный файл <numeric>.
|
#include <numeric> #include <vector> #include <iostream.h> /* * печатается: элементы: 1 3 4 5 7 8 9 частичная сумма элементов: 1 4 8 13 20 28 37 частичная сумма элементов с использованием times<int>(): 1 3 12 60 420 3360 30240 */
int main() { const int ia_size = 7; int ia[ ia_size ] = { 1, 3, 4, 5, 7, 8, 9 }; int ia_res[ ia_size ]; ostream_iterator< int > outfile( cout, " " ); vector< int, allocator > vec( ia, ia+ia_size ); vector< int, allocator > vec_res( vec.size() ); cout << "элементы: "; copy( ia, ia+ia_size, outfile ); cout << endl; cout << "частичная сумма элементов:\n"; partial_sum( ia, ia+ia_size, ia_res ); copy( ia_res, ia_res+ia_size, outfile ); cout << endl; cout << "частичная сумма элементов с использованием times<int>():\n"; partial_sum( vec.begin(), vec.end(), vec_res.begin(), times<int>() ); copy( vec_res.begin(), vec_res.end(), outfile ); cout << endl; |
}
Алгоритм partition()
|
template < class BidirectionalIterator, class UnaryPredicate > BidirectionalIterator partition( BidirectionalIterator first, |
BidirectionalIterator last, UnaryPredicate pred );
partition()
переупорядочивает элементы в диапазоне [first,last). Все элементы, для которых предикат pred
равен true, помещаются перед элементами, для которых он равен false. Например, если дана последовательность {0,1,2,3,4,5,6} и предикат, проверяющий целое число на четность, то мы получим две последовательности – {0,2,4,6} и {1,3,5}. Хотя гарантируется, что четные элементы будут помещены перед нечетными, их первоначальное взаимное расположение может и не сохраниться, т.е. 4 может оказаться перед 2, а 5 перед 1. Сохранение относительного порядка обеспечивает алгоритм stable_partition(), рассматриваемый ниже.
|
#include <algorithm> #include <vector> #include <iostream.h>
class even_elem { public: bool operator()( int elem ) { return elem%2 ? false : true; } };
/* * печатается: исходная последовательность: 29 23 20 22 17 15 26 51 19 12 35 40 разбиение, основанное на четности элементов: 40 12 20 22 26 15 17 51 19 23 35 29 разбиение, основанное на сравнении с 25: 12 23 20 22 17 15 19 51 26 29 35 40 */ int main() { const int ia_size = 12; int ia[ia_size] = { 29,23,20,22,17,15,26,51,19,12,35,40 }; vector< int, allocator > vec( ia, ia+ia_size ); ostream_iterator< int > outfile( cout, " " ); cout << "исходная последовательность: \n"; copy( vec.begin(), vec.end(), outfile ); cout << endl;
cout << "разбиение, основанное на четности элементов:\n"; partition( &ia[0], &ia[ia_size], even_elem() ); copy( ia, ia+ia_size, outfile ); cout << endl; cout << "разбиение, основанное на сравнении с 25:\n"; partition( vec.begin(), vec.end(), bind2nd(less<int>(),25) ); copy( vec.begin(), vec.end(), outfile ); cout << endl; |
}
Алгоритм pop_heap()
|
template< class RandomAccessIterator > void pop_heap( RandomAccessIterator first, RandomAccessIterator last ); template< class RandomAccessIterator, class Compare > void pop_heap( RandomAccessIterator first, |
RandomAccessIterator last, Compare comp );
pop_heap() в действительности не исключает наибольший элемент, а переупорядочивает хип. Он переставляет элементы в позициях first и last-1, а затем перестраивает в хип последовательность в диапазоне [first,last-1). После этого “вытолкнутый” элемент можно получить посредством функции-члена back()
контейнера либо по-настоящему исключить его с помощью pop_back(). В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция comp.
Алгоритм prev_permutation()
|
template < class BidirectionalIterator > bool prev_permutation( BidirectionalIterator first, BidirectionalIterator last ); template < class BidirectionalIterator, class Compare > bool prev_permutation( BidirectionalIterator first, |
BidirectionalIterator last, class Compare );
prev_permutation()
берет последовательность, ограниченную диапазоном [first,last), и, рассматривая ее как перестановку, возвращает предшествующую ей (о том, как упорядочиваются перестановки, говорилось в разделе 12.5). Если предыдущей перестановки не существует, алгоритм возвращает false, иначе true. В первом варианте для определения предыдущей перестановки используется оператор “меньше” для типа элементов контейнера, а во втором – бинарная операция сравнения, заданная программистом.
|
#include <algorithm> #include <vector> #include <iostream.h>
// печатается: n d a n a d d n a d a n a n d a d n int main() { vector< char, allocator > vec( 3 ); ostream_iterator< char > out_stream( cout, " " );
vec[0] = 'n'; vec[1] = 'd'; vec[2] = 'a'; copy( vec.begin(), vec.end(), out_stream ); cout << "\t"; // сгенерировать все перестановки "dan" while( prev_permutation( vec.begin(), vec.end() )) { copy( vec.begin(), vec.end(), out_stream ); cout << "\t"; } cout << "\n\n"; |
}
Алгоритм push_heap()
|
template< class RandomAccessIterator > void push_heap( RandomAccessIterator first, RandomAccessIterator last ); template< class RandomAccessIterator, class Compare > void push_heap( RandomAccessIterator first, |
RandomAccessIterator last, Compare comp );
push_heap()
предполагает, что последовательность, ограниченная диапазоном [first,last-1), – хип и что новый добавляемый к хипу элемент находится в позиции last-1. Все элементы в диапазоне [first,last) реорганизуются в новый хип. Перед вызовом push_heap()
необходимо вставить новый элемент в конец контейнера, возможно, применив функцию push_back()
(это показано в примере ниже). В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера; во втором – операция comp.
Алгоритм random_shuffle()
|
template < class RandomAccessIterator > void random_shuffle( RandomAccessIterator first, RandomAccessIterator last ); template < class RandomAccessIterator, class RandomNumberGenerator > void random_shuffle( RandomAccessIterator first, RandomAccessIterator last, |
RandomNumberGenerator rand);
random_shuffle()
переставляет элементы из диапазона [first,last) в случайном порядке. Во втором варианте можно передать объект-функцию или указатель на функцию, генерирующую случайные числа. Ожидается, что генератор rand возвращает значение типа double в интервале [0,1].
|
#include <algorithm> #include <vector> #include <iostream.h>
int main() { vector< int, allocator > vec; for ( int ix = 0; ix < 20; ix++ ) vec.push_back( ix );
random_shuffle( vec.begin(), vec.end() );
// печатает: // random_shuffle для последовательности 1 .. 20: // 6 11 9 2 18 12 17 7 0 15 4 8 10 5 1 19 13 3 14 16 cout << "random_shuffle для последовательности 1 .. 20:\n"; copy( vec.begin(), vec.end(), ostream_iterator< int >( cout," " )); |
}
Алгоритм remove()
|
template< class ForwardIterator, class Type > ForwardIterator remove( ForwardIterator first, |
ForwardIterator last, const Type &value );
remove()
удаляет из диапазона [first,last) все элементы со значением value. Этот алгоритм (как и remove_if()) на самом деле не исключает элементы из контейнера (т.е. размер контейнера сохраняется), а перемещает каждый оставляемый элемент в очередную позицию, начиная с first. Возвращаемый итератор указывает на элемент, следующий за позицией, в которую помещен последний неудаленный элемент. Рассмотрим, например, последовательность {0,1,0,2,0,3,0,4}. Предположим, что нужно удалить все нули. В результате получится последовательность {1,2,3,4,0,4,0,4}. 1 помещена в первую позицию, 2– во вторую, 3 – в третью и 4 – в четвертую. Элементы, начиная с 0 в пятой позиции, – это “отходы” алгоритма. Возвращенный итератор указывает на 0 в пятой позиции. Обычно этот итератор затем передается алгоритму erase(), который удаляет неподходящие элементы. (При работе со встроенным массивом лучше использовать алгоритмы remove_copy() и remove_copy_if(), а не remove() и remove_if(), поскольку его размер невозможно изменить)
Алгоритм remove_copy()
|
template< class InputIterator, class OutputIterator, class Type > OutputIterator remove_copy( InputIterator first, InputIterator last, |
OutputIterator result, const Type &value );
remove_copy()
копирует все элементы, кроме имеющих значение value, в контейнер, на начало которого указывает result. Возвращаемый итератор указывает на элемент за последним скопированным. Исходный контейнер не изменяется.
|
#include <algorithm> #include <vector> #include <assert.h> #include <iostream.h>
/* печатается: исходный вектор: 0 1 0 2 0 3 0 4 0 5 вектор после remove до erase(): 1 2 3 4 5 3 0 4 0 5 вектор после erase(): 1 2 3 4 5 массив после remove_copy() 1 2 3 4 5 */ int main() { int value = 0; int ia[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5 }; vector< int, allocator > vec( ia, ia+10 ); ostream_iterator< int > ofile( cout," "); vector< int, allocator >::iterator vec_iter; cout << "исходный вектор:\n"; copy( vec.begin(), vec.end(), ofile ); cout << '\n';
vec_iter = remove( vec.begin(), vec.end(), value ); cout << "вектор после remove до erase():\n"; copy( vec.begin(), vec.end(), ofile ); cout << '\n';
// удалить из контейнера неподходящие элементы vec.erase( vec_iter, vec.end() ); cout << "вектор после erase():\n"; copy( vec.begin(), vec.end(), ofile ); cout << '\n'; int ia2[5]; vector< int, allocator > vec2( ia, ia+10 ); remove_copy( vec2.begin(), vec2.end(), ia2, value ); cout << "массив после remove_copy():\n"; copy( ia2, ia2+5, ofile ); cout << endl; |
}
Алгоритм remove_copy_if()
|
template< class InputIterator, class OutputIterator, class Predicate > OutputIterator remove_copy_if( InputIterator first, InputIterator last, |
OutputIterator result, Predicate pred );
remove_copy_if()
копирует все элементы, для которых предикат pred равен false, в контейнер, на начало которого указывает итератор result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.
|
#include <algorithm> #include <vector> #include <iostream.h> /* печатается: исходная последовательность: 0 1 1 2 3 5 8 13 21 34 последовательность после применения remove_if < 10: 13 21 34 последовательность после применения remove_copy_if четное: 1 1 3 5 13 21 */ class EvenValue { public: bool operator()( int value ) { return value % 2 ? false : true; } };
int main() { int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 }; vector< int, allocator >::iterator iter; vector< int, allocator > vec( ia, ia+10 ); ostream_iterator< int > ofile( cout, " " ); cout << "исходная последовательность:\n"; copy( vec.begin(), vec.end(), ofile ); cout << '\n'; iter = remove_if( vec.begin(), vec.end(), bind2nd(less<int>(),10) ); vec.erase( iter, vec.end() );
cout << "последовательность после применения remove_if < 10:\n"; copy( vec.begin(), vec.end(), ofile ); cout << '\n'; vector< int, allocator > vec_res( 10 ); iter = remove_copy_if( ia, ia+10, vec_res.begin(), EvenValue() ); cout << "последовательность после применения remove_copy_if четное:\n"; copy( vec_res.begin(), iter, ofile ); cout << '\n'; |
}
Алгоритм remove_if()
|
template< class ForwardIterator, class Predicate > ForwardIterator remove_if( ForwardIterator first, |
ForwardIterator last, Predicate pred );
remove_if()
удаляет из диапазона [first,last) все элементы, для которых значение предиката pred равно true. remove_if() (как и remove()) фактически не исключает удаленные элементы из контейнера. Вместо этого каждый оставляемый элемент перемещается в очередную позицию, начиная с first. Возвращаемый итератор указывает на элемент, следующий за позицией, в которую помещен последний неудаленный элемент. Обычно этот итератор затем передается алгоритму erase(), который удаляет неподходящие элементы. (Для встроенных массивов лучше использовать алгоритм remove_copy_if().)
Алгоритм replace()
|
template< class ForwardIterator, class Type > void replace( ForwardIterator first, ForwardIterator last, |
const Type& old_value, const Type& new_value );
replace()
заменяет в диапазоне [first,last) все элементы со значением old_value на new_value.
Алгоритм 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() ); |
}
