String: n'tes vorkommen eines Zeichens

Simon2

Hi,

hmmm, ich werde das nochmal im Std nachschlagen ...
Bzgl. "Prädikat-Kopie": Da könnte ich mich aber mit static retten.

Th schrieb:

Bei den find-Algorithmen ist schon garantiert, daß sie das erste Element finden ...

Die Forderung garantiert strenggenommen aber nicht, dass von Vorne und streng sukkzessive gesucht wird. Ich könnte das auch so implementieren, dass ich einfach das Prädikat für alle Elemente auswerte und dann von allen "Positiven" den mit dem niedrigsten Index liefern.....(würde mich zwar der Teufel reiten, würde aber die funktionale Anforderung erfüllen.

Gruß,

Simon2.

CStoll

LordJaxom schrieb:

CStoll schrieb:

Aber es ist nicht garantiert, daß sie die ganze Zeit mit der selben Kopie ihres Prädikats arbeiten - und wenn das irgendwo zwischendurch kopiert wird, bricht die ganze Zählung zusammen.

Der Status der Suche, sprich die Member des Prädikats würden dann doch mitkopiert? Müsste in diesem speziellen Fall nicht sogar der Compiler einen Fehler werfen, wenn das Prädikat kopiert werden soll (wegen den const Membern)?

Nein - der Copy-Ctor läuft ja auch mit const-Elementen.

Und in meinem Buch wurde das Problem an der remove() Funktion verdeutlicht:

It remove_if(It start,It end,Pr pred)
{
  it = find_if(start,end,pred);//kopiert das Prädikat -> geänderter Status wirkt sich nicht auf den weiteren Verlauf aus
  return remove_copy_if(it+1,end,pred,it);//arbeitet mit der Originalversion des Prädikats
}

LordJaxom

CStoll schrieb:

Nein - der Copy-Ctor läuft ja auch mit const-Elementen.

Hast recht. Aber nichts desto trotz werden die Stati doch durch eben diesen mitkopiert.

Und in meinem Buch wurde das Problem an der remove() Funktion verdeutlicht:

It remove(It start,It end,Pr pred)
{
  it = find_if(start,end,pred);//kopiert das Prädikat -> geänderter Status wirkt sich nicht auf den weiteren Verlauf aus
  return remove_copy(it+1,end,it);//arbeitet mit der Originalversion des Prädikats
}

Verstehe ich nicht. Wo wird in remove_copy die lokale Variable pred verwendet?

Falls Du remove_copy_if meintest, das verstehe ich schon, wüsste aber nicht wo das zum Problem führen könnte. Ich muss mir eben darüber im klaren sein dass pred (genauso wie die Iteratoren - siehe aktuelle erase-Diskussion) von der Funktion nicht by-reference übernommen und demzufolge nicht geändert werden.

CStoll

Ja, ich meinte remove_copy_if() - und das Problem ist, wenn dein Prädikat z.B. das x-te Element kennzeichnen soll, zählen beide verwendeten Funktionen wieder von vorne (und du löschst das x-te Element und das 2x-te Element. (der Status wird schon kopiert, entwickelt sich dann aber unabhängig weiter)

pumuckl

In der obigen Klassendefinition von Simon gibts doch garkeinen Copy-Ctor, also duerfte das einem schon um die Ohren fliegen wenns compiliert wird und das find_if() irgedwo das praedikat kopiert.

Dann nochwas zu Simons operator():
a) Ich hab mal irgendwo gelesen, dass man sich nicht drauf verlassen soll, dass die Auswertung eines &&-statements abgebrochen wird, wenn der erste Teil false ist. Sprich: kann es sein dass ++count auch dann ausgefuehrt wird, wenn item != searchItem?
b) fehlt im zweiten if-statement das return - so gibst du auch wenn du es schon das n-te mal gefunden hast false zurueck.

Allgemein meine ich mal was gelesen zu haben, dass die Praedikate fuer derartige Suchen moeglichst kontextfrei sein sollten.

Aber das Problem kann man denke ich anders loesen:

#include <algorithm>

template<class iterator>
iterator find_nth(iterator start, iterator end, const iterator::value_type& val, size_t n) 
{
  while (--n) start = std::find(start, end, val);
  return start;
}

LordJaxom

pumuckl schrieb:

In der obigen Klassendefinition von Simon gibts doch garkeinen Copy-Ctor, also duerfte das einem schon um die Ohren fliegen wenns compiliert wird und das find_if() irgedwo das praedikat kopiert.

Doch, gibt es. Habe ich auch zuerst gedacht, aber habe dabei an den Zuweisungsoperator gedacht (steht aber oben schon ).

pumuckl

dann bin ich blind. Ich seh nur den ctor(char const, size_t const). Und wenn einer angegeben ist entfallen doch die impliziten oder? klar, op= wuerde generiert, aber da der default-ctor auch nicht generiert wird kann auch auf dem wege nichts kopiert werden.

Th

Hallo pumuckl (hast du auch so rote Haare?),

zu a: doch, in C/C++ kann man sich darauf verlassen, daß die logischen Operatoren && und || vorabweisend sind.

zu b:
die Version von Simon sucht das nächste Zeichen hinter den n-gefundenen Zeichen, daher seine Variable 'foundLastTime'.

d.h. bei deinem Code müßte man noch die letzte Zeile ändern:

return start!=end? start+1 : end;

Und die while-Schleife sollte man auch noch auf "start != end" testen, falls weniger als n-Zeichen enthalten sind.

über was für abgefahrenes zeug redet ihr hier?
das hat mit dir frage des OP doch gar nichts mehr zu tun...

Simon2

pumuckl schrieb:

...
a) Ich hab mal irgendwo gelesen, dass man sich nicht drauf verlassen soll, dass die Auswertung eines &&-statements abgebrochen wird, wenn der erste Teil false ist. Sprich: kann es sein dass ++count auch dann ausgefuehrt wird, wenn item != searchItem?
b) fehlt im zweiten if-statement das return - so gibst du auch wenn du es schon das n-te mal gefunden hast false zurueck.
c)Allgemein meine ich mal was gelesen zu haben, dass die Praedikate fuer derartige Suchen moeglichst kontextfrei sein sollten....

a) und c) habe ich beide noch nirgends gelesen und gerade bei a) würde mich das sehr überraschen, allein schon, weil oftmals "die ||-Variante" als guter Stil gepriesen wird.

b) Es fehlt gerade NICHT das return ! Schließlich heisst das Prädikat firstAfter.... und macht genau das, was es soll (hab's getestet, bevor ich's hier reingestellt habe). Das ist natürlich kein Gegenargument gegen CStolls prinzipielle Argumente...

Gruß,

Simon2.

CStoll

pumuckl schrieb:

a) Ich hab mal irgendwo gelesen, dass man sich nicht drauf verlassen soll, dass die Auswertung eines &&-statements abgebrochen wird, wenn der erste Teil false ist. Sprich: kann es sein dass ++count auch dann ausgefuehrt wird, wenn item != searchItem?

Bei selbstdefinierten Operatoren gilt die Funktions-Semantik (alle Argumente werden ausgewertet, bevor der Operator aufgerufen wird) - bei den eingebauten logischen Operatoren greift die Kurzschlusssemantik (wenn der erste Ooperand von && false ist, wird der zweite gar nicht mehr ausgewertet). Aus dem Grund sollte man && und || auch nicht überladen

Allgemein meine ich mal was gelesen zu haben, dass die Praedikate fuer derartige Suchen moeglichst kontextfrei sein sollten.

Ja, das versuche ich auch schon zu erklären

pumuckl schrieb:

dann bin ich blind. Ich seh nur den ctor(char const, size_t const). Und wenn einer angegeben ist entfallen doch die impliziten oder? klar, op= wuerde generiert, aber da der default-ctor auch nicht generiert wird kann auch auf dem wege nichts kopiert werden.

Der Default-Ctor wird nicht generiert, wenn du einen eigenen Ctor hast - Copy-Ctor und operator= deklariert der Compiler auf jedem Fall (es kann nur passieren, daß er sie nicht definieren kann, weil irgendwas die klassische Kopier/Zuweisungssemantik verhindert). Und mit den const-Elementen lässt sich zwar ein Copy-Ctor anlegen, aber kein Zuweisungsoperator.

LordJaxom

pumuckl schrieb:

dann bin ich blind. Ich seh nur den ctor(char const, size_t const). Und wenn einer angegeben ist entfallen doch die impliziten oder? klar, op= wuerde generiert, aber da der default-ctor auch nicht generiert wird kann auch auf dem wege nichts kopiert werden.

Es entfällt nur der **Default-**Ctor, nicht alle impliziten Ctoren. Der Copy-Ctor enfällt nur, wenn Du einen beliebigen Copy-Ctor explizit definierst.

@CStoll:
Ja, danke, dann hab ich es doch nicht falsch verstanden. Das ist natürlich verständlich und sicherlich der Grund, weshalb die numerischen Algorithmen ihren Funktor als Rückgabewert haben.

Simon2

CStoll schrieb:

...

Allgemein meine ich mal was gelesen zu haben, dass die Praedikate fuer derartige Suchen moeglichst kontextfrei sein sollten.

Ja, das versuche ich auch schon zu erklären ;)...

ICH hatte das auch verstanden.

Auch wenn ich das mit der "Sequenzbeliebigkeit" nicht verifizieren kann, ist das "Kopierargument" schon das K.O.-Kriterium.
Wäre ich nicht drauf gekommen (obwohl doch offensichtlich das Prädikat schon in der Schnittstelle als Kopie entgegengenommen wird).

Hmmmmm - schade eigentlich, weil es IMHO das Prädikatkonzept (für den Anwender) reichlich einschränkt (und dem Implementierer dafür mehr Freiheiten gibt)....

Danke,

Simon2.

pumuckl

Th schrieb:

Hallo pumuckl (hast du auch so rote Haare?),

In letzter Zeit nicht, hatte ich aber lange Zeit (daher der Nick), kommt auch wieder

zu a: doch, in C/C++ kann man sich darauf verlassen, daß die logischen Operatoren && und || vorabweisend sind.

Okay, dann hab ich da wohl Mist gelesen oder es einfach falsch verstanden.

zu b:
die Version von Simon sucht das nächste Zeichen hinter den n-gefundenen Zeichen, daher seine Variable 'foundLastTime'.

d.h. bei deinem Code müßte man noch die letzte Zeile ändern:
return start!=end? start+1 : end;
Und die while-Schleife sollte man auch noch auf "start != end" testen, falls weniger als n-Zeichen enthalten sind.

Naja bei meiner Version hab ich mich an die Standard-finds angelehnt, die den iterator auf das erste gefundene Element (und nicht das dahinter) liefern. Hatte dann bei Simons praedikat selbiges angenommen und nicht weiter auf das "after" im Namen geachtet - mea culpa. Und den Test in der while-Schleife benoetigt man auch nicht unbedingt, da find(it, it, bla) ja wohldefiniert ist und einfach it liefert. Klar kann man wieder versuchen, (vorzeitig) zu optimieren, aber wenn man davon ausgeht, dass bei der Suche nach dem n-ten Element das Element meistens auch tatsaechlcih n-mal vorhanden ist, wird die zusaetliche Abfrage eher zum Performancefresser als -retter.

CStoll schrieb:

Der Default-Ctor wird nicht generiert, wenn du einen eigenen Ctor hast - Copy-Ctor und operator= deklariert der Compiler auf jedem Fall (es kann nur passieren, daß er sie nicht definieren kann, weil irgendwas die klassische Kopier/Zuweisungssemantik verhindert). Und mit den const-Elementen lässt sich zwar ein Copy-Ctor anlegen, aber kein Zuweisungsoperator.

Wieder ein Detail gelernt, danke!