Überprüfen, ob alle Elemente eines Vektors in C ++ gleich sind

Wenn ich einen Vektor, der die Werte und überprüfen möchten, dass Sie alle die gleiche, was ist der beste Weg, dies zu tun in C++ effizient? Wenn ich die Programmierung in anderen Sprachen wie R einer Art, wie mein Verstand springt, ist wieder nur die eindeutigen Elemente des Containers und dann, wenn die Länge der einzigartigen Elemente ist mehr als 1, ich kenne al die Elemente können nicht die gleichen sein. In C++ kann dies wie folgt vorgenommen:

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

Aber das Lesen über das internet und SO, sehe ich die anderen Antworten so mit einer Gruppe oder der Algorithmus find_if. Also, was ist der effizienteste Weg, dies zu tun, und warum? Ich mir vorstellen, bei mir ist das nicht der beste Weg, da es sich um das Sortieren jedes element und dann ein ändern der Größe der Vektor - aber vielleicht bin ich falsch.

Dank,
Ben.

InformationsquelleAutor der Frage Ward9250 | 2013-11-29

c++comparison element unique vector

Brauchen Sie nicht, um die Verwendung von std::sort. Es kann getan werden, einfacher

if ( std::adjacent_find( myvector.begin(), myvector.end(), std::not_equal_to<int>() ) == myvector.end() )
{
    std::cout << "All elements are equal each other" << std::endl;
}

InformationsquelleAutor der Antwort Vlad from Moscow

20

können Sie std::equal

version 1:
```
//assuming v has at least 1 element
if ( std::equal(v.begin() + 1, v.end(), v.begin()) )
{
    //all equal
}
```
Dieser vergleicht jedes element mit dem vorherigen.

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:

Bezüglich der Leistungsfähigkeit, nach dem Test mit 100m-Elemente fand ich heraus, dass in Visual Studio 2015 version 1 ist etwa doppelt so schnell wie version 2. Dies ist da die neuesten compiler für vs2015 verwendet sse-Instruktionen in c++ - std-Implementierungen wenn Sie int, float , usw..

wenn Sie _mm_testc_si128 erhalten Sie eine ähnliche Leistung zu std::equal

InformationsquelleAutor der Antwort Raxvan
11

Keine Einschränkungen auf dem Vektor, Sie haben zu Durchlaufen, der Vektor mindestens einmal, egal, der Ansatz. So wählen Sie einfach das erste element und überprüfen Sie, dass alle anderen gleich sind.

InformationsquelleAutor der Antwort Luchian Grigore
2

Sortieren ist O(NlogN) Aufgabe.

Dies ist leicht lösbar in O(N), so dass Sie Ihre aktuelle Methode ist schlecht.

Einem einfachen O(N) wäre als Luchian Grigore andeutet, Durchlaufen Sie den Vektor, der nur einmal, und vergleichen Sie jedes element auf das erste element.

InformationsquelleAutor der Antwort RichardPlunkett

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 der Antwort iNFINITEi

1

Während die asymptotische Komplexität von std::unique linear ist, die tatsächlichen Kosten der Bedienung, ist wahrscheinlich viel größer, als Sie brauchen, und es ist ein inplace-Algorithmus (es werden die Daten ändern, wie es geht).

Der Schnellste Ansatz ist zu vermuten, dass, wenn der Vektor enthält ein einzelnes element, ist es per definitionem eindeutig. Wenn der Vektor enthält mehr Elemente, dann müssen Sie nur überprüfen, ob alle von Ihnen sind genau gleich dem ersten. Dafür müssen Sie nur das erste element, das sich von der ersten unterscheidet, beginnt die Suche ab der zweiten. Wenn es ein solches element, die Elemente sind nicht eindeutig.
```
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();
```
Ist mit C++14 syntax, in ein C++11-toolchain können Sie die korrekte type in lambda. In C++03 könntest du eine Kombination von std::notstd::bind1st/std::bind2nd und std::equal an die Stelle der lambda.

Die Kosten dieses Ansatzes ist distance(start,different element) Vergleiche und keine Kopien. Erwartet und im schlechtesten Fall lineare Kosten in der Anzahl der Vergleiche (und keine Kopien!)

InformationsquelleAutor der Antwort David Rodríguez - dribeas
1

In Ihrem speziellen Fall iteriert Vektor-element und die Suche nach einem anderen element aus der erste würde reichen. Sie können sogar das Glück, zu stoppen, bevor die Bewertung aller Elemente im Vektor. (Eine while-Schleife verwendet werden könnte, aber ich geklebt mit einer for-Schleife aus Gründen der Lesbarkeit)
```
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;
    }
}
```
In Fall, dass Sie wollen wissen, wie viele verschiedene Werte der Vektor enthält, könnten Sie erstellen und überprüfen Sie die Größe, um zu sehen, wie viele verschiedene Werte im inneren:
```
std::set mySet;
std::copy(mySet.begin(), myvector.begin(), myvector.end());
```
InformationsquelleAutor der Antwort Julien B.
1

Vielleicht so etwas wie dieses. Es durchläuft die vector nur einmal und nicht Durcheinander mit der Vektor-Inhalte.
```
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();
```
Wenn die Werte in dem Vektor sind etwas anderes als die Art, die Sie implementieren müssen, um Gleichheits-operator.

InformationsquelleAutor der Antwort Rostfrei

Können Sie einfach std::count zählen alle Elemente, die mit dem Start-element:

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

InformationsquelleAutor der Antwort Tas

Können Sie 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 der Antwort Jee lee

0

der Vollständigkeit halber, weil es ist noch nicht das effizienteste, können Sie mit std::einmalig in ein effizienter Weg, um zu entscheiden, ob alle Mitglieder sind gleich, aber Vorsicht, dass nach der Verwendung von std::unique diese Weise werden die container nutzlos ist:
```
#include <algorithm>
#include <iterator>

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

Anderen Ansatz mit C++ 14:

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

ist auch um N.

InformationsquelleAutor der Antwort Batato

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.