définir la différence pour les doublons dans la deuxième plage, alternative remove_copy

Question

J'ai deux tableaux ou vecteurs, par exemple :

  int first[] = {0,0,1,1,2,2,3,3,3};
  int second[] = {1,3};

J'aimerais me débarrasser des 1 et des 3 de la première série, set_difference ne peut se débarrasser que des premières occurrences de ces valeurs, mais ce n'est pas ce que je veux obtenir.

Dois-je le faire avec supprimer_copie en itérant sur la deuxième plage et en retirant à chaque fois une entrée du premier ensemble.

Quelle serait la meilleure façon de faire cela en C++ ?

Answer 1

Écrire un set_différence spécialisé :

template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator set_difference_any( InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result )
{
  while ( first1 != last1 && first2 != last2 )
    if ( *first1 < *first2 ) {
      *result = *first1;
      ++first1;
      ++result;
    } else if ( *first2 < *first1 ) {
      ++first2;
    } else {
      ++first1;
      //++first2; // this is the difference to set_difference
    }
  return std::copy( first1, last1, result );
}

Puis, appliquez-la au problème :

#include "set_difference_any.h"
#include <boost/range.hpp>
#include <iterator>
#include <vector>

std::vector<int> result;
set_difference_any( boost::begin( first ), boost::end( first ),
                    boost::begin( second ), boost::end( second ),
                    std::back_inserter( result ) );

Cet algorithme est linéaire (max. last1-first1 + last2-first2 comparaisons)

Answer 2

Vous devez écrire une fonction simple ou fonctionnelle qui renvoie true si l'élément est dans second y false autrement (appelons-le ok ). Et ensuite, utilisez std::remove_if o std::remove_copy_if :

first.erase(std::remove_if(first.begin(), first.end(), ok));

P.S. a considéré que first es std::vector<int> et non un tableau.

Answer 3

Êtes-vous sûr que set_difference ne fonctionnera pas ? La norme dans 25.3.5 dit

Cette section définit tous les paramètres de base sur des structures triées. Elles fonctionnent également avec les multi-ensembles contenant contenant des copies multiples d'éléments éléments équivalents.

Et la description de set_difference dit juste qu'il vous donne tout en premier et non en second, ce qui est ce que vous voulez.

Answer 4

La solution générale, pour lorsque second a plus que quelques éléments : faire un std::set (ou unordered_set ) des éléments dans second puis boucle à travers first en supprimant tout ce qui n'est pas l'ensemble. (Par boucle, j'entends for , while , remove_if ou autre).