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

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

Клансайт USSR
Главная » Статьи » Программирование » С++
21. Обобщенные алгоритмы в алфавитном порядке (2)
Алгоритм 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_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;
}

Алгоритм 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";
}

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

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

/j clan ussr /j clan cccp