Markierung von Elementen eines Containers möglich?

redrew99

Gibt es eine Möglichkeit, Elemente eines Containers zu markieren, so daß man z.B. bei mehreren Schleifendurchläufen des Containers diese markierten Elemente überspringen kann?

SeppJ

Beschreibe das eigentliche Problem, nicht die Probleme die du bei der Lösung hast!

EOutOfResources

Du kannst den Bereich mit Iteratoren kennzeichnen und dann mit der Sequenz arbeiten.
Beispiel:

#include <vector>
#include <algorithm>
int main()
{
  typedef std::vector<int> ContainerType;
  ContainerType foo(25, 12345);
  ContainerType::iterator SeqStart, SeqEnd;
  SeqStart = foo.begin() + 3;
  SeqEnd = foo.begin() + 17;
  std::sort(SeqStart, SeqEnd);
}

redrew99

Es geht um eine Berechnung der Primzahlen nach dem Sieb des Eratosthenes.

Um diesen Algorithmus umzusetzen, müssen aus einer Liste von Zahlen die Nichtprimzahlen ausgesiebt werden.

Eine (effektive) Umsetzung des Siebs basiert darauf, daß die Siebung in mehreren Durchläufen erfolgt, wobei bereits erkannte Nichtprimzahlen (Prinzahlen) entweder gelöscht oder erkannt werden müssen.

Eine Löschung dauert zu lange, also kommt wohl nur eine Kennung in Betracht.

CStoll

Beim Sieb enthält der Container doch sowieso nur die "ist Primzahl"-Markierungen (über welche Zahl geredet wird, sagt der Container-Index), also kannst du einfach die gefundenen zusammengesetzten Zahlen auf Null setzen.

(btw, ob das Löschen schnell geht, hängt auch von der Datenstruktur ab ;))

volkard

redrew99 schrieb:

Es geht um eine Berechnung der Primzahlen nach dem Sieb des Eratosthenes.

Um diesen Algorithmus umzusetzen, müssen aus einer Liste von Zahlen die Nichtprimzahlen ausgesiebt werden.

Eine (effektive) Umsetzung des Siebs basiert darauf, daß die Siebung in mehreren Durchläufen erfolgt, wobei bereits erkannte Nichtprimzahlen (Prinzahlen) entweder gelöscht oder erkannt werden müssen.

Eine Löschung dauert zu lange, also kommt wohl nur eine Kennung in Betracht.

Hier nimmt man normalerweise ein Array of bool oder einen vector<bool> oder vector<char>, wobei zu Beginn vec[0] bis vec[obergrenze] auf false gesetzt sind, wobei vec[n]==false falsebedeutet "Die Zahl n ist eine Primzahl". Wegstreichen ist dann Setzen auf true. Lustigerweise werden gar nicht die Zahlen gespeichert, sondern nur als Arrayindex benutzt. Also ein Container, der nur die gesuchte Markierung kann und gar nichts anderes.

redrew99

Danke@all für die Tips soweit

CStoll schrieb:

(btw, ob das Löschen schnell geht, hängt auch von der Datenstruktur ab ;))

Ich hatte zuerst eine Liste genommen und alle Nichtprimzahlen gelöscht.
Funktioniert einwandfrei, aber viel zu langsam
s. auch http://www.c-plusplus.net/forum/286113

CStoll

redrew99 schrieb:

Ich hatte zuerst eine Liste genommen und alle Nichtprimzahlen gelöscht.
Funktioniert einwandfrei, aber viel zu langsam

Bei der Liste ist auch nicht das Löschen so langsam, sondern das elementweise durchiterieren auf der Suche nach den zu löschenden Elementen.