Proxy-Typ bei Iterator-Dereferenzierung

Hallo!
Danke euch, ich werde heute Abend mal damit herumspielen.

@Eisflamme: Ich habe hier ein Datenmodell mit "heterogenen Datentypen". Dafür habe ich mir einen "dynamischen" Vektor gebastelt, der alles unterstützt, wofür der Datentyp nicht von Belang ist, sodass Client-Code nicht überall Typ-Weichen einbauen muss, nur weil er ein bisschen Daten herumkopieren will etc..
Nun war ich zwecks Benutzerfreundlichkeit am überlegen, dass dieser Vektor und dessen Iteratoren eben auch Proxy-Objekte herausgeben können, um ein paar Algorithmen wie "copy" oder "sort" zu ermöglichen. Für copy beispielsweise muss ich im Moment den assign-Member benutzen, sodass Client-Code im Moment eben noch nicht ganz so wie normaler STL-Code aussieht, obwohl es in diesen Fällen eigentlich möglich wäre. Aber irgendwie ist es die Sache vielleicht nicht wert.

knivil

einen "dynamischen" Vektor gebastelt, der alles unterstützt

Schon mal ueber type erasure nachgedacht?

Also vielleicht habe ich mich da etwas falsch ausgedrückt. Der "dynamische" Vektor ist bloß ein äußerer Wrapper für irgendein impl, dass ihm dabei hilft, das umzusetzen, was er so umsetzt, das innere impl leitet dann alles an einen typisierten Container weiter. Ich habe jetzt keinen vector< variant > gebastelt. Und überall wo man eine Referenz auf den "dynamischen" Vektor hat, kann man auch an den echten, inneren kommen. Das ist ja schon halb Type-Erasure, oder nicht, außer dass mein Impl im Moment _immer_ einen vector benutzt, statt das auch noch zu templatisieren, aber was würde besser das Interface eines vectors umsetzen, als ein vector selber...
Aber ich sehe jetzt noch nicht so ganz, wie mir die Type-Erasure dabei helfen sollte, dass man sagen kann std::copy( mydynvec.begin() ... );. Die dynvec::iterator speichern im Moment einen Zeiger auf das impl und einen Index. Im Prinzip könnten sie bei Dereferenzierung ein Proxy vom impl erhalten, der sich um Zuweisung usw. für den entsprechenden Datentyp kümmert.
Wenn ich das aber gerade alles falsch sehe, dann freue ich mich auf die Richtigstellung, weil dann ist es vielleicht doch alles gar nicht so problematich

otze

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.

Shade Of Mine

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.

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

otze

nein. geh mal davon aus, dass dort ein

std::swap(*iter1,*iter2);

steht. have fun.

//edit nein, das Beispiel habe ich mir nicht spontan ausgedacht

//edit2 ausführliches Beispiel mit erklärung:

iterator iter1,iter2;
//initialisieren...

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.

kin compile fehler, aber viel Spaß beim ausführen.

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?