НА ГЛАВНУЮ
Меню сайта
Категория
Ghost++ [1]
С++ [55]
Развлечение
ON - LINE
Опрос
Что лепим морфу первым артом?
Всего ответов: 353
Оbserver Ward

Онлайн всего: 3
Гостей: 3
Пользователей: 0


Друзья сайта
Заведи себе Бота
Hаша кнопка
Для обмена банерами , наша кнопка для размещения у вас на сайте

Клансайт USSR


Главная » Статьи » Программирование » С++

21. Обобщенные алгоритмы в алфавитном порядке (1)
21. Обобщенные алгоритмы в алфавитном порядке

В этом приложении мы рассмотрим все алгоритмы. Мы решили расположить их в алфавитном порядке (за небольшими исключениями), чтобы проще было найти нужный. Каждый алгоритм представлен в следующем виде: сначала описывается прототип функции, затем сам алгоритм, причем особое внимание уделяется интуитивно неочевидным особенностям, и, наконец, приводится пример программы, показывающий, как можно данный алгоритм использовать.

Первыми двумя аргументами всех обобщенных алгоритмов (естественно, не без исключений) является пара итераторов, обычно first и last, обозначающих диапазон элементов внутри контейнера или встроенного массива, над которым работает алгоритм. Этот диапазон (часто называемый интервалом с включенной левой границей), как правило, записывается в виде:

// следует читать: включая first и все последующие
// элементы до last, но не включая сам last
[ first, last )

Это означает, что диапазон начинается с first и заканчивается last, однако сам элемент last не включается. Если

first == last

то говорят, что диапазон пуст.

К паре итераторов предъявляется такое требование: last должен быть достижим, если начать с first и последовательно применять оператор инкремента. Однако компилятор не может проверить выполнение данного ограничения. Если требование не будет выполнено, поведение программы не определено; обычно это заканчивается ее крахом и дампом памяти.

В объявлении каждого алгоритма подразумевается минимальная поддержка, которую должны обеспечить итераторы (краткое обсуждение пяти категорий итераторов см. в разделе 12.4). Например, алгоритм find(), реализующий однопроходный обход контейнера и выполняющий только чтение, требует итератора чтения InputIterator. Ему также можно передать одно- или двунаправленный итератор или итератор с произвольным доступом. Однако передача итератора записи приведет к ошибке. Не гарантируется, что подобные ошибки (при передаче итератора неподходящей категории) будут обнаружены компилятором, поскольку категории итераторов - это не сами типы, а лишь параметры, которыми конкретизируется шаблон функции.

Некоторые алгоритмы существуют в нескольких вариантах: в одном используется тот или иной встроенный оператор, а в другом - объект-функция или указатель на функцию, реализующие альтернативу этому оператору. Например, алгоритм unique() по умолчанию сравнивает соседние элементы контейнера с помощью оператора равенства, определенного в классе, к которому данные элементы принадлежат. Но если в этом классе нет оператора равенства или мы хотим сравнивать элементы иным способом, то можем передать объект-функцию или указатель на функцию, поддерживающую нужную семантику. Есть и такие алгоритмы, которые выполняют похожие действия, но имеют различные имена. Так, имена предикатных версий алгоритмов всегда заканчиваются на _if, скажем find_if(). Например, есть вариант алгоритма replace(), где используется встроенный оператор равенства, и вариант с именем replace_if(), которому передается предикатный объект-функция или указатель на функцию-предикат.

Алгоритмы, модифицирующие контейнер, обычно также существуют в двух вариантах: один осуществляет модификацию по месту, а второй возвращает копию с внесенными изменениями. Так, есть алгоритмы replace() и replace_copy(). Однако вариант с копированием (его имя всегда содержит слово _copy) имеется не для каждого алгоритма, модифицирующего контейнер. К примеру, для алгоритмов sort() его нет. В таких случаях, если нужно, чтобы алгоритм работал с копией, мы должны создать ее самостоятельно и передать в качестве аргумента.

Для использования любого обобщенного алгоритма в программу необходимо включить заголовочный файл

#include <algorithm>

Для употребления любого из четырех численных алгоритмов: adjacent_difference(), accumulate(), inner_product() и partial_sum() - нужно включить также файл

#include <numeric>

Приведенные в этом Приложении примеры программ, в которых используются алгоритмы и различные контейнерные типы, отражают существующую на момент написания книги реализацию. Применение библиотеки ввода/вывода iostream следует соглашениям, установленным до принятия стандарта; скажем, в программу включается заголовочный файл iostream.h, а не iostream. Шаблоны не поддерживают аргументы по умолчанию. Чтобы программа работала на системе, имеющейся у вас, возможно, придется изменить некоторые объявления.

Другое, более подробное, чем в этой книге, описание обобщенных алгоритмов можно найти в работе [MUSSER96], правда, оно несколько отстает от окончательного варианта стандартной библиотеки C++.

    Алгоритм accumulate()
template < class InputIterator, class Type >
Type accumulate(
   InputIterator first, InputIterator last,
   Type init );

template < class InputIterator, class Type,
           class BinaryOperation >
Type accumulate(
   InputIterator first, InputIterator last,
   Type init, BinaryOperation op );

Первый вариант accumulate() вычисляет сумму значений элементов последовательности из диапазона, ограниченного парой итераторов [first,last), с начальным значением, которое задано параметром init. Например, если дана последовательность {1,1,2,3,5,8} и начальное значение 0, то результатом работы алгоритма будет 20. Во втором варианте вместо оператора сложения к элементам применяется переданная бинарная операция. Если бы мы передали алгоритму accumulate() объект-функцию times и начальное значение 1, то получили бы результат 240. accumulate() - это один из численных алгоритмов; для его использования в программу необходимо включить заголовочный файл .

#include <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() - это один из численных алгоритмов, для его использования в программу необходимо включить заголовочный файл .

#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";
}
Категория: С++ | Добавил: r2d2 (29.09.2011)
Просмотров: 411 | Рейтинг: 5.0/1
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Born in Ussr
Залогиниться
Турниры

/j clan ussr /j clan cccp