Comment supprimer les doublons de std :: vector non triés tout en conservant la commande d'origine en utilisant des algorithmes?

J'ai un tableau d'entiers que j'ai besoin de supprimer les doublons tout en maintenant la commande de la première occurrence de chaque entier. Je peux voir faire comme cela, mais imaginer qu'il y est une meilleure manière qui rend l'utilisation des algorithmes de la STL mieux? L'insertion est hors de mon contrôle, je ne peux donc pas vérifier les doublons avant de l'insérer.

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

Comment cela peut être fait en utilisant des algorithmes de la STL?

source d'informationauteur WilliamKF | 2012-08-30

  1. 10

    La naïf façon est d'utiliser des std::set comme tout le monde vous dira. C'est exagéré, et a une mauvaise localité de cache (lent).

    Le smart* façon est d'utiliser des std::vector de manière appropriée (assurez-vous de voir la note au bas):

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

    Alors vous pouvez l'utiliser comme:

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

    *Remarque: C'est la façon intelligente dans les cas typiquesoù le nombre de doublons n'est pas trop élevé. Pour approfondir l'analyse de la performance, voir cette réponse à une question relative à la.

  2. 15

    Sonne comme un travail pour std::copy_if. Définir un prédicat qui garde une trace des éléments qui ont déjà été traitées et retournera false si ils en ont.

    Si vous n'avez pas de C++11, vous pouvez utiliser les maladroitement nommé std::remove_copy_if et inverser la logique.

    C'est non testé exemple:

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

    Puis

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

    où un std::ref a été utilisé pour éviter d'éventuels problèmes avec l'algorithme interne de copier ce qui est avec un état de foncteur, bien que std::copy_if ne place pas les exigences sur les effets secondaires du foncteur d'être appliquée.

  3. 7
    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
  4. 4

    Simple et rapide, 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();
}