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