was ist die bessere Lösung

Hallo

Ich weiss, dass das ein blöder Titel ist, aber ich weiss nicht wie ich es besser formulieren soll.

Ich will auf einem Bildschirm Items platzieren und möchte nicht, dass diese sich überdecken. Da ich im Vollbildmodus 800x600 arbeite lasse ich zur Zeit die X- und Y Pos auswürfeln und setze dann die Items. Damit diese sich nicht überdecken könnte ich nun bei jedem neuen Item prüfen, ob es ein anderes überdeckt, oder ich könnte eine Liste mit möglichen Postionen anlegen und dann immer eine Position auswürfeln lassen. was haltet Ihr für besser, eleganter und vor allem schneller?

Zweite Frage:
Ich versuche gerade mit Listen von STL zu arbeiten. Wie kann ich zum Beispiel das 7. Element aus der Liste löschen. Zur Zeit mache ich dies so:

i = list.begin()
for(int j=0; j<7; j++)
    i++;

Das geht doch aber bestimmt auch einfacher oder muss ich immer bis zur gewünschten Zahl hochrechnen?

Danke
chrische

nimm vector. listen sind für sowas nicht geeignet.

moe szyslak

Warum implementierst du nicht in jedem Objekt eine methode die ueberprueft ob ein anderes Objekt es ueberdeckt, dann gehst du jedemal wenn du ein neues Objekt playiert den Vektor durch und wenn alles gut geht dann kannst du das objekt plazieren!

Hallo

.............. schrieb:

nimm vector. listen sind für sowas nicht geeignet.

Ich dachte, dass Listen genau dafür da sind. Ich will ja Elemente mitten der Liste löschen und dachte, dass ich genau dafür Listen nehmen soll.

moe szyslak schrieb:

Warum implementierst du nicht in jedem Objekt eine methode die ueberprueft ob ein anderes Objekt es ueberdeckt, dann gehst du jedemal wenn du ein neues Objekt playiert den Vektor durch und wenn alles gut geht dann kannst du das objekt plazieren!

Dann müsste ich ja bei jedem neuen Item alle anderen Item checken. Ich dachte, dass dies relativ viel Rechenleistung kostet.

chrische

camper

chrische5 schrieb:

moe szyslak schrieb:

Warum implementierst du nicht in jedem Objekt eine methode die ueberprueft ob ein anderes Objekt es ueberdeckt, dann gehst du jedemal wenn du ein neues Objekt playiert den Vektor durch und wenn alles gut geht dann kannst du das objekt plazieren!

Dann müsste ich ja bei jedem neuen Item alle anderen Item checken. Ich dachte, dass dies relativ viel Rechenleistung kostet.

chrische

im prinzip richtig, aber überdeckungsprobleme sind nicht trivial. man kann in mehrdimensionalen räumen objekte nicht nach ihrer lage sortieren - und damit fällt der ansatz, die kollektion (total) zu sortieren und dadurch die überprüfung zu vereinfachen, schonmal aus. ich kenne mich damit nun nicht aus, soweit ich weiss, teilt man den raum in subräume auf und reduziert das problem dadurch, dass man jeden subraum auf kollisionen untersucht. google hilft bestimmt weiter. auf jeden fall ist das ganze komplex und wenn es sich nur um eine handvoll von objekten handelt, ist eine simple O(N*N) lösung sicher vertretbar.

chrische5 schrieb:

Zweite Frage:
Ich versuche gerade mit Listen von STL zu arbeiten. Wie kann ich zum Beispiel das 7. Element aus der Liste löschen. Zur Zeit mache ich dies so:
i = list.begin()
for(int j=0; j<7; j++)
    i++;

benutze wenigstens ++i.
allerdings gibt es dafür auch einen algorithmus: std::advance

chrische5 schrieb:

Hallo

.............. schrieb:

nimm vector. listen sind für sowas nicht geeignet.

Ich dachte, dass Listen genau dafür da sind. Ich will ja Elemente mitten der Liste löschen und dachte, dass ich genau dafür Listen nehmen soll.

list ist hier auf jeden fall besser als vector oder deque - bei list must du zwar durch die ganze liste durchwandern, aber das eigentliche löschen hat konstante komplexität. bei vector erreicht man konstantes lookup aber das löschen ist linear - und es ist plausibel anzunehmen, dass löschen langsamer als iterieren ist. andererseits ist es nicht sinnvoll überhaupt mit indezes in listen zu arbeiten, wenn du indizes benutzt, kannst du genausogut mit iteratoren arbeiten, und das problem taucht gar nicht erst auf.

Hallo

Ich habe nicht alles kapiert, was du geschrieben hast:

camper schrieb:

chrische5 schrieb:
Zweite Frage:
Ich versuche gerade mit Listen von STL zu arbeiten. Wie kann ich zum Beispiel das 7. Element aus der Liste löschen. Zur Zeit mache ich dies so:
i = list.begin()
for(int j=0; j<7; j++)
    i++;
benutze wenigstens ++i.
allerdings gibt es dafür auch einen algorithmus: std::advance

Was ist denn schlecht an:

i++

camper schrieb:

.............. schrieb:

nimm vector. listen sind für sowas nicht geeignet.

Ich dachte, dass Listen genau dafür da sind. Ich will ja Elemente mitten der Liste löschen und dachte, dass ich genau dafür Listen nehmen soll.
list ist hier auf jeden fall besser als vector oder deque - bei list must du zwar durch die ganze liste durchwandern, aber das eigentliche löschen hat konstante komplexität. bei vector erreicht man konstantes lookup aber das löschen ist linear - und es ist plausibel anzunehmen, dass löschen langsamer als iterieren ist. andererseits ist es nicht sinnvoll überhaupt mit indezes in listen zu arbeiten, wenn du indizes benutzt, kannst du genausogut mit iteratoren arbeiten, und das problem taucht gar nicht erst auf.

[/quote]

Was willst du mir denn mit den letzen Sätzen sagen? Tut mir leid, aber ich kann dir leider nicht in allen Punkten folgen.

chrische

*hochschieb*

chrische

ZuK

chrische5 schrieb:

Was ist denn schlecht an:
i++

i++ : i wird incrementiert der rückgabe wert ist aber das originale i -> es muss zuerst eine kopie von i angefertigt werden ( die dann zurückgegeben wird ) und dann wird das originale i incrementiert.
++i : incrementiert erstmal i und gibt dir dann das incrementierte i zurück -> keine kopie notwendig.

camper schrieb:

andererseits ist es nicht sinnvoll überhaupt mit indezes in listen zu arbeiten, wenn du indizes benutzt, kannst du genausogut mit iteratoren arbeiten, und das problem taucht gar nicht erst auf.

Also Ich verstehe diesen satz so dass es bei listen keinen sinn macht dass du dir irgendwelche indizes ausserhalb der liste merkst. Um auf ein betimmtes element der liste zugreifen zu können solltest du das direkt über einen iterator machen.
Beispiel:

list<int> thelist;
   int i4(4);
   int i5(5);
   int i6(6);
   list<int>::iterator it5;

   thelist.push_back(i4);
   it5 = thelist.insert(thelist.end(), i5);   
   thelist.push_back(i6);

   thelist.erase(it5);

Kurt