C++ mehrere Int Variablen mit einander vergleichen

[agneu (Gast)]

Hallo zusammen,

ich stehe gerade ein bisschen auf dem Schlauch. Ich möchte gerne 10 
integer Variablen auf Ungleichheit überprüfen und mir fällt gerade nicht 
ein wie ich das am besten lösen könnte ohne jede Bedingung händisch 
abzuklopfen.

Hat jemand von euch vielleicht eine Idee.

Vielen lieben Dank schon mal.

[Wolfgang (Gast)]

agneu schrieb:
> Ich möchte gerne 10 integer Variablen auf Ungleichheit überprüfen und mir
> fällt gerade nicht ein wie ich das am besten lösen könnte ohne jede
> Bedingung händisch abzuklopfen.

Wenn du sie unbedingt als Einzelvariablen deklarieren musst, wird dir 
nichts anderes übrig bleiben.

[Christian B. (casandro)]

Abhängig von der Art und Weise wie die deklariert sind könntest Du auch 
auf die erste Variable einen Zeiger machen und den dann weiter zählen... 
das wäre aber die C-Variante.

Willst Du echtes C++ machen, so definierst Du die Integer als Klassen 
und machst einen Iterator und kannst damit das Problem sicherlich schon 
in 200-500 Zeilen lösen.

Ich persönlich finde es problematisch wenn man C++ als Lehrsprache 
verwendet.

[Daniel A. (daniel-a)]

// ungetestet
#include <stddef.h>
#include <stdbool.h>
#include <stdio.h>

int main(){
  int nums[] = {1,2,3,4,5,6,7,8,9,0};
  size_t num_count = sizeof(nums)/sizeof(*nums);
  size_t i,j;
  bool unique=true;
  for( i=0; i < num_count; i++ )
    for( j=i+1; j < num_count; j++ )
      if( nums[j] == nums[i] ){
        unique = false;
        break;
      }
  if( unique ){
    printf("every number is unique\n");
  }else{
    printf("not every number is unique\n");
  }
  return 0;
}

[Hans (Gast)]

Das kommt drauf an, wo die Variablen liegen. Wenn sie in einem 
Standard-Container wie std::vector untergebracht sind, kannst Du einfach 
die beiden Container mit "==" vergleichen.

Wenn Du nur den Teil eines Containters oder auch C-Arrays vergleichen 
willst, kannst Du std::equal benutzen. Oder Du schreibst eben selber 
eine Schleife ...

[Rufus Τ. F. (rufus)]

Wenn bei Daniels Beispiel die innere Schleife abgebrochen wird (wenn 
"unique" auf false gesetzt wird), ist es sinnlos, die äußere Schleife 
weiterlaufen zu lassen. Also sollte eine Überprüfung von "unique" in die 
Schleifenabbruchbedingung (i < num_count) einfließen.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

agneu schrieb:
> Hat jemand von euch vielleicht eine Idee.

Einfachster Algorithmus wäre, du gehst mit jedem Wert durch die ganze 
Liste. Das kann man optimieren, in dem man nur noch die Elemente hinter 
dem betrachteten Element durchsucht, da ein Duplikat vor dem 
betrachtetem Element, vorher schon aufgefallen wäre:

#include <algorithm>
#include <initializer_list>
#include <cassert>

template < class Iter >
bool contains_duplicates( Iter begin, Iter end )
{
    if ( begin == end )
        return false;

    for ( ; begin != end; )
    {
        const auto value = *begin;
        ++begin;

        if ( std::find( begin, end, value ) != end )
            return true;
    }

    return false;
}

template < class T >
bool contains_duplicates( const std::initializer_list< T >& values )
{
    return contains_duplicates( values.begin(), values.end() );
}

int main()
{
    assert( !contains_duplicates( std::initializer_list< int >{} ) );
    assert( !contains_duplicates( { 2 } ) );
    assert( !contains_duplicates( { 2, 3, 1 } ) );
    assert( contains_duplicates( { 2, 2, 0 } ) );
    assert( contains_duplicates( { 2, 0, 2 } ) );

    const int i1 = 1, i2 = 2, i3 = 3, i4 = 4, i5 = 5, i6 = 6, i7 = 7;

    assert( !contains_duplicates( { i1, i2, i3, i4, i5, i6, i7 } ) );
}

Der Algorithmus hat eine Komplexität von O(n^2). Wenn es sehr viel mehr 
Elemente sind, als 10 dann könnte man die Elemente auch vorher sortieren 
(O(log n) und dann einmal durch gehen und die Nachbarn betrachten 
(n*O(log n))

mfg Torsten

[g457 (Gast)]

Warum so C-Style wenns hier ausdrücklich um C++ geht? Wie wärs mit 
std::sort+std::unique, oder std::set, oder std::map (mißbräuchliche 
Nutzung), jeweils zusammen mit size()?

HTH

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Torsten R. schrieb:
>     if ( begin == end )
>         return false;


Das ist überflüssig, da es schon der Schleifenbedingung weiter unten 
entspricht.

[apr (Gast)]

Torsten R. schrieb:
> als 10 dann könnte man die Elemente auch vorher sortieren
> (O(log n) und

In O(log n) sortieren? Not bad!

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

apr schrieb:
> Torsten R. schrieb:
>> als 10 dann könnte man die Elemente auch vorher sortieren
>> (O(log n) und
>
> In O(log n) sortieren? Not bad!

Oder so ähnlich ;-) Auf jeden Fall deutlich besser als n^2. Danke für 
den Hinweis.

[Sven B. (scummos)]

std::unordered_set items = {1, 2, 3, 4, 3, 4, 6}?

[B. S. (bestucki)]

g457 schrieb:
> std::sort+std::unique

Für std::unique muss der Container nicht sortiert sein. Eine Möglichkeit 
wäre auch noch std::sort + std::adjacent_find.

Ohne zu wissen, wie und wo die Variablen gespeichert sind, schlage ich 
vor, die Variablen in ein std::set zu packen und nach jeden Einfügen zu 
prüfen, ob der Wert eingefügt wurde oder nicht (via Rückgabewert von 
std::set::insert). Wurde er nicht eingefügt, ist er bereits vorhanden.

[g457 (Gast)]

>> std::sort+std::unique
>
> Für std::unique muss der Container nicht sortiert sein.

Da behauptet die Doku [0] was anderes, zumindest für die hiesigen 
Zwecke:

Removes all consecutive duplicate elements from the range [..]
            ^^^^^^^^^^^

Nix für ungut.

[0] http://en.cppreference.com/w/cpp/algorithm/unique

[B. S. (bestucki)]

g457 schrieb:
> Da behauptet die Doku [0] was anderes, zumindest für die hiesigen
> Zwecke:
> Removes all consecutive duplicate elements from the range [..]
>             ^^^^^^^^^^^

Oh, das Wort hab ich überlesen. Danke für die Korrektur.

g457 schrieb:
> Nix für ungut.

Kein Problem.

[Sven B. (scummos)]

g457 schrieb:
>>> std::sort+std::unique
>>
>> Für std::unique muss der Container nicht sortiert sein.

Du denkst die Standardbibliothek macht, was du erwartest? Haha, guter 
Witz :D

[Tom (Gast)]

Wenn std::minmax_element nicht völlig blöd gebaut ist, sollte das O(n) 
sein. Geht natürlich nur bei mit < vergleichbaren Datentypen.

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> A{1,1,2,1,1};
    std::vector<int> B{1,1,1,1,1};

    auto mima = std::minmax_element(A.begin(), A.end());
    bool all_equal = (*mima.first == *mima.second);

    auto mima2 = std::minmax_element(B.begin(), B.end());
    bool all_equal2 = (*mima2.first == *mima2.second);

    
    std::cout << "A: " << all_equal << "\tB: " << all_equal2 << "\n";


}

[Tom (Gast)]

Argh, es sollen alle ungleich sein. Problem nicht verstanden, setzen, 
5-.

[Arc N. (arc)]

Hashtabelle: Einfügen, Suchen: O(1) (amortisiert)
Solange einfügen bis ein Element doppelt vorkommt.
Laufzeit O(n), Worstcase O(n²) in Abhängigkeit vom Wertebereich der 
Integer, der Anzahl der Werte und der Implementation.
Ob das bei nur 10 Integern schneller ist, ist allerdings nicht sicher...

[Andreas S. (Firma: Schweigstill IT) (schweigstill)]

Mir fiele noch ein rekursiver Ansatz ein, d.h. eine Funktion, die das 
erste Element einer Liste gegen den Rest der Liste vergleicht und sich 
dann selbst mit dem Rest der Liste aufruft. Effizienz ist aber etwas 
anderes.

[Fabian D. (fabian_d)]

std::sort in Kombination mit std::adjacent_find wäre auch noch möglich.

std::vector<int> v{0, 1, 2, 3, 40, 40, 41, 41, 5};
auto it = std::adjacent_find(v.begin(), v.end());
if (it == v.end())
    // no equal elements found

[Heinz L. (ducttape)]

Wenn die Liste sortiert ist braucht Du logischerweise einfach nur gucken 
ob hintereinanderliegende Elemente gleich sind.

Die Frage ist halt jetzt ob Du irgendeinen Mehrwert woanders erhältst 
wenn Du die Elemente sortierst, bzw ob es möglich ist sie vielleicht 
schon beim Anlegen sortiert anzulegen, und ob das für Dein Problem 
nützlich ist. Das weißt wohl nur Du selbst.