Vérifier si tous les éléments d'un vecteur sont égaux en C++

Si j'ai un vecteur de valeurs et que vous souhaitez vérifier qu'ils sont tous les mêmes, quelle est la meilleure façon de le faire en C++ de manière efficace? Si je ont été de programmation dans un autre langage comme le R d'une façon mes esprits des sauts est à retourner uniquement les éléments du conteneur et puis si la longueur des éléments uniques de plus de 1, je sais que tous les éléments ne peuvent pas être les mêmes. En C++, ce qui peut être fait comme ceci:

//build an int vector
std::sort(myvector.begin(), myvector.end());
std::vector<int>::iterator it;
//Use unique algorithm to get the unique values.
it = std::unique(myvector.begin(), myvector.end());
positions.resize(std::distance(myvector.begin(),it));
if (myvector.size() > 1) {
    std::cout << "All elements are not the same!" << std::endl;
}

Cependant la lecture sur internet et DONC, je vois d'autres réponses telles que l'utilisation d'un jeu ou de la find_if algorithme. Alors, quel est le moyen le plus efficace de le faire et pourquoi? J'imagine que le mien n'est pas la meilleure façon puisqu'il s'agit de tri de chaque élément, puis un redimensionnement du vecteur - mais peut-être que je me trompe.

Grâce,
Ben.

Ceci a été demandé avant: stackoverflow.com/questions/15531258/... Les réponses à souligner, surtout, que l'efficacité dans l'O(n) comparer-tous-pour-la-première méthode peut être acquise en vous assurant de casser la boucle une fois que vous trouver le premier élément qui n'est pas égal.
Tableau version: stackoverflow.com/questions/14120346/... est un sous-ensemble via data().

InformationsquelleAutor Ward9250 | 2013-11-29

c++comparison element unique vector

47

Vous n'avez pas besoin d'utiliser std::sort. Il peut être fait d'une manière simple:
```
if ( std::adjacent_find( myvector.begin(), myvector.end(), std::not_equal_to<>() ) == myvector.end() )
{
    std::cout << "All elements are equal each other" << std::endl;
}
```
- J'étais près de l'affichage d'une solution à l'aide de adjacent_find, mais la mienne aurait présenté un lambda de prédicat, c'est pourquoi je n'ai pas le publier à la fin. not_equal_to était la pièce manquante qui en fait une belle solution.
- Il est étrange que personne n'a mentionné std::all_of.:)
- Votre commentaire suggère il y a une meilleure solution à l'aide de all_of. Si oui, pourriez-vous (ou quelqu'un) de modifier votre réponse à montrer?
InformationsquelleAutor Vlad from Moscow
25

vous pouvez utiliser std::égalité

version 1:
```
//assuming v has at least 1 element
if ( std::equal(v.begin() + 1, v.end(), v.begin()) )
{
    //all equal
}
```
Cela permettra de comparer chaque élément avec la précédente.

version 2:
```
//assuming v has at least 1 element
int e = v[0]; //preferably "const auto& e" instead
bool all_equal = true;
for(std::size_t i = 1,s = v.size();i<s && all_equal;i++)
    all_equal = e == v[i];
```
Edit:

Ce qui concerne la performance, après essai avec 100 millions d'éléments, j'ai découvert que dans Visual Studio 2015 version 1 est deux fois plus rapide que version 2. C'est parce que le compilateur pour vs2015 utilise le jeu d'instructions sse en c++ std implémentations lorsque vous utilisez ints, float , etc..

si vous utilisez _mm_testc_si128 vous permettra d'obtenir une performance similaire à std::equal
- Moins efficace que de simplement en parcourant le tableau, comme vous êtes l'incrémentation de 2 itérateurs en interne.
- Grigore oui , mais c'est plus court à écrire 🙂
- Vrai, mais "quel est Donc le moyen le plus efficace de le faire et pourquoi?"
- Grigore ok , je vais le modifier pour ajouter quelque chose qui est efficace.
- notez que tout en bas, il lui demande de "plus efficen"t, jusqu'au sommet, il lui demande de la "meilleure façon", sous réserve d'être en c++ et efficace. Le "meilleur moyen" permet de considérer le style, la lisibilité et tels, tandis que l'équilibrage contre un possible facteur de 2 à ralentir.
InformationsquelleAutor Raxvan
11

Donné aucune contrainte sur le vecteur, vous avez à parcourir le vecteur au moins une fois, peu importe l'approche. Donc il suffit de choisir le premier élément et vérifiez que toutes les personnes sont égales.
- N'oubliez pas de court-circuit après vous trouvez une valeur inégale à la première!
InformationsquelleAutor Luchian Grigore
2

De tri est un O(NlogN) de la tâche.

C'est facilement résoluble en temps O(N), de sorte que votre méthode actuelle est mauvaise.

Une simple O(N) serait aussi Luchian Grigore suggère, parcourir le vecteur, juste une fois, à comparer chaque élément vers le premier élément.

InformationsquelleAutor RichardPlunkett
2

Alors que la complexité asymptotique de std::unique est linéaire, le coût réel de l'opération est probablement beaucoup plus grand que vous avez besoin, et c'est une place algorithme (il va modifier les données comme il va).

La manière la plus rapide de l'approche est de supposer que si le vecteur contient un seul élément, il est unique par définition. Si le vecteur contient plus d'éléments, alors vous avez juste besoin de vérifier s'ils sont tous exactement égale à la première. Pour cela, vous avez seulement besoin de trouver le premier élément qui diffère de la première, en commençant la recherche à partir de la deuxième. Si il y a un tel élément, les éléments ne sont pas uniques.
```
if (v.size() < 2) return true;
auto different = std::find_if(v.begin()+1, v.end(), 
                              [&v](auto const &x) { x != v[0]; });
return different == v.end();
```
C'est à l'aide de C++14 de la syntaxe, en C++11 de la chaîne, vous pouvez utiliser le bon type dans le lambda. En C++03, vous pouvez utiliser une combinaison de std::not, std::bind1st/std::bind2nd et std::equal en place de la lambda.

Le coût de cette approche est distance(start,different element) comparaisons et pas de copies. Attend et pire des cas linéaire des coûts dans le nombre de comparaisons (et pas des copies!)
- Déclaration d'ouverture est trompeuse. Oui Unique est linéaire, mais il a suivi sur un tri, ce qui n'est absolument pas linéaire.
- Si votre seul espoir est de détecter s'il existe une valeur unique ou pas, vous n'avez pas besoin de trier. Notez que ce n'est pas de tenter de résoudre le problème générique de la suppression des doublons ou de trouver le nombre de valeurs unique il y a, mais plutôt de trouver s'il existe au moins un non-valeur en double. Peut-être que je devrait en faire plus explicite dans la réponse... même si c'est juste un commentaire sur la question de l'approche, plutôt que de ma propre approche.
InformationsquelleAutor David Rodríguez - dribeas

if(std::all_of(myvector.begin()+1, myvector.end(), std::bind(std::equal_to<int>(),
                                      std::placeholders::_1, myvector.front())) {
  //all members are equal
}

InformationsquelleAutor iNFINITEi

1

Dans votre cas particulier, une itération sur élément du vecteur et de trouver un élément différent du premier, serait suffisant. Vous pouvez même avoir la chance de s'arrêter avant l'évaluation de tous les éléments de votre vecteur. (Une boucle while peut être utilisé, mais j'ai ensuite collé avec une boucle for pour des raisons de lisibilité)
```
bool uniqueElt = true;
int firstItem = *myvector.begin();
for (std::vector<int>::const_iterator it = myvector.begin()+1; it != myvector.end() ; ++it) {
    if(*it != firstItem) {
        uniqueElt = false;
        break;
    }
}
```
Dans le cas où vous voulez savoir combien de valeurs différentes de votre vecteur contient, vous pourriez construire un ensemble et vérifier sa taille afin de voir comment de nombreuses valeurs différentes sont à l'intérieur:
```
std::set mySet;
std::copy(mySet.begin(), myvector.begin(), myvector.end());
```
- Pourquoi est-ce plus efficace que juste une itération à travers le vecteur?
- il n'est pas, et, en général, est aussi mauvais que le tri.
- Il n'est pas, je n'ai pas eu le temps d'élaborer ma réponse pour l'instant. Cependant, je pense que c'est utile pour Ward9250 à savoir que la construction d'un ensemble serait une possibilité, s'il était à la recherche de plus d'une valeur unique.
InformationsquelleAutor Julien B.
1

Vous pouvez simplement utiliser std::count à compter tous les éléments qui correspondent à l'élément de départ:
```
std::vector<int> numbers = { 5, 5, 5, 5, 5, 5, 5 };
if (std::count(std::begin(numbers), std::end(numbers), numbers.front()) == numbers.size())
{
    std::cout << "Elements are all the same" << std::endl;
}
```
- Je ne vois pas comment ce est tout "simple" que tous les autres moyens posté le 4 ans plus tôt. En fait, c'est une perte de temps parce que count a continuer, même après avoir trouvé le 1er différents élément, mais vous avez seulement besoin de savoir si il y en avait un, de sorte que ceux-ci sont purement gaspillage de cycles.
- Vous soulevez un bon point, à l'époque, je n'avais pas considéré qu'il itérer sur tous les éléments; toutefois, de nombreuses autres solutions de faire de même, et je ne prétend pas que c'est la meilleure méthode de faire, mais j'ai rencontré ce problème et trouvé ceci pour être le plus lisible solution. Si un vector est très grand alors qu'il serait certainement utile d'utiliser une solution qui ne serait pas itérer sur tous les éléments.
InformationsquelleAutor Tas

Vous pouvez utiliser FunctionalPlus(https://github.com/Dobiasd/FunctionalPlus):

std::vector<std::string> things = {"same old", "same old"};
if (fplus::all_the_same(things))
    std::cout << "All things being equal." << std::endl;

InformationsquelleAutor Jee lee

1

Peut-être quelque chose comme ça. Il traverse vecteur, juste une fois, ne plaisante pas avec le vecteur de contenu.
```
std::vector<int> values { 5, 5, 5, 4 };
bool equal = std::count_if(values.begin(), values.end(), [ &values ] (auto size) { return size == values[0]; }) == values.size();
```
Si les valeurs du vecteur sont quelque chose de différent type de base que vous avez à mettre en œuvre l'égalité de l'opérateur.

Après prise en compte de underscore_d remarques, je vais changer les solution possible
```
std::vector<int> values { 5, 5, 5, 4 };
bool equal = std::all_of(values.begin(),values.end(),[ &values ] (auto item) { return item == values[0]; });
```
- C'est aussi un gaspillage de temps, car count a continuer, même après avoir trouvé le 1er différents élément, mais vous avez seulement besoin de savoir si il y en avait un, de sorte que ceux qui sont gaspillées cycles. Je ne vois pas pourquoi nous avions besoin d'une mauvaise alternative 4 ans plus tard.
- D'accord. Vous avez raison.
InformationsquelleAutor Rostfrei
0

par souci d'exhaustivité, car il n'est pas toujours la plus efficace, vous pouvez utiliser std::unique dans un moyen plus efficace pour décider si tous les membres sont les mêmes, mais méfiez-vous qu'après l'utilisation de std::unique cette façon, le conteneur est inutile:
```
#include <algorithm>
#include <iterator>

if (std::distance(cntnr.begin(), std::unique(cntnr.begin(), cntnr.end()) == 1)
{
  //all members were the same, but
}
```
InformationsquelleAutor stefaanv

Une autre approche à l'aide de C++ 14:

bool allEqual = accumulate(v.begin(), v.end(), true, [first = v[0]](bool acc, int b) {
    return acc && (b == first);
  });

qui est aussi d'ordre N.

InformationsquelleAutor Batato

Vous devez vous connecter pour publier un commentaire.