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

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

Клансайт USSR
Главная » Статьи » Программирование » С++
21. Обобщенные алгоритмы в алфавитном порядке (5)
Алгоритм set_union()

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

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

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

#include <algorithm>
#include <set>
#include <string>
#include <iostream.h>
/* печатается:
   элементы множества #1:
        Иа-Иа Пух Пятачок Тигра
   элементы множества #2:
        Бука Пух Слонопотам
   элементы set_union():
        Бука Иа-Иа Пух Пятачок Слонопотам Тигра
   элементы set_intersection():
        Пух
   элементы set_difference():
        Иа-Иа Пятачок Тигра
   элементы_symmetric_difference():
       Бука Иа-Иа Пятачок Слонопотам Тигра
*/
int main()
{
    string str1[] = { "Пух", "Пятачок", "Тигра", "Иа-Иа" };
    string str2[] = { "Пух", "Слонопотам", "Бука" };
     ostream_iterator< string >  ofile( cout, " " );
        
    set<string,less<string>,allocator> set1( str1, str1+4 );
    set<string,less<string>,allocator> set2( str2, str2+3 );

     cout << "элементы множества #1:\n\t";
     copy( set1.begin(), set1.end(), ofile ); cout << "\n\n";
     cout << "элементы множества #2:\n\t";
     copy( set2.begin(), set2.end(), ofile ); cout << "\n\n";

    set<string,less<string>,allocator> res;
    set_union( set1.begin(), set1.end(),
                set2.begin(), set2.end(),
                inserter( res, res.begin() ));

     cout << "элементы set_union():\n\t";
     copy( res.begin(), res.end(), ofile ); cout << "\n\n";

    res.clear();
    set_intersection( set1.begin(), set1.end(),
                       set2.begin(), set2.end(),
                       inserter( res, res.begin() ));

     cout << "элементы set_intersection():\n\t";
     copy( res.begin(), res.end(), ofile ); cout << "\n\n";

     res.clear();
     set_difference( set1.begin(), set1.end(),
                     set2.begin(), set2.end(),
                     inserter( res, res.begin() ));

     cout << "элементы set_difference():\n\t";
     copy( res.begin(), res.end(), ofile ); cout << "\n\n";

     res.clear();
     set_symmetric_difference( set1.begin(), set1.end(),
                               set2.begin(), set2.end(),
                               inserter( res, res.begin() ));

     cout << "элементы set_symmetric_difference():\n\t";
     copy( res.begin(), res.end(), ofile ); cout << "\n\n";
}

Алгоритм sort()

template< class RandomAccessIterator >
void
sort( RandomAccessIterator first,
      RandomAccessIterator last );

template< class RandomAccessIterator, class Compare >
void
sort( RandomAccessIterator first,
      RandomAccessIterator last, Compare comp );

sort() переупорядочивает элементы в диапазоне [first,last) по возрастанию, используя оператор "меньше", определенный для типа элементов контейнера. Во втором варианте порядок устанавливается операцией сравнения comp. (Для сохранения относительного порядка равных элементов пользуйтесь алгоритмом stable_sort().) Мы не приводим пример, специально иллюстрирующий применение алгоритма sort(), поскольку его можно найти во многих других программах, в частности в binary_search(), equal_range() и inplace_merge().
Алгоритм 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";
}

Алгоритмы для работы с хипом

В стандартной библиотеке используется макс-хип. Макс-хип - это представленное в виде массива двоичное дерево, для которого значение ключа в каждом узле больше либо равно значению ключа в каждом из узлов-потомков. (Подробное обсуждение макс-хипа можно найти в [SEDGEWICK88]. Альтернативой ему является мин-хип, для которого значение ключа в каждом узле меньше либо равно значению ключа в каждом из узлов-потомков.) В реализации из стандартной библиотеки самое большое значение (корень дерева) всегда оказывается в начале массива. Например, приведенная последовательность букв удовлетворяет требованиям, накладываемым на хип:

X T O G S M N A E R A I

В данном примере X - это корневой узел, слева от него находится T, а справа - O. Обратите внимание, что потомки не обязательно должны быть упорядочены (т.е. значение в левом узле не обязано быть меньше, чем в правом). G и S - потомки узла T, а M и N - потомки узла O. Аналогично A и E - потомки G, R и A - потомки S, I - левый потомок M, а N - листовой узел без потомков.

Четыре обобщенных алгоритма для работы с хипом: make_heap(), pop_heap(), push_heap() и sort_heap() - поддерживают его создание и различные манипуляции. В последних трех алгоритмах предполагается, что последовательность, ограниченная парой итераторов, - действительно хип (в противном случае поведение программы не определено). Заметим, что список нельзя использовать как контейнер для хранения хипа, поскольку он не поддерживает произвольный доступ. Встроенный массив для размещения хипа использовать можно, но в этом случае трудно применять алгоритмы pop_heap() и push_heap(), так как они требуют изменения размера контейнера. Мы опишем все четыре алгоритма, а затем проиллюстрируем их работу на примере небольшой программы.
Алгоритм 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.
Алгоритм 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.
Алгоритм 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.
Алгоритм sort_heap()

template< class RandomAccessIterator >
void
sort_heap( RandomAccessIterator first,
           RandomAccessIterator last );
template< class RandomAccessIterator, class Compare >
void
sort_heap( RandomAccessIterator first,
           RandomAccessIterator last, Compare comp );

sort_heap() сортирует последовательность в диапазоне [first,last), предполагая, что это правильно построенный хип; в противном случае поведение программы не определено. (Разумеется, после сортировки хип перестает быть хипом!) В первом варианте при сравнении используется оператор "меньше", определенный для типа элементов контейнера, а во втором - операция comp.

#include <algorithm>
#include <vector>
#include <assert.h>
template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
int main()
{
    int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
    vector<int, allocator > vec( ia, ia+12 );
        

     // печатается: 51 35 40 23 29 20 26 22 19 12 17 15
    make_heap( &ia[0], &ia[12] );
     void (*pfi)( int ) = print_elements;
     for_each( ia, ia+12, pfi ); cout << "\n\n";

     // печатается: 12 17 15 19 23 20 26 51 22 29 35 40
     // минимальный хип: в корне наименьший элемент
    make_heap( vec.begin(), vec.end(), greater<int>() );
     for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";

     // печатается: 12 15 17 19 20 22 23 26 29 35 40 51
    sort_heap( ia, ia+12 );
     for_each(  ia, ia+12, pfi ); cout <<"\n\n";

    // добавим новый наименьший элемент
    vec.push_back( 8 );

     // печатается: 8 17 12 19 23 15 26 51 22 29 35 40 20
    // новый наименьший элемент должен оказаться в корне
    push_heap( vec.begin(), vec.end(), greater<int>() );
     for_each(  vec.begin(), vec.end(), pfi ); cout << "\n\n";

     // печатается: 12 17 15 19 23 20 26 51 22 29 35 40 8
    // наименьший элемент должен быть заменен на следующий по порядку

    pop_heap( vec.begin(), vec.end(), greater<int>() );
     for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
}
Категория: С++ | Добавил: r2d2 (29.09.2011)
Просмотров: 959 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Born in Ussr
Залогиниться
Главная Регистрация Вход
Турниры

/j clan ussr /j clan cccp