inplace_merge

[szablon funkcji] Scala dwa posortowane zakresy w jeden posortowany zakres.

Składnia

#include <algorithm>

namespace std
{
template < class BidirectionalIterator >
void inplace_merge(
BidirectionalIterator First,
BidirectionalIterator Middle,
BidirectionalIterator Last
);

template < class BidirectionalIterator, class Predicate >
void inplace_merge(
BidirectionalIterator First,
BidirectionalIterator Middle,
BidirectionalIterator Last,
Predicate Compare
);
}

Argumenty

Argument	Opis
BidirectionalIterator First	Dwukierunkowy iterator, wskazujący na pierwszy element pierwszego zakresu danych.
BidirectionalIterator Middle	Dwukierunkowy iterator, wskazujący na pierwszy element drugiego zakresu danych. Iterator ten wskazuje jednocześnie na element będący za ostatnim elementem pierwszego zakresu danych.
BidirectionalIterator Last	Dwukierunkowy iterator, wskazujący na element będący za ostatnim elementem drugiego zakresu danych.
Predicate Compare	_{» Dokumentacja ♦}binarny predykat, który określa sposób uporządkowania danych tj. który element jest mniejszy od którego. Predykat ten przyjmuje dwa elementy z zakresu oraz zwraca wartość `true`, jeśli pierwszy argument powinien znajdować się za drugim, natomiast `false` w przeciwnym wypadku.

Opis szczegółowy

Funkcja scala dwa posortowane zakresy w jeden posortowany zakres. Sposób sortowania danych można określić za pomocą _{» Dokumentacja ♦}binarnego predykatu. Scalane zakresy danych muszą być poprawnie posortowane przed ich scaleniem oraz dostęp do ostatniego elementu danych musi być możliwy poprzez wykonywanie inkrementacji rozpoczynając od iteratora pierwszego elementu.

Złożoność obliczeniowa algorytmu jest zależna od dostępnej pamięci, ponieważ algorytm alokuje tymczasowy bufor. Jeżeli odpowiednia ilość pamięci jest dostępna to algorytm będzie posiadał złożoność O(n), gdzie n to liczba elementów występujących w zakresie. W przypadku gdy nie ma dostępnej wystarczającej ilości pamięci złożoność obliczeniowa algorytmu wynosi O(n*log(n)).

Przykład

#include <cstdio>
#include <algorithm>
#include <vector>

std::vector < int >& operator <<( std::vector < int >& v, const int & iWartosc )
{
v.push_back( iWartosc );
return v;
}

void wypisz( const std::vector < int >& v )
{
for( std::vector < int >::const_iterator i = v.begin(); i != v.end(); ++i )
printf( "%d, ", * i );

printf( "\n" );
}

int main()
{
std::vector < int > dane;
dane << 7 << 3 << 5 << 1 << 8 << 9 << 30 << 1 << 8 << 100 << 10 << 20 << 50 << 99;
std::vector < int >::iterator itSrodek = dane.begin() + dane.size() / 2;
wypisz( dane );
std::sort( dane.begin(), itSrodek );
std::sort( itSrodek, dane.end() );
wypisz( dane );
std::inplace_merge( dane.begin(), itSrodek, dane.end() );
wypisz( dane );
return 0;
}

Standardowe wyjście programu:

7, 3, 5, 1, 8, 9, 30, 1, 8, 100, 10, 20, 50, 99,
1, 3, 5, 7, 8, 9, 30, 1, 8, 10, 20, 50, 99, 100,
1, 1, 3, 5, 7, 8, 8, 9, 10, 20, 30, 50, 99, 100,

Linki zewnętrzne

http://www.cplusplus.com/reference/algorithm/inplace_merge/

Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem jest zabronione.

Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.