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

std::merge

Материал из cppreference.com
< cpp‎ | algorithm

Эта страница была переведена автоматически с английской версии вики используя Переводчик Google.

Перевод может содержать ошибки и странные формулировки. Наведите курсор на текст, чтобы увидеть оригинал. Вы можете помочь в исправлении ошибок и улучшении перевода. Для инструкций перейдите по ссылке.

Щёлкните здесь, чтобы увидеть английскую версию этой страницы

 
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 функцию сравнения. Относительный порядок эквивалентных элементов сохраняется.
Оригинал:
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.
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

Содержание

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

first1, last1 -
первый ряд элементов для слияния
Оригинал:
the first range of elements to merge
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
first2, last2 -
второй ряд элементов для слияния
Оригинал:
the second range of elements to merge
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
d_first -
В начале назначения диапазона
Оригинал:
the beginning of the destination range
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
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.
Типы Type1 и Type2 должны быть таковы, что объекты типов InputIt1 и InputIt2 могут быть разыменованы и затем неявно преобразованы в Type1 и Type2 соответственно. ​

Требования к типам
-
InputIt1 должен соответствовать требованиям InputIterator.
-
InputIt2 должен соответствовать требованиям InputIterator.
-
OutputIt должен соответствовать требованиям OutputIterator.

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

Выходной итератор на элемент после последнего элемента скопировал.
Оригинал:
An output iterator to element past the last element copied.
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

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

В большинстве сравнений std::distance(first1, last1) + std::distance(first2, last2) + 1.
Оригинал:
At most std::distance(first1, last1) + std::distance(first2, last2) + 1 comparisons.
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

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

Первый вариант 
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);
}
Второй вариант 
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

[править] См. также
объединяет два приказал диапазонов на месте
Оригинал:
merges two ordered ranges in-place
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

(шаблон функции) [edit]
виды диапазон в порядке возрастания
Оригинал:
sorts a range into ascending order
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

(шаблон функции) [edit]
виды диапазон элементов при сохранении порядка между равными элементами
Оригинал:
sorts a range of elements while preserving order between equal elements
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

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