std::merge

De 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.

Click here for the English version of this page

Bibliothèque d'algorithmes

Fonctions

Non-modification de la séquence des opérations

all_of
any_of
none_of

(C++11)
(C++11)
(C++11)

find
find_if
find_if_not

(C++11)

Modification de la séquence des opérations

(C++11)

(C++11)

(C++11)

(C++11)

remove_copy
remove_copy_if

replace
replace_if

replace_copy
replace_copy_if

random_shuffle
shuffle

(C++11)

unique

unique_copy

Des opérations de partitionnement

(C++11)

(C++11)

(C++11)

Opérations de tri (sur les gammes triés)

(C++11)

(C++11)

Opérations binaires de recherche (sur les gammes triés)

Définir les opérations (sur les gammes triés)

merge

set_symmetric_difference

Opérations Heap

(C++11)

Minimum / maximum de fonctionnement

(C++11)

(C++11)

lexicographical_compare

is_permutation

(C++11)

next_permutation

prev_permutation

Opérations numériques

(C++11)

Bibliothèque C

Déclaré dans l'en-tête `<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)

Fusionne deux gammes triés [first1, last1) et [first2, last2) dans une gamme débutant triés à d_first. La première version utilise operator< de comparer les éléments, la deuxième version utilise la fonction de comparaison donnée comp. L'ordre relatif des éléments équivalents est préservée .

Sommaire

[modifier] Paramètres

first1, last1	-	la première gamme d'éléments �� fusionner 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	-	la seconde plage d'éléments à fusionner 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	-	le début de la plage de destination 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`.

[modifier] Retourne la valeur

Un itérateur de sortie à l'élément après le dernier élément copié .

[modifier] Complexité

À la plupart des comparaisons std::distance(first1, last1) + std::distance(first2, last2) + 1 .

[modifier] Mise en œuvre possible

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);
}

[modifier] Exemple

#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';
}

Résultat :

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

[modifier] Voir aussi


inplace_merge	fusionne deux gammes commandés sur place 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. (fonction générique) [edit]

sort	trie une plage dans l'ordre ascendant 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. (fonction générique) [edit]

stable_sort	Trie une plage d'éléments, tout en préservant l'ordre entre des éléments égaux 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. (fonction générique) [edit]

Récupérée de « https://fr.cppreference.com/mwiki/index.php?title=cpp/algorithm/merge&oldid=47523 »

Langage
Concepts
Bibliothèque d'utilitaires
Bibliothèque pour les chaînes de caractères
Bibliothèque de conteneurs
Bibliothèque d'algorithmes
Bibliothèque d'itérateurs
Bibliothèque pour le calcul numérique
Bibliothèque pour les entrées/sorties
Bibliothèque pour la régionalisation
Bibliothèque pour les expressions régulières (C++11)
Bibliothèque pour les opérations atomiques (C++11)
Bibliothèque pour les processus légers (threads) (C++11)

cppreference.com

Espaces de noms

Variantes

Affichages

Actions

std::merge

Sommaire

[modifier] Paramètres

[modifier] Retourne la valeur

[modifier] Complexité

[modifier] Mise en œuvre possible

[modifier] Exemple

[modifier] Voir aussi

Navigation

Boîte à outils