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

CKTIS / C++

std::merge — стабилно сливане на сортирани диапазони

std::merge от <algorithm> копира два сортирани диапазона в отделен изходен диапазон. Запазва дубликатите и стабилността и връща итератор след последния записан елемент.

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

#include <algorithm>
std::merge(first1, last1, first2, last2, result);
std::merge(first1, last1, first2, last2, result, comp);

std::merge слива [first1, last1) и [first2, last2), като записва всички елементи от result нататък. И двата входа вече трябва да са сортирани по един и същ ред: по подразбиране във възходящ ред или според реда, зададен от comp. Компараторът трябва да задава строга слаба наредба. Несортираните входове нарушават предусловията на алгоритъма; функцията не сортира входовете предварително.

Сливането е стабилно: запазва реда на елементите във всеки вход, а елементите с еквивалентни ключове от първия диапазон се поставят преди тези от втория. Еквивалентност означава, че нито comp(a, b), нито comp(b, a) е истина. Дубликатите остават в изхода.

Изходният диапазон не трябва да се припокрива с нито един от входните диапазони. Осигурете място за сбора от дължините им или използвайте подходящ итератор за вмъкване. Самото извикване на reserve() за вектор не създава елементи, в които може да се записва чрез begin(). Върнатият итератор сочи позицията след последния записан елемент.

За разглежданите тук претоварвания без политика за изпълнение работата е линейна спрямо общия брой елементи N, с най-много N - 1 сравнения, когато N > 0. Не бъркайте тази функция с std::inplace_merge, която слива два съседни сортирани поддиапазона в рамките на същия диапазон. Примерът използва синтаксис, съвместим с C++23; цитираният работен проект се актуализира и може да включва и по-късни разширения.

Примери

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    const std::array<int, 3> a{1, 3, 5};
    const std::array<int, 3> b{2, 3, 6};
    std::array<int, 6> result{};

    const auto end = std::merge(a.begin(), a.end(),
                                b.begin(), b.end(), result.begin());

    for (auto it = result.begin(); it != end; ++it) {
        if (it != result.begin()) {
            std::cout << ' ';
        }
        std::cout << *it;
    }
    std::cout << '\n';
}

Резултат

1 2 3 3 5 6

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници