Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Opracował: Piotr DejaVu Szawdyński
Język C++

inplace_merge

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

Składnia

C/C++
#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

ArgumentOpis
BidirectionalIterator FirstDwukierunkowy iterator, wskazujący na pierwszy element pierwszego zakresu danych.
BidirectionalIterator MiddleDwukierunkowy 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 LastDwukierunkowy iterator, wskazujący na element będący za ostatnim elementem drugiego zakresu danych.
Predicate Compare» Dokumentacjabinarny 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ą » Dokumentacjabinarnego 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

C/C++
#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