c++ - valores - eliminar repetidos array c

¿Cómo eliminar duplicados de std:: vector sin clasificar mientras se mantiene el orden original usando algoritmos?

Question

Tengo una matriz de enteros de la que necesito eliminar duplicados mientras mantengo el orden de la primera ocurrencia de cada entero. Puedo verlo de esta manera, pero ¿imagino que hay una forma mejor de utilizar mejor los algoritmos STL? La inserción está fuera de mi control, por lo que no puedo verificar los duplicados antes de insertarlos.

int unsortedRemoveDuplicates(std::vector<int> &numbers) {
    std::set<int> uniqueNumbers;
    std::vector<int>::iterator allItr = numbers.begin();
    std::vector<int>::iterator unique = allItr;
    std::vector<int>::iterator endItr = numbers.end();

    for (; allItr != endItr; ++allItr) {
        const bool isUnique = uniqueNumbers.insert(*allItr).second;

        if (isUnique) {
            *unique = *allItr;
            ++unique;
        }
    }

    const int duplicates = endItr - unique;

    numbers.erase(unique, endItr);
    return duplicates;
}

¿Cómo se puede hacer esto usando algoritmos STL?

Answer 1

Suena como un trabajo para std :: copy_if . Defina un predicado que realiza un seguimiento de los elementos que ya se han procesado y devuelve falso si lo tienen.

Si no tiene soporte para C ++ 11, puede usar el torpemente llamado std :: remove_copy_if e invertir la lógica.

Este es un ejemplo no probado:

template <typename T>
struct NotDuplicate {
  bool operator()(const T& element) {
    return s_.insert(element).second; // true if s_.insert(element);
  }
 private:
  std::set<T> s_;
};

Entonces

std::vector<int> uniqueNumbers;
NotDuplicate<int> pred;
std::copy_if(numbers.begin(), numbers.end(), 
             std::back_inserter(uniqueNumbers),
             std::ref(pred));

donde se usó std::ref para evitar posibles problemas con el algoritmo que copia internamente lo que es un funtor con estado, aunque std::copy_if no std::copy_if ningún requisito sobre los efectos secundarios del funtor que se aplica.

Answer 2

Esto es lo que WilliamKF está buscando. Utiliza la declaración de borrado. Este código es bueno para las listas, pero no es bueno para los vectores. Para los vectores, no debe usar la declaración de borrado.

//makes uniques in one shot without sorting !! 
template<class listtype> inline
void uniques(listtype* In)
    {

    listtype::iterator it = In->begin();
    listtype::iterator it2= In->begin();

    int tmpsize = In->size();

        while(it!=In->end())
        {
        it2 = it;
        it2++;
        while((it2)!=In->end())
            {
            if ((*it)==(*it2))
                In->erase(it2++);
            else
                ++it2;
            }
        it++;

        }
    }

Lo que he probado para vectores sin usar sort es que:

//makes vectors as fast as possible unique
template<typename T> inline
void vectoruniques(std::vector<T>* In)
    {

    int tmpsize = In->size();

        for (std::vector<T>::iterator it = In->begin();it<In->end()-1;it++)
        {
            T tmp = *it;
            for (std::vector<T>::iterator it2 = it+1;it2<In->end();it2++)
            {
                if (*it2!=*it)
                    tmp = *it2;
                else
                    *it2 = tmp;
            }
        }
        std::vector<T>::iterator it = std::unique(In->begin(),In->end());
        int newsize = std::distance(In->begin(),it);
            In->resize(newsize);
    }

De alguna manera, parece que esto funcionaría. Lo probé un poco, tal vez alguien puede decir si esto realmente funciona. Esta solución no necesita ningún operador mayor. Me refiero a por qué usar el operador más grande para buscar elementos únicos. Uso de vectores:

int myints[] = {21,10,20,20,20,30,21,31,20,20,2}; 
std::vector<int> abc(myints , myints+11);
vectoruniques(&abc);

Answer 3

Aquí hay algo que maneja los tipos POD y no POD con soporte de movimiento. Utiliza el operador predeterminado == o un predicado de igualdad personalizado. No requiere clasificación / operador <, generación de clave o un conjunto separado. No tengo idea de si esto es más eficiente que los otros métodos descritos anteriormente.

template <typename Cnt, typename _Pr = std::equal_to<typename Cnt::value_type>>
void remove_duplicates( Cnt& cnt, _Pr cmp = _Pr() )
{
    Cnt result;
    result.reserve( std::size( cnt ) );  // or cnt.size() if compiler doesn''t support std::size()

    std::copy_if( 
        std::make_move_iterator( std::begin( cnt ) )
        , std::make_move_iterator( std::end( cnt ) )
        , std::back_inserter( result )
        , [&]( const typename Cnt::value_type& what ) 
        { 
            return std::find_if( 
                std::begin( result )
                , std::end( result )
                , [&]( const typename Cnt::value_type& existing ) { return cmp( what, existing ); }
            ) == std::end( result );
        }
    );  // copy_if

    cnt = std::move( result );  // place result in cnt param
}   // remove_duplicates

Uso / pruebas:

{
    std::vector<int> ints{ 0,1,1,2,3,4 };
    remove_duplicates( ints );
    assert( ints.size() == 5 );
}

{
    struct data 
    { 
        std::string foo; 
        bool operator==( const data& rhs ) const { return this->foo == rhs.foo; }
    };

    std::vector<data>
        mydata{ { "hello" }, {"hello"}, {"world"} }
        , mydata2 = mydata
        ;

    // use operator==
    remove_duplicates( mydata );
    assert( mydata.size() == 2 );

    // use custom predicate
    remove_duplicates( mydata2, []( const data& left, const data& right ) { return left.foo == right.foo; } );
    assert( mydata2.size() == 2 );

}

Answer 4

Rápido y simple, C ++ 11:

template<typename T>
size_t RemoveDuplicatesKeepOrder(std::vector<T>& vec)
{
    std::set<T> seen;

    auto newEnd = std::remove_if(vec.begin(), vec.end(), [&seen](const T& value)
    {
        if (seen.find(value) != std::end(seen))
            return true;

        seen.insert(value);
        return false;
    });

    vec.erase(newEnd, vec.end());

    return vec.size();
}

Answer 5

La forma ingenua es usar std::set como todo el mundo te dice. Es excesivo y tiene una localidad de memoria caché pobre (lenta).
La forma inteligente * es usar std::vector adecuada (asegúrese de ver la nota al pie en la parte inferior):

#include <algorithm>
#include <vector>
struct target_less
{
    template<class It>
    bool operator()(It const &a, It const &b) const { return *a < *b; }
};
struct target_equal
{
    template<class It>
    bool operator()(It const &a, It const &b) const { return *a == *b; }
};
template<class It> It uniquify(It begin, It const end)
{
    std::vector<It> v;
    v.reserve(static_cast<size_t>(std::distance(begin, end)));
    for (It i = begin; i != end; ++i)
    { v.push_back(i); }
    std::sort(v.begin(), v.end(), target_less());
    v.erase(std::unique(v.begin(), v.end(), target_equal()), v.end());
    std::sort(v.begin(), v.end());
    size_t j = 0;
    for (It i = begin; i != end && j != v.size(); ++i)
    {
        if (i == v[j])
        {
            using std::iter_swap; iter_swap(i, begin);
            ++j;
            ++begin;
        }
    }
    return begin;
}

Entonces puedes usarlo como:

int main()
{
    std::vector<int> v;
    v.push_back(6);
    v.push_back(5);
    v.push_back(5);
    v.push_back(8);
    v.push_back(5);
    v.push_back(8);
    v.erase(uniquify(v.begin(), v.end()), v.end());
}

* Nota: Esa es la manera inteligente en casos típicos , donde la cantidad de duplicados no es demasiado alta. Para un análisis de rendimiento más completo, consulte esta respuesta relacionada a una pregunta relacionada .

Answer 6

Para verificar el rendimiento de las soluciones propuestas, he probado tres de ellas, enumeradas a continuación. Las pruebas usan vectores aleatorios con elementos de 1 mln y una relación diferente de duplicados (0%, 1%, 2%, ..., 10%, ..., 90%, 100%).

• La solución de Mehrdad , actualmente la respuesta aceptada:

  void uniquifyWithOrder_sort(const vector<int>&, vector<int>& output)
  {
      using It = vector<int>::iterator;
      struct target_less
      {
          bool operator()(It const &a, It const &b) const { return *a < *b; }
      };
  
      struct target_equal
      {
          bool operator()(It const &a, It const &b) const { return *a == *b; }
      };
  
      auto begin = output.begin();
      auto const end = output.end();
      {
          vector<It> v;
          v.reserve(static_cast<size_t>(distance(begin, end)));
          for (auto i = begin; i != end; ++i)
          {
              v.push_back(i);
          }
          sort(v.begin(), v.end(), target_less());
          v.erase(unique(v.begin(), v.end(), target_equal()), v.end());
          sort(v.begin(), v.end());
          size_t j = 0;
          for (auto i = begin; i != end && j != v.size(); ++i)
          {
              if (i == v[j])
              {
                  using std::iter_swap; iter_swap(i, begin);
                  ++j;
                  ++begin;
              }
          }
      }
  
      output.erase(begin, output.end());
  }

• La solución de juanchopanza

  void uniquifyWithOrder_set_copy_if(const vector<int>& input, vector<int>& output)
  {
      struct NotADuplicate
      {
          bool operator()(const int& element)
          {
              return _s.insert(element).second;
          }
  
      private:
          set<int> _s;
      };
  
      vector<int> uniqueNumbers;
      NotADuplicate pred;
  
      output.clear();
      output.reserve(input.size());
      copy_if(
          input.begin(),
          input.end(),
          back_inserter(output),
          ref(pred));
  }

• La solución de Leviathan

  void uniquifyWithOrder_set_remove_if(const vector<int>& input, vector<int>& output)
  {
      set<int> seen;
  
      auto newEnd = remove_if(output.begin(), output.end(), [&seen](const int& value)
      {
          if (seen.find(value) != end(seen))
              return true;
  
          seen.insert(value);
          return false;
      });
  
      output.erase(newEnd, output.end());
  }

Se modifican ligeramente para simplificar y para permitir la comparación de soluciones in situ con soluciones in situ. El código completo utilizado para probar está disponible aquí .

Los resultados sugieren que si sabe que tendrá al menos un 1% de duplicados, la solución remove_if con std::set es la mejor. De lo contrario, debe ir con la solución de sort :

// Intel(R) Core(TM) i7-2600 CPU @ 3.40 GHz 3.40 GHz
// 16 GB RAM, Windows 7, 64 bit
//
// cl 19
// /GS /GL /W3 /Gy /Zc:wchar_t /Zi /Gm- /O2 /Zc:inline /fp:precise /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /WX- /Zc:forScope /Gd /Oi /MD /EHsc /nologo /Ot 
//
// 1000 random vectors with 1 000 000 elements each.
// 11 tests: with 0%, 10%, 20%, ..., 90%, 100% duplicates in vectors.

// Ratio: 0
// set_copy_if   : Time : 618.162 ms +- 18.7261 ms
// set_remove_if : Time : 650.453 ms +- 10.0107 ms
// sort          : Time : 212.366 ms +- 5.27977 ms
// Ratio : 0.1
// set_copy_if   : Time : 34.1907 ms +- 1.51335 ms
// set_remove_if : Time : 24.2709 ms +- 0.517165 ms
// sort          : Time : 43.735 ms +- 1.44966 ms
// Ratio : 0.2
// set_copy_if   : Time : 29.5399 ms +- 1.32403 ms
// set_remove_if : Time : 20.4138 ms +- 0.759438 ms
// sort          : Time : 36.4204 ms +- 1.60568 ms
// Ratio : 0.3
// set_copy_if   : Time : 32.0227 ms +- 1.25661 ms
// set_remove_if : Time : 22.3386 ms +- 0.950855 ms
// sort          : Time : 38.1551 ms +- 1.12852 ms
// Ratio : 0.4
// set_copy_if   : Time : 30.2714 ms +- 1.28494 ms
// set_remove_if : Time : 20.8338 ms +- 1.06292 ms
// sort          : Time : 35.282 ms +- 2.12884 ms
// Ratio : 0.5
// set_copy_if   : Time : 24.3247 ms +- 1.21664 ms
// set_remove_if : Time : 16.1621 ms +- 1.27802 ms
// sort          : Time : 27.3166 ms +- 2.12964 ms
// Ratio : 0.6
// set_copy_if   : Time : 27.3268 ms +- 1.06058 ms
// set_remove_if : Time : 18.4379 ms +- 1.1438 ms
// sort          : Time : 30.6846 ms +- 2.52412 ms
// Ratio : 0.7
// set_copy_if   : Time : 30.3871 ms +- 0.887492 ms
// set_remove_if : Time : 20.6315 ms +- 0.899802 ms
// sort          : Time : 33.7643 ms +- 2.2336 ms
// Ratio : 0.8
// set_copy_if   : Time : 33.3077 ms +- 0.746272 ms
// set_remove_if : Time : 22.9459 ms +- 0.921515 ms
// sort          : Time : 37.119 ms +- 2.20924 ms
// Ratio : 0.9
// set_copy_if   : Time : 36.0888 ms +- 0.763978 ms
// set_remove_if : Time : 24.7002 ms +- 0.465711 ms
// sort          : Time : 40.8233 ms +- 2.59826 ms
// Ratio : 1
// set_copy_if   : Time : 21.5609 ms +- 1.48986 ms
// set_remove_if : Time : 14.2934 ms +- 0.535431 ms
// sort          : Time : 24.2485 ms +- 0.710269 ms

// Ratio: 0
// set_copy_if   : Time: 666.962 ms +- 23.7445 ms
// set_remove_if : Time: 736.088 ms +- 39.8122 ms
// sort          : Time: 223.796 ms +- 5.27345 ms
// Ratio: 0.01
// set_copy_if   : Time: 60.4075 ms +- 3.4673 ms
// set_remove_if : Time: 43.3095 ms +- 1.31252 ms
// sort          : Time: 70.7511 ms +- 2.27826 ms
// Ratio: 0.02
// set_copy_if   : Time: 50.2605 ms +- 2.70371 ms
// set_remove_if : Time: 36.2877 ms +- 1.14266 ms
// sort          : Time: 62.9786 ms +- 2.69163 ms
// Ratio: 0.03
// set_copy_if   : Time: 46.9797 ms +- 2.43009 ms
// set_remove_if : Time: 34.0161 ms +- 0.839472 ms
// sort          : Time: 59.5666 ms +- 1.34078 ms
// Ratio: 0.04
// set_copy_if   : Time: 44.3423 ms +- 2.271 ms
// set_remove_if : Time: 32.2404 ms +- 1.02162 ms
// sort          : Time: 57.0583 ms +- 2.9226 ms
// Ratio: 0.05
// set_copy_if   : Time: 41.758 ms +- 2.57589 ms
// set_remove_if : Time: 29.9927 ms +- 0.935529 ms
// sort          : Time: 54.1474 ms +- 1.63311 ms
// Ratio: 0.06
// set_copy_if   : Time: 40.289 ms +- 1.85715 ms
// set_remove_if : Time: 29.2604 ms +- 0.593869 ms
// sort          : Time: 57.5436 ms +- 5.52807 ms
// Ratio: 0.07
// set_copy_if   : Time: 40.5035 ms +- 1.80952 ms
// set_remove_if : Time: 29.1187 ms +- 0.63127 ms
// sort          : Time: 53.622 ms +- 1.91357 ms
// Ratio: 0.08
// set_copy_if   : Time: 38.8139 ms +- 1.9811 ms
// set_remove_if : Time: 27.9989 ms +- 0.600543 ms
// sort          : Time: 50.5743 ms +- 1.35296 ms
// Ratio: 0.09
// set_copy_if   : Time: 39.0751 ms +- 1.71393 ms
// set_remove_if : Time: 28.2332 ms +- 0.607895 ms
// sort          : Time: 51.2829 ms +- 1.21077 ms
// Ratio: 0.1
// set_copy_if   : Time: 35.6847 ms +- 1.81495 ms
// set_remove_if : Time: 25.204 ms +- 0.538245 ms
// sort          : Time: 46.4127 ms +- 2.66714 ms

Answer 7

Aquí hay una versión genérica de c ++ 11 que funciona con iteradores y no asigna almacenamiento adicional. Puede tener la desventaja de ser O (n ^ 2) pero es más rápido para tamaños de entrada más pequeños.

template<typename Iter>
Iter removeDuplicates(Iter begin,Iter end)
{
    auto it = begin;
    while(it != end)
    {
        auto next = std::next(it);
        if(next == end)
        {
            break;
        }
        end = std::remove(next,end,*it);
        it = next;
    }

    return end;
}

....

std::erase(removeDuplicates(vec.begin(),vec.end()),vec.end());

Código de muestra: http://cpp.sh/5kg5n

Answer 8

int unsortedRemoveDuplicates(std::vector<int>& numbers)
{
    std::set<int> seenNums; //log(n) existence check

    auto itr = begin(numbers);
    while(itr != end(numbers))
    {
        if(seenNums.find(*itr) != end(seenNums)) //seen? erase it
            itr = numbers.erase(itr); //itr now points to next element
        else
        {
            seenNums.insert(*itr);
            itr++;
        }
    }

    return seenNums.size();
}


//3 6 3 8 9 5 6 8
//3 6 8 9 5