Doppelte Sätze im vector

[bigpoint]

Ich habe einen Vector, in dem vector mit eine strucktur(int,int,int,CString)

In dem vector kommen doppelte Datensätze.

Wie kann ich überprüfen, ob in dem vector die ersten zwei int gleich sind??

[Klotzkopp]

Wie kann ich überprüfen, ob in dem vector die ersten zwei int gleich sind??

Meinst du, wie du überprüfen kannst, ob es zwei Elemente im Vektor gibt, bei denen die beiden ersten int-Member gleich sind?

Falls ja: Es interessiert dich also nicht, welche Elemente das sind, nur ob es doppelte gibt?

[bigpoint]

Sorry für die ungenaue Problem Beschreibung

Meinst du, wie du überprüfen kannst, ob es zwei Elemente im Vektor gibt, bei denen die beiden ersten int-Member gleich sind?

Falls ja: Es interessiert dich also nicht, welche Elemente das sind, nur ob es doppelte gibt?

ja

[Klotzkopp]

Ich sehe da drei Möglichkeiten:

1.

Duplikate für jeden Eintrag zählen (count_if mit passendem Vergleichsprädikat).

Vorteil: in-place, kann vorzeitig abgebrochen werden.

Nachteil: O(n²).

2.

Alle Elemente in ein Set mit passendem Ordnungsprädikat übertragen. Wenn die Anzahl der Elemente im Set kleiner ist als im Vector, gab es Duplikate.

Vorteil: O(n * log n)

Nachteil: Zusätzlicher Speicher für den Set

3.

Kopie des Vectors erstellen, sortieren (std::sort mit passendem Ordnungsprädikat), Duplikate suchen (std::unique mit demselben Ordnunsprädikat). Wenn unique end() zurückgibt, gab es keine Duplikate.

Vorteil: O(n * log n)

Nachteil: Noch mehr Speicher als für 2 erforderlich.

Wozu ich raten würde, hängt davon ab, wie oft das gebraucht wird, wie viele Objekte da so drin sind und wie teuer es ist, sie zu kopieren.

Möglicherweise wäre auch ein ganz anderer Ansatz sinnvoll. Dazu wäre es aber notwendig zu erfahren, wozu du das brauchst. Vielleicht kann man ja von vornherein sortieren oder Duplikate verhindern.

[bigpoint]

Hmm, ich gehe den vector in eine schleife durch, ich will aber in der schleife jedes mal überprüfen können ob es die zwei int doppelt vorhanden sind oder auch nicht.

Es wird nur einmal gebraucht, da es sich nicht um viele Datensätze (die in dem vector sind) handelt ist kopieren nicht so teuer, denke ich.

Wehre es sinnvoll sich in der schleife ein array einzulegen in dem die zwei int speichern und immer wieder den array auf doppelte ds überprüfen??

[Klotzkopp]

Hmm, ich gehe den vector in eine schleife durch, ich will aber in der schleife jedes mal überprüfen können ob es die zwei int doppelt vorhanden sind oder auch nicht.

Dann mach einfach ein count_if. Wenn das mehr als 1 liefert, gab's den Wert doppelt.

Das könnte so aussehen:

// Datenstruktur

struct Data

{

    int i1;

    int i2;

    int i3;

    CString s;

};


// Vergleichsprädikat

struct Pred

{

    Pred( const Data& d ) : m_d(d) {}

    bool operator()(const Data& d)

    {

        return d.i1 == m_d.i1 && d.i2 == m_d.i2;

    }

    const Data& m_d;

};


int main()

{

    vector<Data> v;


    // ...


    for( size_t i=0; i<v.size(); ++i )

    {

        if( count_if( v.begin(), v.end(), Pred(v[i]) ) != 1 )

        {

            // doppelt!

        }

    }

}[/code]

count_if ist in <algorithm> deklariert.

[bigpoint]

Ja das funktioniert auch suuper

Ich stehe auf dem schlauch

mein Problem ist noch,

Struck Data

 (

   i1=1;i2=2

   i1=1;i2=2

   i3=6;

   i3=7;

) 

[/PHP]

In der schleife soll ich einen string "i1=1;i2=2;i3 in (6,7)" bauen,

[Klotzkopp]

In der schleife soll ich einen string "i1=1;i2=2;i3 in (6,7)" bauen,

Sollte da nach dem Komma noch etwas kommen?

Ansonsten verstehe ich nicht, wo das Problem liegt. Weißt du nicht, wie man einen String zusammensetzt?

[bigpoint]

Sollte da nach dem Komma noch etwas kommen?

nein

Weißt du nicht, wie man einen String zusammensetzt?

bis jetzt dachte ich schon

die structur seht so aus:

Struck Data

 (

   i1=1; i2=2; i3=6

   i1=1; i2=2; i3=7   

)   

[/PHP]

spricht die schleife lauft zwei mal durch

[PHP]
CStrin s;
for(..)
{
if( count_if( v.begin(), v.end(), Pred(v[i]) ) != 1 )
{
s.Format("i1=%i;i2=%i;i3 in (%i)",..);
}
}

wenn ich es so aufbaue, habe ich natürlich in i3 nur 7, muss ich also mir i3 noch mal merken und noch mal eine schleife aufbauen :eek

[Guybrush Threepwood]

Das Problem ist das dich doch interessiert welche Elemente genau die doppelten sind und nicht nur ob etwas doppelt vorkommt oder nicht.

Evtl. wäre ein std::set besser als ein std::vector dafür geeignet, aber ich kenn mich da nicht so aus. Klotzkopp kann da sicher mehr zu sagen...

[Klotzkopp]

die structur seht so aus:

Struck Data

 (

   i1=1; i2=2; i3=6

   i1=1; i2=2; i3=7   

)   

[/PHP]
Gültiger Code ist das nicht, aber ich glaube, ich weiß, was du meinst 



wenn ich es so aufbaue, habe ich natürlich  in i3 nur 7, muss ich also mir  i3 noch mal merken und noch mal eine schleife aufbauen :eek
Ich habe doch vorher ausdrücklich gefragt, ob es reicht, wenn du weißt, [b]ob[/b] Duplikate drin sind. Jetzt ist klar, dass das nicht reicht. Du brauchst offensichtlich die i3-Werte der Duplikate.


Damit ist die count_if-Lösung nicht mehr sinnvoll, weil die eben nicht ohne weiteres liefern kann, wo die Duplikate liegen.


Dann würde ich doch zu einer map raten, die als Schlüssel eine Struktur mit den i1- und i2-Werten und als Wert einen vector der i3-Werte hat:


[code]// Datenstruktur

struct Data

{

    int i1;

    int i2;

    int i3;

    CString s;

};


// Schluessel für die map

struct DataKey

{

    DataKey( Data d ) : i1(d.i1), i2(d.i2 ) {}

    int i1;

    int i2;

    bool operator<( const DataKey& rhs ) const

    {

        return i1 != rhs.i1 ? i1 < rhs.i1 : i2 < rhs.i2;

    }

};



int main()

{

    typedef map<DataKey, vector<int> > map_type;

    map_type m;


    vector<Data> v;


    // ...


    for( size_t i=0; i<v.size(); ++i )

    {

        m[DataKey( v[i] )].push_back( v[i].i3 );

    }

    for( map_type::iterator i = m.begin(); i != m.end(); ++i)

    {

        if( i->second.size() > 1 )

        {

            ostringstream ss;

            ss << i->second.size() 

               << " Duplikate fuer i1= " 

               << i->first.i1

               << ", i2=" 

               << i->first.i2 

               << ": i3 in ( ";


            for( size_t j = 0; j < i->second.size(); ++j )

            {

                ss << i->second[j] << " ";

            }

            ss << ")";


            CString s = ss.str().c_str();

        }

    }

}[/code]

[bigpoint]

das funkt super, danke

wie wurde es in C# ausschauen ?

Was sollte ich statt map nehmen ?

[bigpoint]

wie wurde es in C# ausschauen ?

Was sollte ich statt map nehmen ?

habe es mit IDictionary gelöst