comment trouver les doublons dans std::vector<string>, et de renvoyer une liste d'entre eux?

De l'OMI, Ben Voigt a commencé avec une bonne idée de base, mais je vous déconseille de prendre sa formulation trop littéralement.

En particulier, je n'aime pas l'idée de chercher une chaîne de caractères dans le jeu, puis de l'ajouter à votre jeu si il n'est pas présent, et en l'ajoutant à la sortie si les, il était présent. Cela signifie essentiellement que chaque fois que nous les rencontrons un nouveau mot, nous sommes la recherche de notre ensemble de mots existants, une fois pour vérifier si un mot est présent, et à nouveau à insérer parce qu'il ne l'était pas. La plupart de cette recherche sera essentiellement identiques, à moins qu'un autre thread mutation de la structure dans l'intervalle (ce qui pourrait donner une race condition).

Au lieu de cela, j'aimerais commencer par essayer de l'ajouter à l'ensemble des mots que vous avez vu. Qui renvoie un pair<iterator, bool>, avec la bool ensemble de true si et seulement si la valeur a été inséré -- c'est à dire, ne l'a pas déjà présent. Qui nous permet de consolider la recherche d'une chaîne existante et de l'insertion de la nouvelle chaîne de caractères en un seul insert:

while (input >> word)
    if (!(existing.insert(word)).second)
        output.insert(word);

Ce nettoie également le débit suffisant qu'il est assez facile de transformer l'essai en un foncteur que nous pouvons ensuite utiliser avec std::remove_copy_if pour produire nos résultats assez directement:

#include <set>
#include <iterator>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>

class show_copies {
    std::set<std::string> existing;
public:
    bool operator()(std::string const &in) {
        return existing.insert(in).second;
    }
};

int main() {
    std::vector<std::string> words{ "words", "words", "are", "fun", "fun" };
    std::set<std::string> result;

    std::remove_copy_if(words.begin(), words.end(),
        std::inserter(result, result.end()), show_copies());

    for (auto const &s : result)
        std::cout << s << "\n";
}

En fonction de si je m'en souciais plus sur la simplicité du code ou de la vitesse d'exécution, je pourrais utiliser un std::vector au lieu de la set pour le résultat, et l'utilisation std::sort suivie par std::unique_copy pour produire le résultat final. Dans un tel cas, je serais probablement aussi remplacer le std::set à l'intérieur de show_copies avec un std::unordered_set à la place:

#include <unordered_set>
#include <iterator>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>

class show_copies {
    std::unordered_set<std::string> existing;
public:
    bool operator()(std::string const &in) {
        return existing.insert(in).second;
    }
};

int main() {
    std::vector<std::string> words{ "words", "words", "are", "fun", "fun" };
    std::vector<std::string> intermediate;

    std::remove_copy_if(words.begin(), words.end(),
        std::back_inserter(intermediate), show_copies());

    std::sort(intermediate.begin(), intermediate.end());
    std::unique_copy(intermediate.begin(), intermediate.end(),
        std::ostream_iterator<std::string>(std::cout, "\n"));
}

C'est un peu plus complexe (une ligne entière de plus!) mais probablement beaucoup plus vite quand/si le nombre de mots devient très grande. Notez également que je suis en utilisant std::unique_copy principalement pour produire visible de sortie. Si vous voulez juste le résultat dans une collection, vous pouvez utiliser le standard unique/effacement de l'idiome à obtenir des éléments uniques dans intermediate.

OriginalL'auteur Jerry Coffin

En place (pas d'espace de stockage supplémentaire). Aucune chaîne de la copie (à l'exception de la liste des résultats). Un tri + un pass:

#include <string>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
        vector<string> vec{"words", "words", "are", "fun", "fun"};
        list<string> dup;

        sort(vec.begin(), vec.end());

        const string  empty{""};
        const string* prev_p = &empty;

        for(const string& s: vec) {
                if (*prev_p==s) dup.push_back(s);
                prev_p = &s;
        }

        for(auto& w: dup) cout << w << ' '; 
        cout << '\n';
}

OriginalL'auteur Leonid Volnitsky

Voici un meilleur algorithme que celles d'autres personnes ont proposé:

#include <algorithm>
#include <vector>

template<class It> It unique2(It const begin, It const end)
{
    It i = begin;
    if (i != end)
    {
        It j = i;
        for (++j; j != end; ++j)
        {
            if (*i != *j)
            { using std::swap; swap(*++i, *j); }
        }
        ++i;
    }
    return i;
}
int main()
{
    std::vector<std::string> v;
    v.push_back("words");
    v.push_back("words");
    v.push_back("are");
    v.push_back("fun");
    v.push_back("words");
    v.push_back("fun");
    v.push_back("fun");
    std::sort(v.begin(), v.end());
    v.erase(v.begin(), unique2(v.begin(), v.end()));
    std::sort(v.begin(), v.end());
    v.erase(unique2(v.begin(), v.end()), v.end());
}

C'est mieux, car il ne nécessite swap sans auxiliaire vector pour le stockage, ce qui signifie qu'il se comporte de façon optimale pour des versions antérieures de C++, et il ne nécessite pas d'éléments pour être copiable.

Si vous êtes plus intelligent, je pense que vous pouvez éviter le tri le vecteur à deux reprises.

OriginalL'auteur Mehrdad