Vecor Iterator

*lt*---*gt*

Hallo,

weis nicht wie ich innerhalb einer while Schleife über einen Vector, diesem Vector innerhalb dieser Schleife neue Elemente hinzufügen kann und den Vektor wieder neu sortieren kann s.u. Bitte um Verbesserungsvorschläge. Muss kein fertiger code sein, habe ja auch kein lauffähiges Bsp.

sort( events.begin(), events.end(), sortBOEvents);
...

while (!events.empty())
{
  //Vectorinhalt aufsteigend sortiert, brauche kleinstes Element
  currEv = events[0];

....

  //einige Prüfungen und wenn OK, neues event wird eingefügt
  events.push_back(intersP); <-------- hier Problem
  // events neu sortieren, das bekommt die while Schleife nicht mit   
  //oder Vektor gar nicht sortieren und Methode schreiben, die das kleinste Element liefert?
  // oder ??

  events.erase(events.begin()); //auch falsch, möchte das currEv löschen und nach Neusortierung muss das nicht mehr das 1. Element in Vektor sein
}

schon mal Danke!

SeppJ

Was möchtest du überhaupt erreichen? Klingt nämlich eher nach einem Fall für ein (multi-)set.

Auch kann ich dein Problem nicht nachvollziehen? Wieso sollte ein while(!events.empty()) nicht auf Änderungen an events reagieren oder damit sonstwelche Schwierigkeiten haben?

*lt*---*gt*

Ich möchte solange noch Elemente in dem Vektor sind, diesen durchlaufen. Initial ist der Vektor schon mit Werten gefüllt. Im Schleifendurchlauf kommen weitere Elemente hinzu. Diese sollen wieder sortiert werden.
Falls das unklar ausgedrückt ist: Der Algorithmus soll ein Bentley Ottmann Algo werden, hier der Pseudocode
X entspricht meinem Vektor events.

Initialize event queue x = all segment endpoints;
Sort x by increasing x and y;
Initialize sweep line SL to be empty;
Initialize output intersection list L to be empty;

While (x is nonempty) {
Let E = the next event from x;
If (E is a left endpoint) {
Let segE = E's segment;
Add segE to SL;
Let segA = the segment above segE in SL;
Let segB = the segment below segE in SL;
If (I = Intersect( segE with segA) exists)
Insert I into x;
If (I = Intersect( segE with segB) exists)
Insert I into x;
}
Else If (E is a right endpoint) {
Let segE = E's segment;
Let segA = the segment above segE in SL;
Let segB = the segment below segE in SL;
Remove segE from SL;
If (I = Intersect( segA with segB) exists)
If (I is not in x already) Insert I into x;
}
Else { // E is an intersection event
Add E to the output list L;
Let segE1 above segE2 be E's intersecting segments in SL;
Swap their positions so that segE2 is now above segE1;
Let segA = the segment above segE2 in SL;
Let segB = the segment below segE1 in SL;
If (I = Intersect(segE2 with segA) exists)
If (I is not in x already) Insert I into x;
If (I = Intersect(segE1 with segB) exists)
If (I is not in x already) Insert I into x;
}
remove E from x;
}
return L;

SeppJ

http://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm#Data_structures

Binäre Suchbäume und priority queues gibt es schon in der STL.

*lt*---*gt*

Danke, mal schaun wie weit ich komme..