База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

std::inplace_merge: стабилно сливане на съседни серии

std::inplace_merge стабилно слива два последователни вече сортирани поддиапазона в същия диапазон.

Версия: C++23

Синтаксис

template<class BidirectionalIt>
void std::inplace_merge(BidirectionalIt first, BidirectionalIt middle, BidirectionalIt last);

template<class BidirectionalIt, class Compare>
void std::inplace_merge(BidirectionalIt first, BidirectionalIt middle, BidirectionalIt last, Compare comp);

std::inplace_merge(first,middle,last) слива [first,middle) и [middle,last) чрез std::less; претоварване приема comp. И двата трябва да са валидни и сортирани по един ред. Резултатът заема [first,last) и е стабилен: еквивалентните елементи от първата серия остават пред втората.

Примерът съдържа 1,4,7 и 2,3,8; след сливането извежда 1 2 3 4 7 8. middle маркира входната граница, не запазена позиция.

Нарушаването на precondition за сортиране е undefined behavior. Нужни са двупосочни итератори и преместваеми, разменяеми стойности. Без policy достатъчно помощна памет дава точно N−1 сравнения; без буфер се използва алгоритъмът без памет до O(N log N), а другите изключения се разпространяват. При стандартна policy неприхванато изключение от елемент извиква std::terminate; липса на временна памет за паралелно изпълнение може да хвърли std::bad_alloc.

Примери

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{1, 4, 7, 2, 3, 8};
    std::inplace_merge(values.begin(), values.begin() + 3, values.end());
    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
}

Резултат

1 2 3 4 7 8 

std::inplace_merge → 1 2 3 4 7 8

Източници