Eléments répétés dans un std::vector

Question

J'ai un std::vector et je veux vérifier tous les éléments qu'il contient. Si un certain élément apparaît plus d'une fois, je signale une erreur.

Voici comment je l'ai fait :

std::vector test;
test.push_back("YES");
test.push_back("YES");

for(int i = 0; i < test.size(); i++)
{
    if(test[i] > 1)
    {
        DCS_LOG_DEBUG("ERREUR AVEC LE COMPTEUR")
    }
}

Cela n'a pas fonctionné même si je sais comment compter en utilisant la méthode std::vector::count(). Mais je veux obtenir le décompte pour chaque élément, au lieu de tout compter... des idées ?

Answer 1

La manière la plus simple est de std::sort le vecteur puis d'utiliser std::adjacent_find.

---

Cependant, si vous ne voulez pas trier le vecteur, vous pouvez faire quelque chose comme ceci en C++11:

#include 
#include  // For std::hash.
#include 
#include 

int main() {

    // Données de test.
    std::vector v;
    v.push_back("a");
    v.push_back("b");
    v.push_back("c");
    v.push_back("a");
    v.push_back("c");
    v.push_back("d");
    v.push_back("a");

    // Fonction de hachage pour la table de hachage.
    auto h = [](const std::string* s) {
        return std::hash()(*s);
    };

    // Comparateur d'égalité pour la table de hachage.
    auto eq = [](const std::string* s1, const std::string* s2) {
        return s1->compare(*s2) == 0;
    };

    // La table de hachage:
    //      Clé: Pointeur vers l'élément de 'v'.
    //      Valeur: Nombre d'occurrences.
    std::unordered_map m(v.size(), h, eq);

    // Compter les occurrences.
    for (auto v_i = v.cbegin(); v_i != v.cend(); ++v_i)
        ++m[&(*v_i)];

    // Imprimer les chaînes qui apparaissent plus d'une fois:
    for (auto m_i = m.begin(); m_i != m.end(); ++m_i)
        if (m_i->second > 1)
            std::cout << *m_i->first << ": " << m_i->second << std::endl;

    return 0;

}

Ceci imprime:

a: 3
c: 2

Je ne l'ai pas réellement testé, mais il y a des chances pour que cela soit assez performant, pour les raisons suivantes:

• En supposant que les éléments réels du vecteur ne produisent pas de hachages pathologiquement déséquilibrés, il s'agit en fait d'un algorithme en O(n), par opposition à O(n*log(n)) pour le tri.
• Nous utilisons la table de hachage de pointeurs vers des chaînes, pas les chaînes elles-mêmes, donc il n'y a pas de copie inutile qui a lieu.
• Nous pouvons "pré-allouer" les seaux de la table de hachage (nous passons v.size() lors de la construction de m), donc les redimensionnements de la table de hachage sont minimisés.

Answer 2

Élément spécifique

Le compte est la manière habituelle de procéder :

#include 
...

    if (count (test.begin(), test.end(), "YES") > 1)
        std::cerr << "positif\n";

Si vous avez besoin de plus de performance, vous pouvez le faire de manière classique :

bool existe = false;
for (const auto& v : test) {
    if (v == "YES") {
        if (existe) {
            std::cerr << "positif\n";
            break;
        }
        else existe = true;
    }
}

N'importe quel élément plusieurs fois

Pour de grands vecteurs, essayez std::set :

std::set existe;
for (const auto &v : test) {
    if (!existe.insert(v).second)
        std::cerr << "positif\n";
}

Dans cette approche, si vous voulez également pouvoir reconnaître si vous avez déjà mentionné sa non-unicité, vous pouvez utiliser std::multiset :

const std::multiset comptes (test.begin(), test.end());
for (const auto &v: test)
    if (comptes.count (v) == 2) std::cerr << "meh\n";

Si le conteneur est petit, et que vous voulez juste voir si un élément est présent plus d'une fois :

auto multitimes = [&test] (const std::string &str) {
    return count(test.begin(),test.end(),str)>1;
};
if (any_of (test.begin(), test.begin(), multitimes))
    std::cerr << "quelque chose était là plus d'une fois\n";

Answer 3

Vous pouvez utiliser std::map et définir un mapping d'une clé (string) à un compteur (int) :

#include 
#include 
/* ... */
std::map count_map;

/* ... */

count_map[key]++;

Answer 4

Utilisez std::count pour compter les éléments: http://www.cplusplus.com/reference/algorithm/count/

http://en.cppreference.com/w/cpp/algorithm/count

Answer 5

La manière la plus simple de faire ce que vous voulez est de trier le tableau, puis de voir quels éléments se répètent plus d'une fois. Si vous ne voulez pas modifier le tableau lui-même, vous devrez créer une copie. C'est une solution en O(n * lg n) sans espace supplémentaire si vous ne vous souciez pas de l'ordre, et avec un espace supplémentaire en O(n) si vous vous en souciez.

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

// Si vous vous souciez uniquement de la présence d'un élément répété, faites ceci :
int size = test.size();
unique(test.begin(), test.end());
if (test.size() != size) {
  cout << "Un élément est répété.";
}

// Si vous vous souciez des éléments qui se répètent, faites ceci :
for (unsigned index = 1; index < test.size(); ++index) {
  if (test[index] == test[index - 1] && (index == 1 || test[index - 2] != test[index])) {
     cout << test[index] << " est répété.";
  }
}

J'ai fourni deux solutions : La première est lorsque vous vous souciez uniquement de savoir si une chaîne est répétée, et la seconde est lorsque vous voulez savoir exactement quelles chaînes sont répétées.