Comment rendre les éléments d'un vecteur uniques ? (supprimer les doublons non adjacents)

Question

J'ai un vecteur contenant quelques doublons non adjacents.

Prenons un exemple simple :

2 1 6 1 4 6 2 1 1

J'essaie de faire ce vector unique en supprimant les doublons non adjacents et en conservant l'ordre des éléments.

Le résultat serait :

2 1 6 4 

Les solutions que j'ai essayées sont les suivantes :

1. Insertion dans un std::set mais le problème avec cette approche est qu'elle va perturber l'ordre des éléments.
2. Utilisez la combinaison de std::sort et std::unique. Mais à nouveau, même problème d'ordre.

3. Élimination manuelle des doublons :

       Define a temporary vector TempVector.
       for (each element in a vector)
       {
           if (the element does not exists in TempVector)
           {
               add to TempVector;
           }
       }
       swap orginial vector with TempVector.

Ma question est la suivante :

Existe-t-il un algorithme STL capable de supprimer les doublons non adjacents d'un vecteur ? Quelle est sa complexité ?

Answer 1

Je pense que vous le feriez comme ça :

J'utiliserais deux itérateurs sur le vecteur :

Le premier lit les données et les insère dans un ensemble temporaire.

Lorsque les données lues ne sont pas dans l'ensemble, vous les copiez du premier itérateur au second et vous les incrémentez.

A la fin, vous ne gardez que les données jusqu'au deuxième itérateur.

La complexité est O( n .log( n ) ) car la recherche d'éléments dupliqués utilise l'ensemble et non le vecteur.

#include <vector>
#include <set>
#include <iostream>

int main(int argc, char* argv[])
{
    std::vector< int > k ;

    k.push_back( 2 );
    k.push_back( 1 );
    k.push_back( 6 );
    k.push_back( 1 );
    k.push_back( 4 );
    k.push_back( 6 );
    k.push_back( 2 );
    k.push_back( 1 );
    k.push_back( 1 );

{
    std::vector< int >::iterator r , w ;

    std::set< int > tmpset ;

    for( r = k.begin() , w = k.begin() ; r != k.end() ; ++r )
    {
        if( tmpset.insert( *r ).second )
        {
            *w++ = *r ;
        }
    }

    k.erase( w , k.end() );
}

    {
        std::vector< int >::iterator r ;

        for( r = k.begin() ; r != k.end() ; ++r )
        {
            std::cout << *r << std::endl ;
        }
    }
}

Answer 2

Sans utiliser une set il est possible de le faire avec (éventuellement) une certaine perte de performance :

template<class Iterator>
Iterator Unique(Iterator first, Iterator last)
{
    while (first != last)
    {
        Iterator next(first);
        last = std::remove(++next, last, *first);
        first = next;
    }

    return last;
}

utilisé comme dans :

vec.erase( Unique( vec.begin(), vec.end() ), vec.end() );

Pour les ensembles de données plus petits, la simplicité de la mise en œuvre et l'absence d'allocation supplémentaire requise peuvent compenser la complexité théoriquement plus élevée de l'utilisation d'un système de gestion des données supplémentaire. set . La mesure avec une entrée représentative est la seule façon d'en être sûr, cependant.

Answer 3

Comme la question était "existe-t-il un algorithme STL... ? quelle est sa complexité ?", il est logique d'implémenter la fonction de la manière suivante std::unique :

template <class FwdIterator>
inline FwdIterator stable_unique(FwdIterator first, FwdIterator last)
{
    FwdIterator result = first;
    std::unordered_set<typename FwdIterator::value_type> seen;

    for (; first != last; ++first)
        if (seen.insert(*first).second)
            *result++ = *first;
    return result;
}

Voici donc comment std::unique est mis en œuvre plus un ensemble supplémentaire. Le site unordered_set est plus rapide qu'une set . On enlève tous les éléments dont la comparaison est égale à l'élément qui les précède (le premier élément est conservé car on ne peut pas unifier vers rien). L'itérateur retourné pointe vers la nouvelle extrémité dans l'intervalle [first,last) .

EDIT : La dernière phrase signifie que le conteneur lui-même n'est PAS modifié par les éléments suivants unique . Cela peut prêter à confusion. L'exemple suivant réduit en fait le conteneur à l'ensemble unifié.

1: std::vector<int> v(3, 5);
2: v.resize(std::distance(v.begin(), unique(v.begin(), v.end())));
3: assert(v.size() == 1);

La ligne 1 crée un vecteur { 5, 5, 5 } . Dans la ligne 2 appelant unique renvoie un itérateur vers le 2ème élément, qui est le premier élément qui n'est pas unique. Par conséquent, distance renvoie 1 et resize élague le vecteur.

Answer 4

Vous pouvez supprimer certaines des boucles dans fa's répondre en utilisant remove_copy_if :

class NotSeen : public std::unary_function <int, bool>
{
public:
  NotSeen (std::set<int> & seen) : m_seen (seen) { }

  bool operator ()(int i) const  {
    return (m_seen.insert (i).second);
  }

private:
  std::set<int> & m_seen;
};

void removeDups (std::vector<int> const & iv, std::vector<int> & ov) {
  std::set<int> seen;
  std::remove_copy_if (iv.begin ()
      , iv.end ()
      , std::back_inserter (ov)
      , NotSeen (seen));
}

Cela n'a aucune incidence sur la complexité de l'algorithme (c'est-à-dire que tel qu'il est écrit, il est également O(n log n)). Vous pouvez améliorer cela en utilisant unordered_set, ou si la plage de vos valeurs est suffisamment petite, vous pouvez simplement utiliser un tableau ou un bitarray.

Answer 5

Il n'y a pas d'algorithme STL qui fasse ce que vous voulez en préservant l'ordre original de la séquence.

Vous pourriez créer un std::set d'itérateurs ou d'index dans le vecteur, avec un prédicat de comparaison qui utilise les données référencées plutôt que les itérateurs/index pour trier les choses. Ensuite, on supprime du vecteur tout ce qui n'est pas référencé dans l'ensemble. (Bien sûr, vous pourriez tout aussi bien utiliser une autre fonction std::vector d'itérateurs/index, std::sort y std::unique que, et utiliser ceci comme référence pour savoir ce qu'il faut garder).