[C++] Spaß mit zyklischen Abhängigkeiten

Programmiersprachen, APIs, Bibliotheken, Open Source Engines, Debugging, Quellcode Fehler und alles was mit praktischer Programmierung zu tun hat.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

[C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

An manchen Tagen schlägt C++ mit Wucht.

Code: Alles auswählen

struct entry;

typedef std::map<const resource*, entry> resource_map;
typedef std::map<utf8_string, resource_map::iterator> string_map;

struct entry
{
   string_map::iterator itByName;
   string_map::iterator itByFile;

   [...]
};
Vielleicht (hoffentlich) bin ich auch einfach nur übermüdet, aber ich sehe keine Möglichkeit, den Quelltext in eine gültige Reihenfolge zu bringen.

Anmerkung: Ausgelagert aus dem Jammer-Thread, es ist eine Unart meinerseits, dort einfach alles ungeordnet versacken zu lassen.
Zuletzt geändert von CodingCat am 18.04.2012, 11:54, insgesamt 3-mal geändert.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
simbad
Establishment
Beiträge: 132
Registriert: 14.12.2011, 14:30

Jammer-Thread

Beitrag von simbad »

Das ist einfach mal geraten. Habe keinen Compiler zur Hand um das testen zu können.

Code: Alles auswählen

struct entry;

struct entry
{
    std::map<utf8_string, std::map<const resource*, entry>::iterator>::iterator itByName;
    std::map<utf8_string, std::map<const resource*, entry>::iterator>::iterator itByFile;

   [...]
};

typedef std::map<const resource*, entry> resource_map;
typedef std::map<utf8_string, resource_map::iterator> string_map;

Dann hast du fürs coding die typedefs. Ist halt nur ein wenig unübersichtlich. Aber wenns erstmal geht ist das eh egal.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: Jammer-Thread

Beitrag von CodingCat »

Naja, so umständlich musst du das nicht machen. Vereinfacht ist das:

Code: Alles auswählen

struct entry
{
   typedef std::map<const resource*, entry> resource_map;
   typedef std::map<utf8_string, resource_map::iterator> string_map;

   string_map::iterator itByName;
   string_map::iterator itByFile;

   [...]
};

typedef entry::resource_map resource_map;
typedef entry::string_map string_map;
Leider ist das auch nicht gültiger, weil entry innerhalb der struct-Definition noch immer ein unvollständiger Typ ist, erst innerhalb von Methodendefinitionen o.ä. gilt entry als vollständig. Das muss so sein, weil sonst offensichtlich unsinnige Dinge wie struct entry { entry next; }; gültig wären.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: Jammer-Thread

Beitrag von dot »

Wäre es nicht vielleicht sinnvoller, die Ressourcen nicht direkt in einer der beiden maps abzulegen, sondern in einem eigenen Container und in den Maps dann nur Pointer oder Indices zu speichern?
Wieso genau müssen die resource_map und die string_map auf diese merkwürdige Art voneinander abhängig sein?
So wie ich das sehe, willst du eben einfach nur verschiedene Wege bieten, deine Ressourcen zu identifizieren!? Imo sollte das aber völlig unabhängig davon sein, wo und wie diese Ressourcen genau gemenaged werden. Und verschiedene mappings sollten selbst auch unabhängig voneinander sein.

Btw: Vermutlich wär es eine gute Idee, hier std::unordered_map statt std::map zu verwenden.
Zuletzt geändert von dot am 18.04.2012, 10:56, insgesamt 1-mal geändert.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: Jammer-Thread

Beitrag von CodingCat »

Ja, mit Zeigern oder Indizes wäre das alles kein Problem. Dummerweise akzeptiert aber kein STL-Container Zeiger an Stelle von Iteratoren. Ich brauche hier wirklich Iteratoren, um alle Indizes aktuell halten zu können, ohne jedes Mal den Affentanz von drei Map-Lookups aufführen zu müssen. :cry:

Map verwende ich wegen des geringeren Speicherverbrauchs.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: Jammer-Thread

Beitrag von dot »

Ich hinterfrage nicht die Tatsache, dass du hier iteratoren benutzt, sondern die generelle Struktur des ganzen. Warum zwei derart voneinander abhängige maps? Zumindest so wie ich das Problem verstehe, sollten die zwei Maps imo völlig unabhängig voneinander sein.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: Jammer-Thread

Beitrag von CodingCat »

Damit ich von einem Map-Eintrag zu allen anderen Map-Einträgen komme? Wenn sich Name und/oder Datei ändern, muss ich die String-Maps synchron halten. (Davon abgesehen speichere ich Name und Datei ungern zweimal, und da die Abbildung nicht bijektiv ist, müssen beide in den Schlüsseln gespeichert werden.)

Zur Klarstellung: Die Ressourcen selbst werden natürlich in keiner der Maps gespeichert, es handelt sich nur um eine Cache-Verwaltungsstruktur für Ressourcenteilung nach Name/Datei.

Randnotiz: Visual C++ sieht natürlich mal wieder absolut keine Probleme in diskutiertem Code, weil die Template-Instantiierung eh erst ganz am Ende durchgeführt wird.

Nachtrag: Meine aktuelle Variante ist übrigens:

Code: Alles auswählen

struct entry;

typedef std::map<utf8_string, entry*> string_map;

struct entry
{
   string_map::iterator itByName;
   string_map::iterator itByFile;

   [...]
};

typedef std::map<const resource*, entry> resource_map;
Aber auch hier habe ich das Problem, dass ich nicht an die resource_map-Iteratoren komme, wenn ich nach Name/Datei suche. Breche ich den Kreis in die andere Richtung, kann ich wiederum Namen und Dateien nicht aktuell halten.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
BeRsErKeR
Establishment
Beiträge: 689
Registriert: 27.04.2002, 22:01

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von BeRsErKeR »

Und wozu 2 maps? Kannst du nicht einfach eine nutzen und als Key ein std::pair<utf8_string, const resource*> nehmen? Oder von mir aus ein struct mit beiden Dingen und entsprechenden überladenen Vergleichs-Operatoren. Du handelst dir meiner Meinung nach hier unnötig Redundanz ein und vorallem deine zyklischen Abhängigkeiten.

Ich würde einfach ein typedef std::map<std::pair<utf8_string, const resource *>, entry *> entry_map; nutzen.
Ohne Input kein Output.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

Meine Probleme resultieren doch gerade aus der Vermeidung von Redundanz. Deinen Vorschlag verstehe ich nicht, mit einem kombinierten Schlüssel kann ich dann weder nach Name noch nach Ressource suchen, was dem Ganzen irgendwie den Sinn nimmt?

Falls das noch nicht klar geworden ist, es geht um einen Multi-Index-Container, d.h. am Ende existieren drei Maps:

Code: Alles auswählen

resource_map entries; // Cache-Informationen nach Ressourcen
string_map entriesByName; // Cache-Informationen nach Name
string_map entriesByFile; // Cache-Informationen nach Datei
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von dot »

Wieso kannst du nicht einfach sowas machen:

Code: Alles auswählen

std::unordered_map<utf8_string, resource*> resourcesByName;
std::unordered_map<utf8_string, resource*> resourcesByFile;
joggel

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von joggel »

Also... ich bin mir nicht sicher ob ich alles verstanden habe und auch nicht, ob der evtl. Ansatz deinen Anwendungsfall genüge tut.

Du hast eine Menge von Resourcen. Die einzelnen Elemente werden entweder durch Namen entriesByName und/oder durch Dateie(-namen) referenziert entriesByFile?

Wenn ja, dann könntest du doch soetwas wie eine Helper-Classe einführen.
Diese Helferklasse kapselt dann 2 std::maps.

Eine für das referenzieren über den Namen: std::map<sName,const resource*>
Eine für das referenzieren über die Datei(-namen): std::map<sFile,const resource*>

sName und sFile wären dann struct's (oder Class's).

struct sName
{
utf8_string m_Name;
}

und
struct sFile
{
utf8_string m_File;
}


Du könntest dann die Helferklasse zum Beispiel so verwenden:

Code: Alles auswählen

mHelper.addKeyValue( const sName& name, const resource* res)
oder

Code: Alles auswählen

mHelper.addKeyValue(const sFile& file, const resource* res)
Du müsstest nur dann, solltest du irgend etwas an den Einträgen ändern, die Helper-Klasse informieren und ggf. die 2 maps aktualisieren.

Aber wie gesagt:
Bin mir nicht sicher ob ich dein Problem 100%ig verstanden habe. Oder ob der Aufwand zu groß wäre :)
und ob ich überhaupt bis zum Ende gedacht habe ^^
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

Der hier diskutierte Code stammt aus genau einer solchen Helferklasse. ;)

Die direkte Abbildung von Namen und/oder Dateien auf Ressourcen-Zeiger in euren beiden Posts impliziert leider einen zweiten Lookup mit Ressourcen-Zeiger, um auch an die Cache-Information (Abbildung Ressourcen-Zeiger → Zusatzinformation) zur jeweiligen Ressource zu kommen. Biegt man das jetzt so um, dass man direkt den Zeiger auf die Cache-Information anstatt des Ressourcen-Zeigers mit Namen/Dateien assoziiert, sind wir wieder bei der aktuellen Lösung, der jedoch die direkte Abbildung Name/Datei → Iterator zu Cache-Information fehlt. Es ist ja nicht so, dass ein zweiter Lookup dermaßen schmerzhaft wäre. Es ärgert mich nur tierisch, weil es prinzipiell überhaupt kein Problem ist, wäre da nicht dieses blödsinnige Beschränkung aufgrund von unvollständigen Typen.

Auch wenn ich den Iterator zu den Cache-Informationen so selten brauche, dass ein zweiter Lookup in diesen Fällen absolut irrelevant wäre, heißt das, dass ich in meiner öffentlichen Schnittstelle entweder absolut inkonsistenten und redundanten Zugriff, mal mittels Iterator, mal mittels Schlüssel, anbieten, oder aber intern mit viel Aufwand und zusätzlichen Zeigern eigene Iteratorklassen zusammenschustern muss. Die zyklische Lösung ist dagegen außen wie innen elegant, einfach und konsistent. :evil:
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

Nachtrag: Natürlich mag dieses ganze Konstrukt zunächst etwas überdimensioniert erscheinen, wenn man nur die einfache Assoziation von Namen und Dateien mit Ressourcen im Kopf hat. Schlussendlich geht es hier aber vor allem um den Erhalt von Invarianten: Die Eindeutigkeit von Namen, die Eindeutigkeit von Dateinamen, die Umbenennung und Umspeicherung von Ressourcen in andere Dateien, ohne den Verlust von namens- und dateiunabhängigen logischen Ressourcenzuordnungen. Dieser Index ist in jeder Hinsicht multidirektional. Was beim Laden unter einem Namen oder einer Datei gefunden wurde, muss am Ende beim Speichern möglicherweise mit völlig neuem Namen oder neuer Datei referenziert werden (auch Wechsel von Name zu Datei oder umgekehrt sind dabei denkbar).

Ohne die vielzähligen Zustandsübergangsmöglichkeiten und Invarianten im Editor-Kontext wäre das alles in der Tat trivial und vor allem aufteilbar.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
BeRsErKeR
Establishment
Beiträge: 689
Registriert: 27.04.2002, 22:01

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von BeRsErKeR »

Also so richtig verstehe ich nicht was du vor hast. Wozu muss denn das Entry selbst überhaupt einen Iterator kennen? Das erscheint mir recht unlogisch, weil der Iterator mit dem Entry nichts zu tun hat. Der Iterator verweist zwar auf ein Entry aber deshalb muss das Entry den Iterator nicht kennen.

Mach halt deine 3 maps:

Code: Alles auswählen

typedef std::map<const resource *, entry *> resource_map;
typedef std::map<utf8_string, entry *> string_map;

resource_map entries; // Cache-Informationen nach Ressourcen
string_map entriesByName; // Cache-Informationen nach Name
string_map entriesByFile; // Cache-Informationen nach Datei
Aber lass den Iterator-Kram in der Entry-Klasse weg. Wozu brauchst du das überhaupt?
Ohne Input kein Output.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

Wie oben beschrieben, ohne Iteratoren habe ich keine Möglichkeit, ohne zusätzliche Lookups die entsprechenden Elemente in den STL-Containers zu identifizieren und zu manipulieren. Wozu steht einen Post über deinem, möglicherweise hast du den vor dem Verfassen noch nicht sehen können.
Zuletzt geändert von CodingCat am 18.04.2012, 14:31, insgesamt 1-mal geändert.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
Schrompf
Moderator
Beiträge: 4884
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von Schrompf »

BeRsErKeR hat geschrieben:Aber lass den Iterator-Kram in der Entry-Klasse weg. Wozu brauchst du das überhaupt?
Hat er doch schon geschrieben - um mehrfache Lookups zu vermeiden, wenn die Resource geändert werden soll.

Ich würde dafür wohl einen Boost Multi Index Container nutzen. Aber ich habe keine Ahnung, wie der intern implementiert ist.

[edit] Ninja! Hier geht's ab.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

Ja, darüber habe ich auch schon nachgedacht. Aber eigentlich war ich gerade so erfolgreich dabei, boost endlich rauszudrängen. Prinzipiell hätte ich es ja jetzt schon in eleganter Form zusammen, wenn mir die Bibliothek/Sprache nicht so in die Quere käme. :mrgreen:
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 13:27

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von eXile »

Habe ich gerade Tomaten auf den Augen, oder kann man das einfach so lösen? (Einfach immer den second-Typ kapseln.)

Code: Alles auswählen

#include <iostream>
#include <map>

struct resource {};
struct utf8_string {};

struct entry;
struct resource_map_iterator;

typedef std::map<const resource*, entry> resource_map;
typedef std::map<utf8_string, resource_map_iterator> string_map;

struct entry
{
    string_map::iterator itByName;
    string_map::iterator itByFile;
    
    // [...]
};

struct resource_map_iterator
{
    resource_map::iterator it;
};

int main(int argc, char* argv[])
{
    resource_map rmap;
    string_map smap;
    
    std::cout << "compiled fine." << std::endl;
}
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

Leider nein, weil resource_map_iterator zum Zeitpunkt von string_map::iterator itByName; incomplete ist, und damit die Instantiierung von string_map laut Standard zu undefiniertem Verhalten führt.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
BeRsErKeR
Establishment
Beiträge: 689
Registriert: 27.04.2002, 22:01

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von BeRsErKeR »

Wäre eine Iteration über eine Liste denn zu aufwendig?

Also etwa so:

Code: Alles auswählen

class entry;
typedef std::list<entry *> entry_list;
entry_list my_entries;

class entry
{
    public:
        static entry * entry_by_name(utf8_string name)
        {
            for (entry_list::const_iterator iter = my_entries.begin(); iter != my_entries.end(); ++iter)
            {
                if (iter->Name == name)
                    return *iter;
            }

            return nullptr; // oder: throw something
        }

        // ...

    private:
        utf8_string Name;
        utf8_string File;
        const resource * Resource;
};
Ohne Input kein Output.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

Sorry, aber ich sehe nun wirklich keinen Zusammenhang zum Problem mehr. Schlussendlich habe ich mit deinem Code nicht mal Iteratoren, sondern immer noch Zeiger?!?

Dein Design ist übrigens höchst kurios, weshalb ich jetzt doch noch korrigierend abschweifen muss. Machen wir hier also einfach einen Design- und C++-Exkurs auf:

Es gibt wirklich keinen Grund dafür, Funktionalität für Listen von Einträgen in die Einträge selbst zu bauen. Dass diese Funktionalität dann auch noch auf äußere globale Variablen zurückgreift, war deinerseits zwar vermutlich nur unüberlegt, ist aber selbst für Pseudocode bedenklich. Wo deine entries am Ende liegen sollen, ist mir auch nicht klar, dann doch eher eine Liste von entry-Objekten an Stelle von Zeigern. Nebenbei bemerkt sind auch Listen von unvollständigen Typen undefiniert, d.h. eine Liste von Einträgen darfst du frühestens nach der Definition von entry definieren. Damit hättest du ohne Zeiger sogar in deinem unglücklichen Beispiel schon eine unlösbare zyklische Abhängigkeit geschaffen. ;-)

Der Vollständigkeit halber hier für dich und derzeitige wie zukünftige Mitleser noch eine korrigierte Version, auch wenn das alles nichts mehr mit dem Ausgangsproblem zu tun hat:

Code: Alles auswählen

struct entry
{
   utf8_string Name;
   utf8_string File;
   const resource * Resource;
};

typedef std::list<entry> entry_list;

// Nutzung der STL Algorithmen empfohlen
entry_list::iterator entry_by_name(entry_list &list, const utf8_string& name) // Referenz statt by Value
{
   return std::find_if( list.begin(), list.end(), [&name](const entry &left) { return (left.Name == name); } );
}

// Ohne STL Algorithmen
entry_list::iterator entry_by_name(entry_list &list, const utf8_string& name) // Referenz statt by Value
{
   entry_list::iterator iter = list.begin(); // Return Value Optimization mitnehmen

   while (iter != list.end() && iter->Name != name)
      ++iter;

   return iter;
}
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 13:27

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von eXile »

CodingCat hat geschrieben:Leider nein, weil resource_map_iterator zum Zeitpunkt von string_map::iterator itByName; incomplete ist, und damit die Instantiierung von string_map laut Standard zu undefiniertem Verhalten führt.
Dann eben als shared_ptr, welche ich mit unvollständigen Typen deklarieren instantiieren darf?

Code: Alles auswählen

#include <iostream>
#include <map>

struct resource {};
struct utf8_string{};

struct entry;
struct resource_map_iterator;

typedef std::map<const resource*, entry> resource_map;
typedef std::map<utf8_string, resource_map_iterator> string_map;

struct entry
{
    std::shared_ptr<string_map::iterator> itByName;
    std::shared_ptr<string_map::iterator> itByFile;
    
    // [...]
};

struct resource_map_iterator
{
    std::shared_ptr<resource_map::iterator> it;
};

int main(int argc, char* argv[])
{
    resource_map rmap;
    string_map smap;
    
    std::cout << "compiled fine." << std::endl;
}
Mmh, hab gerade gesehen, dass deine aktuelle Variante vermutlich sogar schöner ist. I'm not good with computers!
Zuletzt geändert von eXile am 18.04.2012, 16:15, insgesamt 1-mal geändert.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

Prinzipiell ja, wenn du sie nicht an genau den falschen Stellen eingefügt hättest. :P

Code: Alles auswählen

struct entry;
struct resource_map_iterator;

// resource_map_iterator unbekannt, Zeiger erforderlich
// shared_ptr wäre wirklich übertrieben ineffizient
typedef std::map< utf8_string, std::unique_ptr<resource_map_iterator> > string_map;

struct entry
{
	// Vollständig bekannt, kein Zeiger erforderlich
	string_map::iterator itByName;
	string_map::iterator itByFile;
	
	// [...]
};

typedef std::map<const resource*, entry> resource_map;

// Vollständig bekannt, kein Zeiger erforderlich
struct resource_map_iterator { resource_map::iterator it; };

// [...]
Aber die Indirektion über weitere Heap-Objekte ist auch nichts, womit ich mich in diesem Fall anfreunden kann.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 13:27

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von eXile »

Ich habe mal den Kram abstrahiert (ohne Beachtung der Reihenfolge):

Code: Alles auswählen

struct X {}; 
struct Y {};

typedef std::map<X, A> mapA;
typedef std::map<Y, B> mapB;

struct A { mapB::iterator it; };
struct B { mapA::iterator it; };
Mmmh, es stinkt, ja. So wie die unvollständige-Typen-Abhängigkeiten aussieht:
mapAAmapB::iteratormapBBmapA::iteratormapA
musst du die Kette wohl an irgendeiner Stelle unterbrechen.

So wie ich das sehe, bleiben nur diese Möglichkeiten:
  • map(A/B)::iterator durch einen Typ ersetzten, der vollständig bekannt ist, und zu map(A/B)::iterator konvertierbar?
  • Heap-Objekte in Kauf nehmen
  • Eigene std-Container basteln. TL;DR-Version warum die diese Restriktion in die std-Container gebaut haben:
    http://www.drdobbs.com/184403814 hat geschrieben:In the end, it all seemed too murky and too poorly understood; the standardization committee didn't think there was any choice except to say that STL containers aren't supposed to work with incomplete types. For good measure, we applied that prohibition to the rest of the standard library too.
  • Auf kompatible Compiler testen
Es tut mir leid, aber das ist alles, was ich mit meinem beschränkten C++-Horizont hier bieten kann.
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von dot »

Vielleicht hilft auch boost.bimap!?
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

@dot: Nein, eine Bimap wäre wohl zu wenig. boost.multiindex hat ein sehr umfassendes und für dieses Problem mehr als ausreichendes Interface, aber eigentlich hätte ich langfristig wie gesagt boost lieber draußen statt drin.

@eXile: Jap, zusammengefasst sieht es exakt so aus. Hätte ich den von dir verlinkten Artikel vor einigen Jahren nicht zufällig gelesen, wäre es mir vermutlich nicht mal aufgefallen; Visual C++ schluckt es ja. Eigene Container basteln kommt offensichtlich nicht in Frage. Die erste Option ist das, worum ich mich seit gestern Abend drücke, weil es auf jeden Fall extrem hässlich wird. :|
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

Das eigentlich Überraschende ist, dass VC++ wie GCC überhaupt keine Probleme mehr mit den Dingen haben, die in dem Artikel zu STL Containers und Incomplete Types damals (2002) angesprochen wurden. Selbst folgendes Beispiel direkt aus dem Artikel, welches darin als ganz offensichtlich unkompilierbar verkauft wurde, macht nicht die geringstem Probleme:

Code: Alles auswählen

#include <iostream>
#include <map>
 
struct state
{
        int value;
        typedef std::map<int, state> state_map;
        state_map next;
};
 
int main()
{
        state machine;
 
        machine.next[0].value = 5;
        machine.next[2].value = 10;
        state::state_map::iterator it = machine.next.find(2);
 
        std::cout << it->second.value;
 
        return 0;
}
Siehe: http://ideone.com/jSehs

Mir ist auch nicht ganz klar, welche Probleme der Autor des Artikels darin sah, die Container-Templates mit vorübergehend unvollständigen Typen zum Kompilieren zu bringen. Eigentlich sollten die naheliegenden Implementierungen alle auch damit klarkommen, sofern nicht Container-intern ungeschickt sofort alle internen Datenstrukturen mit zur Instantiierung gezwungen werden.

(Im Fall von map dürfte man zum Beispiel Container-intern in Deklarationen nicht auf typedefs aus std::pair zugreifen, aber das ist sehr einfach vermeidbar. Der Artikel tut hier so, als müsste std::pair auf alle Fälle immer sofort mit instantiiert werden.)


So drängt sich in diesem Fall tatsächlich mal der Verdacht auf, dass die Standard-Autoren damals einfach nur eine ungeschickte Referenzimplementierung hatten, unter der wir jetzt Jahrzehnte leiden dürfen :evil:
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von CodingCat »

Ich habe noch ein wenig recherchiert und bin auf einige Diskussionen gestoßen, in denen tatsächlich rauskam, dass die fehlerfreie Instantiierung von STL Container Templates mit Incomplete Types bei umsichtiger Implementierung problemlos realisierbar sein sollte, und einige gängige Implementierungen das längst tun (Dinkumware, libstdc++, libc++ (ab clang 3?)).

Allerdings bin ich im Zusammenhang mit clang auf ein weiteres Problem gestoßen: Offensichtlich prüft der neue clang-Compiler für die Standard Library übergebene Typen bereits auf Concept-Konformanz, was die Frage aufwirft, wie eigentlich Concepts mit Incomplete Types zusammenspielen werden, wenn sie denn dann innerhalb der nächsten zwei Dekaden in den Standard aufgenommen werden sollten.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
Aramis
Moderator
Beiträge: 1458
Registriert: 25.02.2009, 19:50
Echter Name: Alexander Gessler
Wohnort: 2016
Kontaktdaten:

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von Aramis »

der nächsten zwei Dekaden
Es ist mir unerklaerlich woher du deinen unerschuetterlichen Optimismus nur nimmst :-)
Benutzeravatar
BeRsErKeR
Establishment
Beiträge: 689
Registriert: 27.04.2002, 22:01

Re: [C++] Spaß mit zyklischen Abhängigkeiten

Beitrag von BeRsErKeR »

CodingCat hat geschrieben:Sorry, aber ich sehe nun wirklich keinen Zusammenhang zum Problem mehr. Schlussendlich habe ich mit deinem Code nicht mal Iteratoren, sondern immer noch Zeiger?!?
Prinzipiell ja nicht unbedingt schlimm, sofern du damit trotzdem zum Ziel gelangen würdest. Ich glaube aber dass ich einfach nicht verstanden habe was du eigentlich vorhast.
CodingCat hat geschrieben:Dein Design ist übrigens höchst kurios, weshalb ich jetzt doch noch korrigierend abschweifen muss. Machen wir hier also einfach einen Design- und C++-Exkurs auf:
Das ist nett, aber das ist nicht unbedingt "mein Design". Ich würde sowas so auch nicht umsetzen. Es war eher die Suche nach einer Lösung ohne Anspruch auf Schönheit und gutes Design.
CodingCat hat geschrieben:Es gibt wirklich keinen Grund dafür, Funktionalität für Listen von Einträgen in die Einträge selbst zu bauen.
Hm für mich sind Iteratoren auch "Funktionalität für Listen von Einträgen" und die würde ich halt auch nicht in Einträge bauen (wie ich bereits erwähnte). Aber genau diese Tatsache führte mich ja zu diesem Schritt.
CodingCat hat geschrieben:Dass diese Funktionalität dann auch noch auf äußere globale Variablen zurückgreift, war deinerseits zwar vermutlich nur unüberlegt, ist aber selbst für Pseudocode bedenklich. Wo deine entries am Ende liegen sollen, ist mir auch nicht klar, dann doch eher eine Liste von entry-Objekten an Stelle von Zeigern.
Du darfst dir gern noch eine Klasse "Liste" drumrum denken. Ich wollte keine Seiten schreiben, sondern nur etwas andeuten. ;) Es ist auch kein Pseudo-Code, sondern eher eine Idee wie man Abhängigkeiten los wird.
CodingCat hat geschrieben:Nebenbei bemerkt sind auch Listen von unvollständigen Typen undefiniert, d.h. eine Liste von Einträgen darfst du frühestens nach der Definition von entry definieren. Damit hättest du ohne Zeiger sogar in deinem unglücklichen Beispiel schon eine unlösbare zyklische Abhängigkeit geschaffen. ;-)
Genau deshalb habe ich ja eine Liste von Zeigern verwendet. Genauer gesagt wollte ich deine Anforderungen ohne Iterator und stattdessen über Zeiger realisieren, DAMIT die Abhängigkeiten verschwinden. Ob das nun in übermüdetem Zustand geklappt ist eine andere Geschichte. ;)
Ohne Input kein Output.
Antworten