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

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


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

Клансайт USSR


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

21. Обобщенные алгоритмы в алфавитном порядке (4)
Алгоритм 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_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().)
Алгоритм 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';
}

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

Алгоритм reverse()

template< class BidirectionalIterator >
void
reverse( BidirectionalIterator first,
         BidirectionalIterator last );

reverse() меняет порядок элементов контейнера в диапазоне [first,last) на противоположный. Например, если есть последовательность {0,1,1,2,3}, то после обращения получится {3,2,1,1,0}. Алгоритм reverse_copy() template< class BidirectionalIterator, class OutputIterator > OutputIterator reverse_copy( BidirectionalIterator first, BidirectionalIterator last, OutputIterator result ); reverse_copy() ведет себя так же, как reverse(), только новая последовательность копируется в контейнер, начиная с result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения. #include <algorithm> #include <list> #include <string> #include <iostream.h> /* печатается: Исходная последовательность строк: Signature of all things I am here to read seaspawn and seawrack that rusty boot Последовательность строк после применения reverse(): boot rusty that seawrack and seaspawn read to here am I things all of Signature */ class print_elements { public: void operator()( string elem ) { cout << elem << ( _line_cnt++%8 ? " " : "\n\t" ); } static void reset_line_cnt() { _line_cnt = 1; } private: static int _line_cnt; }; int print_elements::_line_cnt = 1; int main() { string sa[] = { "Signature", "of", "all", "things", "I", "am", "here", "to", "read", "seaspawn", "and", "seawrack", "that", "rusty", "boot" }; list< string, allocator > slist( sa, sa+15 ); cout << "Исходная последовательность строк:\n\t"; for_each( slist.begin(), slist.end(), print_elements() ); cout << "\n\n"; reverse( slist.begin(), slist.end() ); print_elements::reset_line_cnt(); cout << "Последовательность строк после применения reverse():\n\t"; for_each( slist.begin(), slist.end(), print_elements() ); cout << "\n"; list< string, allocator > slist_copy( slist.size() ); reverse_copy( slist.begin(), slist.end(), slist_copy.begin() ); }
Алгоритм rotate()

template< class ForwardIterator >
void
rotate( ForwardIterator first,
        ForwardIterator middle, ForwardIterator last );

rotate() перемещает элементы из диапазона [first,last) в конец контейнера. Элемент, на который указывает middle, становится первым. Например, для слова "hissboo" вращение вокруг буквы 'b' превращает слово в "boohiss".
Алгоритм rotate_copy()

template< class ForwardIterator, class OutputIterator >
OutputIterator
rotate_copy( ForwardIterator first, ForwardIterator middle,
             ForwardIterator last, OutputIterator result );

rotate_copy() ведет себя так же, как rotate(), только новая последовательность копируется в контейнер, начиная с result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.

#include <algorithm>
#include <vector>
#include <iostream.h>
/* печатается:
   исходная последовательность:
   1 3 5 7 9 0 2 4 6 8 10
   вращение вокруг среднего элемента(0) ::
   0 2 4 6 8 10 1 3 5 7 9
   вращение вокруг предпоследнего элемента(8) ::
   8 10 1 3 5 7 9 0 2 4 6
   rotate_copy вокруг среднего элемента ::
   7 9 0 2 4 6 8 10 1 3 5
*/
int main()
{
    int ia[] = { 1, 3, 5, 7, 9, 0, 2, 4, 6, 8, 10 };

    vector< int, allocator > vec( ia, ia+11 );
        ostream_iterator< int >  ofile( cout, " " );

     cout << "исходная последовательность:\n";
     copy( vec.begin(), vec.end(), ofile ); cout << '\n';

    rotate( &ia[0], &ia[5], &ia[11] );

     cout << "вращение вокруг среднего элемента(0) ::\n";
     copy( ia, ia+11, ofile ); cout << '\n';

    rotate( vec.begin(), vec.end()-2, vec.end() );
        
    cout << "вращение вокруг предпоследнего элемента(8) ::\n";
    copy( vec.begin(), vec.end(), ofile ); cout << '\n';

    vector< int, allocator > vec_res( vec.size() );

     rotate_copy( vec.begin(), vec.begin()+vec.size()/2,
                  vec.end(), vec_res.begin() );

     cout << "rotate_copy вокруг среднего элемента ::\n";
     copy( vec_res.begin(), vec_res.end(), ofile );
     cout << '\n';
}

Алгоритм search()

template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator
search( ForwardIterator1 first1, ForwardIterator1 last1,
        ForwardIterator2 first2, ForwardIterator2 last2 );

template< class ForwardIterator1, class ForwardIterator2,
          class BinaryPredicate >
ForwardIterator
search( ForwardIterator1 first1, ForwardIterator1 last1,
        ForwardIterator2 first2, ForwardIterator2 last2,
        BinaryPredicate pred );

Если даны два диапазона, то search() возвращает итератор, указывающий на первую позицию в диапазоне [first1,last1), начиная с которой второй диапазон входит как подпоследовательность. Если подпоследовательность не найдена, возвращается last1. Например, в слове Mississippi подпоследовательность iss встречается дважды, и search() возвращает итератор, указывающий на начало первого вхождения. В первом варианте для сравнения элементов используется оператор равенства, во втором - указанная программистом операция сравнения.

#include <algorithm>
#include <vector>
#include <iostream.h>

/* печатается:
   Ожидаем найти подстроку 'ate': a t e
   Ожидаем найти подстроку 'vat': v a t
*/

int main()
{
     ostream_iterator< char >  ofile( cout, " " );
    
    char str[ 25 ]   = "a fine and private place";
    char substr[] = "ate";
        
    char *found_str = search(str,str+25,substr,substr+3);

    cout << "Ожидаем найти подстроку 'ate': ";
     copy( found_str, found_str+3, ofile ); cout << '\n';
        
    vector< char, allocator > vec( str, str+24 );
    vector< char, allocator > subvec(3);

    subvec[0]='v'; subvec[1]='a'; subvec[2]='t';
    
    vector< char, allocator >::iterator iter;
     iter = search( vec.begin(), vec.end(),
                    subvec.begin(), subvec.end(),
                    equal_to< char >() );

    cout << "Ожидаем найти подстроку 'vat': ";
     copy( iter, iter+3, ofile ); cout << '\n';
}

Алгоритм search_n()

template< class ForwardIterator, class Size, class Type >
ForwardIterator
search_n( ForwardIterator first, ForwardIterator last,
          Size count, const Type &value );

template< class ForwardIterator, class Size,
          class Type, class BinaryPredicate >
ForwardIterator
search_n( ForwardIterator first, ForwardIterator last,
          Size count, const Type &value, BinaryPredicate pred );

search_n() ищет в последовательности [first,last) подпоследовательность, состоящую из count повторений значения value. Если она не найдена, возвращается last. Например, для поиска подстроки ss в строке Mississippi следует задать value равным 's', а count равным 2. Если же нужно найти две расположенные подряд подстроки ssi, то value задается равным "ssi", а count снова 2. search_n() возвращает итератор на первый элемент со значением value. В первом варианте для сравнения элементов используется оператор равенства, во втором - указанная программистом операция сравнения.

#include <algorithm>
#include <vector>
#include <iostream.h>

/* печатается:
   Ожидаем найти два вхождения 'o': o o
   Ожидаем найти подстроку 'mou':  m o u
*/
    
int main()
{
     ostream_iterator< char >  ofile( cout, " " );

    const char blank = ' ';
    const char oh    = 'o';

    char str[ 26 ]  = "oh my a mouse ate a moose";
    char *found_str = search_n( str, str+25, 2, oh );
        
    cout << "Ожидаем найти два вхождения 'o': ";
     copy( found_str, found_str+2, ofile ); cout < <'\n';

    vector< char, allocator > vec( str, str+25 );
        
    // найти первую последовательность из трех символов,
    // ни один из которых не равен пробелу: mou of mouse

    vector< char, allocator >::iterator iter;
     iter = search_n( vec.begin(), vec.end(), 3,
                     blank, not_equal_to< char >() );

    cout < <"Ожидаем найти подстроку 'mou':  ";
     copy( iter, iter+3, ofile ); cout < < '\n';
}

Алгоритм set_difference()

template< class InputIterator1, class InputIterator2,
          class OutputIterator >
OutputIterator
set_difference( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2,
                OutputIterator result );

template< class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare >
OutputIterator
set_difference( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2,
                OutputIterator result, Compare comp );

set_difference() строит отсортированную последовательность из элементов, имеющихся в первой последовательности [first1,last1), но отсутствующих во второй - [first2,last2). Например, разность последовательностей {0,1,2,3} и {0,2,4,6} равна {1,3}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора "меньше", определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
Алгоритм set_intersection()

template< class InputIterator1, class InputIterator2,
          class OutputIterator >
OutputIterator
set_intersection( InputIterator1 first1, InputIterator1 last1,
                  InputIterator2 first2, InputIterator2 last2,
                  OutputIterator result );

template< class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare >
OutputIterator
set_intersection( InputIterator1 first1, InputIterator1 last1,
                  InputIterator2 first2, InputIterator2 last2,
                  OutputIterator result, Compare comp );

set_intersection() строит отсортированную последовательность из элементов, встречающихся в обеих последовательностях - [first1,last1) и [first2,last2). Например, пересечение последовательностей {0,1,2,3} и {0,2,4,6} равно {0,2}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора "меньше", определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
Алгоритм set_symmetric_difference()

template< class InputIterator1, class InputIterator2,
          class OutputIterator >
OutputIterator
set_symmetric_difference(
       InputIterator1 first1, InputIterator1 last1,
       InputIterator2 first2, InputIterator2 last2,
       OutputIterator result );

template< class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare >
OutputIterator
set_symmetric_difference(
       InputIterator1 first1, InputIterator1 last1,
       InputIterator2 first2, InputIterator2 last2,
       OutputIterator result, Compare comp );

set_symmetric_difference() строит отсортированную последовательность из элементов, которые встречаются только в первой последовательности [first1,last1) или только во второй - [first2,last2). Например, симметрическая разность последовательностей {0,1,2,3} и {0,2,4,6} равна {1,3,4,6}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора "меньше”, определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
Категория: С++ | Добавил: r2d2 (29.09.2011)
Просмотров: 308 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Born in Ussr
Залогиниться
Турниры

/j clan ussr /j clan cccp