Proxy-Typ bei Iterator-Dereferenzierung

Sone

otze schrieb:

Sone schrieb:

Wenn alle Operationen, die die entsprechenden Algorithmen fordern, eingehalten werden, dann geht das wunderbar.

Ja, und das beinhaltet, dass der Referenztyp value_type& ist. Und ich kenne eine Standardbibliothek bei der kein Workaround hilft, da crasht sort einfach.

Ich verstehe gar nicht, was du meinst. value_type ist das Proxy, ganz einfach. Das habe ich auch im zweiten Teil meines Posts impliziert. Wenn du dann von iterator ableitest, wird das Typedef automatisch gesetzt.

Da man sich aber value_type frei aussuchen kann, ist das ganze nur theoretischer natur.

iterator::reference a=*iter1;//reference nicht value_type&
iterator::reference b=*iter2;
std::swap(a,b);//ruft std::swap(iterator::reference&, iterator::reference&) auf
//also werden a und b getauscht, aber nicht die Werte hinter a und b.

Hier würde man** iterator_swap **nutzen.

Ich sehe übrigens nicht, was das Problem ist. Natürlich werden die Werte getauscht. Das Proxy-Objekt ist der Werte-Typ, ganz einfach... wieso sollte da was crashen?

camper

otze schrieb:

Ja, und das beinhaltet, dass der Referenztyp value_type& ist. Und ich kenne eine Standardbibliothek bei der kein Workaround hilft, da crasht sort einfach.

Das wird nirgendwo (bei den Algorithmen oder Iteratoren) verlangt. Die Anforderung echter Referenzen existiert so nur für Container.
Die korrekte Verwendung von Proxies kann man sich auch leicht am Beispiel von vector<bool> anschauen:
reference ist der Proxy, value_type bleibt weiter der Typ, mit dem tatsächlich gearbeitet werden soll.

otze

@Sone

Nochmal, und ganz deutlich, weil du es nicht selbst raffst: DAS WAR DAS SORT IN EINER VÖLLIG STANDARDKONFORMEN IMPLEMENTATION DER STANDARDBIBLIOTHEK.

Es ist völlig egal, wie du es machen würdest, was man ansonsten verwenden würde und whatever. Und ja, ich kann auch iter_swap EXAKT GENAUSO implementieren. Es ist mir völlig egal, wie du das machst, solange ein Compiler deer da draussen überall im Produktiveinsatz ist, das anders macht.

Man hölle nochmal.

Du darfst dich nicht auf eine bestimmte Implementation verlassen, egal wie dumm unintuitiv oder whatever sie ist. std::swap darf sich auch nen Zeiger auf das Objekt ziehen und dann damit machen was es will.

@camper

http://www.boost.org/doc/libs/1_54_0/libs/iterator/doc/new-iter-concepts.html

Forward Iterator *i is T& (or const T& once issue 200 is resolved)

//edit siehe auch Tabelle 74 im C++03 Standard. C++11 ist mir Wumpe, wäre mir aber auch nicht bekannt, dass das geändert wurde.

Sone

DAS WAR DAS SORT IN EINER VÖLLIG STANDARDKONFORMEN IMPLEMENTATION DER STANDARDBIBLIOTHEK.

1. Woher soll ich wissen, dass das eine Sort-Implementierung war?
2. Es ist völlig egal von woher dieser Code kommt. Der Code selbst ist völlig egal. Um den geht es mir jetzt nicht.

Es ist mir völlig egal, wie du das machst, solange ein Compiler deer da draussen überall im Produktiveinsatz ist, das anders macht.

Wovon zum Teufel sprichst du gerade?

Mir ging es darum, dass der Iterator mit dem Proxy als value_type völlig normal funktioniert.

Soweit ich sehen kann, geht es gerade gar nicht um irgendwelche komischen Hacks, sondern einfach darum, dass statt dem eigentlichen Objekt der Iterator ein Proxy "hält". Und dieses preisgibt. Damit ist iterator_traits<Iterator>::value_type zwar nicht gleich dem Objekttyp, aber was solls.

Falls es gerade darum geht, eine Referenz vom entsprechenden Elementtyp mit einem Proxy zu initialisieren o.ä., lass es mich wissen.

Ich hab nur irgendwie immer im Hinterkopf, dass man irgendwie keinen Typ einfacherweise so bauen kann, dass er sich in allen Fällen genau wie ein anderer Typ verhält. Aber ich täusche mich wohl gerade.

Konvertierungsoperator?
(Zwar nicht alle Fälle, aber nah dran)

otze

@Sone "nein, das Beispiel habe ich mir nicht spontan ausgedacht ".

Sone schrieb:

Mir ging es darum, dass der Iterator mit dem Proxy als value_type völlig normal funktioniert.

Nein. Denn entweder ist std::swap nicht funktionsfähig, oder deine referenz hat kein Referenzsemantik. suchs dir aus.

//edit es ist nebenbei nicht nur der vc08 der dabei aussteigt. der gcc versucht ja mit std::vector<bool> klarzukommen und macht deswegen sowas im iter_swap wenn der referenztyp nicht nach value_typ& konvertierbar ist.

iterator::value_type tmp = *iter1;
*iter1 = *iter2;
*iter2 = tmp;

funktioniert bei eurer wahl des value_type also auch nicht.

(ja, ich bin schonmal durch diese Hölle gegangen. Nein, die ganzen billigen Tricks funktionieren nicht. Ja, das führt zu zufälligen Problemen auf fremden compilern. Nein man macht das nicht.)

Sone

Ok, ganz langsam:

oder deine referenz hat kein Referenzsemantik.

Ich nehme hier von vornherein an, dass die "Referenz" und iterator_traits::reference usw. den Typ Referenz auf Proxy haben.

Wieso sollte Referenz auf Proxy mit Proxys nicht funktionieren?

otze

implementier mal einen iterator, der das erfüllt. Dann renn aber damit sofort zu den boost::iterator leuten, die freuen sich sicherlich zu hören, dass ihr Proposal zur Änderung des Standards unnötig ist.

Und std::swap(*iter1,*iter2); muss funktioneiren. Das als Minimalanfordrung.

//edit Überlege dir auch, wie du das implementieren willst:

struct SonesUnmöglicherIterator{
    struct Proxy{...};
    typedef Proxy value_type;
    typedef Proxy& reference;

    reference operator*(){
        return Proxy(...);//lala
    }
};

Sone

Ich glaube, ich habe das Problem.

(Edit: Ich habe nicht aktualisiert, während ich das geschrieben habe!)
Du redest sicher gerade davon, dass man bei bestimmten Operationen (wie Dereferenzierung bei Iteratoren) keinen Objekttyp zurückgeben darf, sondern nur Referenztypen...

Und man kann natürlich nicht die Adresse eines prvalues nehmen, welches eine Funktion zurückgibt.

Edit: Verdammt, stimmt, davon hat Onkel Otze tatsächlich geredet! Aber ich habe es erraten müssen, wie kann das sein?

Sone

struct SonesUnmöglicherIterator
{

    struct Proxy{...}; 
    typedef Proxy value_type; 
    typedef Proxy& reference; 

    reference operator*()
    {
        static std::vector<Proxy> vec;
        vec.push_back( Proxy(...) );
        return vec.back();
    } 
};

Ist natürlich ein relativ krasser Overhead, aber was solls.

otze

for(std::size_t i = 0; i != std::numeric_limits<std::size_t>::max(); ++i){
    *iter;
}

ja, du hast es Begriffen. Ich bin eigentlich von vornherein davon ausgegangen, dass du genauw eißt, wo das Problem ist, und nur die Standardbiliothek übertölpeln wolltest. Und ich wollte dir nur ein paar Gegenbeispiele liefern, die mir so begegnet sind bevor ich random_shuffle neu geschrieben hab...für sort war ich bislang noch zu faul, aber solange kein bugreport rein kommt...

Sone

Ich bin eigentlich von vornherein davon ausgegangen, dass du genauw eißt, wo das Problem ist..

Nein, nein. Ich habe nur zu eng gedacht. Habe schließlich nicht die Erfahrung.

... und nur die Standardbiliothek übertölpeln wolltest.

Das versuche ich praktisch nie. Das ist nämlich sehr frickelig. Bei so etwas würde ich eigentlich sofort aussteigen und mein Design irgendwo weiter höher angucken.

Ein kleiner Scherz noch, analog zu deinem Code:

struct SonesUnmoeglicherIterator // oe
{
    struct Proxy{...}; 
    typedef Proxy value_type; 
    typedef Proxy& reference; 

    reference operator*()
    {
        static std::set<Proxy> set;
        return set.insert(Proxy(...)).first;
    } 
};

Was natürlich eine doofe Anforderung stellt und dazu einen unnötigen Overhead hat. Vielleicht kann man den value_type noch hashen, dann ginge unordered_set .

camper

otze schrieb:

//edit siehe auch Tabelle 74 im C++03 Standard. C++11 ist mir Wumpe, wäre mir aber auch nicht bekannt, dass das geändert wurde.

Ignoranz ist kein besonders überzeugendes Argument.
1. Ja, C++11 führt hier notwenige Korrekturen durch: das Ergbnis der Dereferenzierung muss für InputIteratoren in value_type konvertierbar sein, und für ForwardIteratoren gleich reference.
2. swap sollte niemals qualifiziert aufgerufen werden, insbesondere stellt das SwapableRequirement auf den unqualifizierten Aufruf von swap ab. Jeder Aufruf von swap aus der Standardbibliothek heraus erfolgt somit unqualifiziert. Und nat. hat jeder vernünftig programmierter Proxy seine eigene swap-Funktion mitzubringen, da der normale Dreieckstausch offenbar nicht funktionieren kann.

also

struct my_iterator
{
    typedef whatever value_type;
    struct proxy
    {
        ...
        proxy& operator=(value_type);
        operator value_type();
        ...
        friend void swap(proxy&,proxy&);
    };
    typedef proxy reference;
    usw...
    reference operator*() const;
};

iterator::value_type tmp = *iter1;
*iter1 = *iter2;
*iter2 = tmp;

funktioniert dann plötzlich auch wieder.

Sone

operator value_type();

Absichtlich keine Referenz? Wie will dann jemand vom Proxy aus den Referee ändern?

Edit: my_iterator muss ein InputIterator oder OutputIterator sein.

camper

Sone schrieb:

operator value_type();
Absichtlich keine Referenz? Wie will dann jemand vom Proxy aus den Referee ändern?

Edit: my_iterator muss ein InputIterator oder OutputIterator sein.

Indem die Zeile darüber genutzt wird?

Sone

camper schrieb:

Edit: my_iterator muss ein InputIterator oder OutputIterator sein.

Indem die Zeile darüber genutzt wird?

Ja, aber was wenn Funktionen aufgerufen werden? Also keine nackten Zuweisungen?

Oder ist das vom Standard her nicht garantiert, dass das funktionieren muss?

camper

Sone schrieb:

camper schrieb:

Edit: my_iterator muss ein InputIterator oder OutputIterator sein.

Indem die Zeile darüber genutzt wird?

Ja, aber was wenn Funktionen aufgerufen werden? Also keine nackten Zuweisungen?

Kein Standardalgorithmus würde das tun (ausser über mem-Funktionszeiger).

Sone

camper schrieb:

Kein Standardalgorithmus würde das tun (ausser über mem-Funktionszeiger).

Es geht nicht darum, ob das ein Standardalgorithmus tun würde oder nicht tun würde, sondern ob er es darf. Darf er?

otze

camper schrieb:

otze schrieb:

//edit siehe auch Tabelle 74 im C++03 Standard. C++11 ist mir Wumpe, wäre mir aber auch nicht bekannt, dass das geändert wurde.

Ignoranz ist kein besonders überzeugendes Argument.

Ignoranz der Realität auch nicht. Wieviele Softwarefirmen da draussen verwenden vc08? Ich sags dir: ziemlich viele. Wieviele Bibliotheken müssen c++03 noch unterstützen: ne ganze ecke mehr. Nur weil wir jetzt den magischen C++11 standard haben müssen wir nicht code propagieren, der in C++03 problemlos compiliert aber falsches Verhalten hat.

1. Ja, C++11 führt hier notwenige Korrekturen durch: das Ergbnis der Dereferenzierung muss für InputIteratoren in value_type konvertierbar sein, und für ForwardIteratoren gleich reference.

DAnn schauen wir uns doch mal an, als was reference in C++11 definiert ist.
Ich hab hier natürlich nicht den originalstandard rumligen sondern verwende den C++11 draft N3242. Wenn sich zwischen dem letzten draft und dem iso standard da noch was geändert hat: nur her damit. Da steht:

24.2.5
Forward iterators
[forward.iterators]
A class or a built-in type X satisfies the requirements of a forward iterator if
— X satisfies the requirements of an input iterator (24.2.3),
— X satisfies the DefaultConstructible requirements (17.6.3.1),
— if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T

Also ändert sich dort genau gar nichts.

2. swap sollte niemals qualifiziert aufgerufen werden

Die garantie dass das auch nicht passiert, haben wir aber erst seit C++11

Sone

Wenn sich zwischen dem letzten draft und dem iso standard da noch was geändert hat: nur her damit.

Du bist nicht besonders gut informiert, oder?
N3337

Die Anforderungen für Forward-Iteratoren sind

A class or pointer type X satisfies the requirements of a forward iterator if
— X satisfies the requirements of an input iterator (24.2.3),
— X satisfies the DefaultConstructible requirements (17.6.3.1),
— if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T,
— the expressions in Table 109 are valid and have the indicated semantics, and
— objects of type X offer the multi-pass guarantee, described below.

otze

das ist exakt identisch? Da steht nun genau entweder reference ist T& oder T const&.