Inplace union trié vecteurs

Question

Je voudrais une méthode efficace pour faire inplace union d'un vecteur trié avec un autre vecteur trié. Par inplace, je veux dire que l'algorithme ne doit pas créer un nouveau vecteur ou un autre stockage pour stocker l'union, même temporairement. Au lieu de cela, le premier vecteur devrait croître simplement d'exactement le nombre de nouveaux éléments.

Quelque chose comme:

void inplace_union(vector & A, const vector & B); 

Lorsque, par la suite, Un contient tous les éléments de A union Bet est triée.

std::set_union dans <algorithm> ne fonctionnera pas car il écrase sa destination, qui serait A.

Aussi, peut-il être fait avec juste un passage sur les deux vecteurs?

Edit: des éléments qui sont à la fois A et B ne doit apparaître qu'une fois dans A.

Answer 1

Oui, cela peut être fait en place, et en O (n ) temps, en supposant les deux entrées sont triées, et avec un passage sur les deux vecteurs. Voici comment:

Étendre A (le vecteur de destination) par B.size() - faire de la place pour nos nouveaux éléments.

Effectue une itération arrière sur les deux vecteurs, à partir de la fin de B et la fin d'origine de A. Si les vecteurs sont triés petit → gros (grand à la fin), alors prenez l'itérateur pointant vers le plus grand nombre, et collez-le dans la vraie fin de A. Continuez jusqu'à ce que l'itérateur B touche le début de B. Les itérateurs inversés devraient s'avérer particulièrement agréables ici.

Exemple:

A: [ 1, 2, 4, 9 ] 
B: [ 3, 7, 11 ] 

* = iterator,^= where we're inserting, _ = unitialized 
A: [ 1, 3, 4, 9*, _, _, _^ ] B: [ 3, 7, 11* ] 
A: [ 1, 3, 4, 9*, _, _^, 11 ] B: [ 3, 7*, 11 ] 
A: [ 1, 3, 4*, 9, _^, 9, 11 ] B: [ 3, 7*, 11 ] 
A: [ 1, 3, 4*, 9^, 7, 9, 11 ] B: [ 3*, 7, 11 ] 
A: [ 1, 3*, 4^, 4, 7, 9, 11 ] B: [ 3*, 7, 11 ] 
A: [ 1, 3*^, 3, 4, 7, 9, 11 ] B: [ 3, 7, 11 ] 

modifier super: Avez-vous envisagé std::inplace_merge? (que j'ai peut-être juste ré-inventé?)

Answer 2

Je crois que vous pouvez utiliser l'algorithme std::inplace_merge. Voici l'exemple de code:

void inplace_union(std::vector<int>& a, const std::vector<int>& b) 
{ 
    int mid = a.size(); //Store the end of first sorted range 

    //First copy the second sorted range into the destination vector 
    std::copy(b.begin(), b.end(), std::back_inserter(a)); 

    //Then perform the in place merge on the two sub-sorted ranges. 
    std::inplace_merge(a.begin(), a.begin() + mid, a.end()); 

    //Remove duplicate elements from the sorted vector 
    a.erase(std::unique(a.begin(), a.end()), a.end()); 
} 

Answer 3

L'idée set_difference est bonne, mais l'inconvénient est que nous ne savons pas combien nous devons développer le vecteur à l'avance.

Ceci est ma solution qui fait le set_difference deux fois, une fois pour compter le nombre d'emplacements supplémentaires dont nous aurons besoin, et une fois de plus pour faire la copie réelle.

Remarque: cela signifie que nous allons parcourir deux fois la source.

#include <algorithm> 
#include <boost/function_output_iterator.hpp> 

// for the test 
#include <vector> 
#include <iostream> 


struct output_counter 
{ 
    output_counter(size_t & r) : result(r) {} 
    template <class T> void operator()(const T & x) const { ++result; } 
private: 
    size_t & result; 
}; 


// Target is assumed to work the same as a vector 
// Both target and source must be sorted 
template <class Target, class It> 
void inplace_union(Target & target, It src_begin, It src_end) 
{ 
    const size_t mid = target.size(); // Store the end of first sorted range 

    // first, count how many items we will copy 
    size_t extra = 0; 
    std::set_difference( 
     src_begin, src_end, 
     target.begin(), target.end(), 
     boost::make_function_output_iterator(output_counter(extra))); 

    if (extra > 0) // don't waste time if nothing to do 
    { 
     // reserve the exact memory we will require 
     target.reserve(target.size() + extra); 

     // Copy the items from the source that are missing in the destination 
     std::set_difference( 
      src_begin, src_end, 
      target.begin(), target.end(), 
      std::back_inserter(target)); 

     // Then perform the in place merge on the two sub-sorted ranges. 
     std::inplace_merge(target.begin(), target.begin() + mid, target.end()); 
    } 
} 



int main() 
{ 
    std::vector<int> a(3), b(3); 
    a[0] = 1; 
    a[1] = 3; 
    a[2] = 5; 

    b[0] = 4; 
    b[1] = 5; 
    b[2] = 6; 

    inplace_union(a, b.begin(), b.end()); 

    for (size_t i = 0; i != a.size(); ++i) 
     std::cout << a[i] << ", "; 
    std::cout << std::endl; 

    return 0; 
} 

Compilé avec les en-têtes de boost, le résultat est:

$ ./test 
1, 3, 4, 5, 6,