Пространства имён
Варианты
Действия

std::merge

Материал из cppreference.com

This page has been machine-translated from the English version of the wiki using Google Translate.

The translation may contain errors and awkward wording. Hover over text to see the original version. You can help to fix errors and improve the translation. For instructions click here.

 
C++
 
Алгоритмы
Функции
Немодифицирующие линейные операции
Модифицирующие линейные операции
Разделение
Сортировка (на отсортированных промежутках)
Бинарный поиск (на отсортированных промежутках)
Множества (на отсортированных промежутках)
Куча
Минимум/максимум
Числовые операции
Библиотека C
 
Заголовочный файл <algorithm>
template< class InputIt1, class InputIt2, class OutputIt >

OutputIt merge( InputIt1 first1, InputIt1 last1,
                InputIt2 first2, InputIt2 last2

                OutputIt d_first );
 (1)
template< class InputIt1, class InputIt2, class OutputIt, class Compare>

OutputIt merge( InputIt1 first1, InputIt1 last1,
                InputIt2 first2, InputIt2 last2

                OutputIt d_first, Compare comp );
 (2)
Объединяет два отсортированных диапазонах [first1, last1) и [first2, last2) в один отсортированный диапазон начало в d_first. Первый вариант используется operator< для сравнения элементов, вторая версия использует данную comp функцию сравнения. Относительный порядок эквивалентных элементов сохраняется.
Original:
Merges two sorted ranges [first1, last1) and [first2, last2) into one sorted range beginning at d_first. The first version uses operator< to compare the elements, the second version uses the given comparison function comp. The relative order of equivalent elements is preserved.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Содержание

[править] Параметры

first1, last1 -
первый ряд элементов для слияния
Original:
the first range of elements to merge
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
first2, last2 -
второй ряд элементов для слияния
Original:
the second range of elements to merge
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
d_first -
В начале назначения диапазона
Original:
the beginning of the destination range
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
comp - comparison function which returns ​true if the first argument is less than the second.

The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function must not modify the objects passed to it.
The types  Type1 and  Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to  Type1 and  Type2 respectively. ​

Type requirements
-
InputIt1 must meet the requirements of InputIterator.
-
InputIt2 must meet the requirements of InputIterator.
-
OutputIt must meet the requirements of OutputIterator.

[править] Возвращаемое значение

Выходной итератор на элемент после последнего элемента скопировал.
Original:
An output iterator to element past the last element copied.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[править] Сложность

В большинстве сравнений std::distance(first1, last1) + std::distance(first2, last2) + 1.
Original:
At most std::distance(first1, last1) + std::distance(first2, last2) + 1 comparisons.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[править] Возможная реализация

First version 
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first)
{
    for (; first1 != last1; ++d_first) {
        if (first2 == last2) {
            return std::copy(first1, last1, d_first);
        }
        if (*first2 < *first1) {
            *d_first = *first2;
            ++first2;
        } else {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}
Second version 
template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first, Compare comp)
{
    for (; first1 != last1; ++d_first) {
        if (first2 == last2) {
            return std::copy(first1, last1, d_first);
        }
        if (comp(*first2, *first1)) {
            *d_first = *first2;
            ++first2;
        } else {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

[править] Пример

#include <iostream>
#include <iterator>
#include <cstdlib>
#include <algorithm>
#include <vector>
 
int main()
{
    const std::size_t items = 10;
 
    std::vector<int> v1, v2, dst;
 
    // fill the vectors
    for (std::size_t idx = 0; idx < items; ++idx) {
        v1.push_back(std::rand()%items);
        v2.push_back(std::rand()%items);
    }
 
    // sort
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
 
    // output v1
    std::cout << "v1 : ";
    std::copy(v1.begin(), v1.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    // output v2
    std::cout << "v2 : ";
    std::copy(v2.begin(), v2.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    // merge
    std::merge(v1.begin(), v1.end(),
               v2.begin(), v2.end(),
               std::back_inserter(dst));
 
    // output
    std::cout << "dst: ";
    std::copy(dst.begin(), dst.end(),
             std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

Вывод: 

v1 : 0 0 2 2 3 3 3 6 7 9
v2 : 1 2 5 5 6 6 6 6 7 9
dst: 0 0 1 2 2 2 3 3 3 5 5 6 6 6 6 6 7 7 9 9

[править] См. также
объединяет два приказал диапазонов на месте
Original:
merges two ordered ranges in-place
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

(шаблон функции) [edit]
виды диапазон в порядке возрастания
Original:
sorts a range into ascending order
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

(шаблон функции) [edit]
виды диапазон элементов при сохранении порядка между равными элементами
Original:
sorts a range of elements while preserving order between equal elements
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

(шаблон функции) [edit]
Источник — «http://ru.cppreference.com/mwiki/index.php?title=cpp/algorithm/merge&oldid=30512»