|
Алгоритм 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";
| }
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|
