На этом шаге мы рассмотрим алгоритмы, используемые для слияния смежных упорядоченных интервалов.
Для выполнения этой операции можно использовать следующие алгоритмы:
void inplace_merge (BidirectionalIterator beg1, BidirectionalIterator end1beg2, Bidirectional Iterator end2) void inplace_merge (BidirectionalIterator beg1, BidirectionalIterator end1beg2, BidirectionalIterator end2, BinaryPredicate op)
Обе формы выполняют слияние смежных упорядоченных интервалов [beg1, end1beg2) и [end1beg2,end2) так, чтобы интервал [beg1,end2) содержал упорядоченную совокупность элементов обоих интервалов.
Сложность линейная при наличии дополнительной памяти (numberOfElements-1 сравнений), n*log(n) в противном случае (numberOfElements*log(numberOfElements) сравнений).
Пример использования алгоритма inplace_merge():
//--------------------------------------------------------------------------- #include <vcl.h> #include <iterator> #include "algostuff.hpp" #include <conio.h> //необходимо для getch() #pragma hdrstop //--------------------------------------------------------------------------- #pragma argsused using namespace std; std::string ToRus(const std::string &in) { char *buff = new char [in.length()+1]; CharToOem(in.c_str(),buff); std::string out(buff); delete [] buff; return out; } int main() { list<int> coll; // Вставка двух упорядоченных интервалов INSERT_ELEMENTS(coll,1,7); INSERT_ELEMENTS(coll,1,8); PRINT_ELEMENTS(coll,"Исходная коллекция:\n"); // Определение начала второго интервала (элемент после 7) list<int>::iterator pos; pos = find (coll.begin(), coll.end(), // Интервал 7); // Значение ++pos; // Слияние в один упорядоченный интервал inplace_merge (coll.begin(), pos, coll.end()); PRINT_ELEMENTS(coll,"Коллекция после слияния:\n"); getch(); return 0; } //---------------------------------------------------------------------------
Результат выполнения программы выглядит так:
Рис.1. Результат работы приложения
Со следующего шага мы начнем рассматривать численные алгоритмы.
