Gleicher Datenbestand in zwei verschiedenen Anordnungen - Designproblem

audacia

Für ein Programm, das mit mathematischen Ausdrücken arbeitet, benötige ich einen die Formel repräsentierenden Datenbestand, der in zwei Reihenfolgen zugreifbar sein muß:
- einmal in der, in welcher er eingelesen wird
- einmal nach Priorität sortiert

Für diverse Operationen (Vereinfachung, Differenzierung etc.) ist es nötig, aus dem Datenbestand eine Sequenz von Objekten zu entfernen oder an einer bestimmten Stelle einzufügen. Das ist auch mein Problem - bisher hatte ich den Datenbestand in einem Vektor organisiert und zugleich eine Prioritäts-Indexliste (multimap) erstellt, die bei jedem Löschvorgang nach ungültigen Indices durchsucht wurde, wodurch Einfüge- und Löschoperationen natürlich viel zu langsam wurden. Nun wollte ich, um die Performance zu verbessern, den Datenbestand in einer verketteten Liste speichern und die Objekte sich selbst in die Prioritätenliste eintragen und aus dieser wieder entfernen lassen. Dabei stoße ich auf folgendes Problem:

struct termentry_t
    {
        unsigned data;
        std::multimap <int, std::list <termentry_t>::iterator>::iterator iter; // <-- Rekursion!
    ...
    };

Daß ein Datenelement selbst einen Iterator auf die Prioritätsliste, die wiederum Iteratoren auf Datenelemente als Werte hat, enthält, ist ein rekursiver Bezug und wird vom Compiler auch entsprechend bemängelt. Und da stehe ich auf dem Schlauch...

Hat jemand eine Idee, wie das zu lösen wäre?

camper

Das hat nichts mit Rekursion zu tun. Die Frage ist hier einzig, ob eine std::list (und auch der Standardallokator) mit einem unvollständigen Typen instantiiert werden kann. Es ist relativ leicht zu erklären, warum das bei einer Wald-und-Wiesen -Implementation von vector möglich und bei list nicht möglich ist. Allerdings bin ich mir einigermaßen sicher, dass es mit ein paar Tricks immer möglich sein sollte. Ich kann mich aber nicht erinnern, dieses Problem in der Literatur oder im Standard thematisiert gesehen zu haben. Mir fällt denn auch keine simple Lösung in deinem Falle ein. Möglicherweise bist du mit Mehrfachindizierung im Sinne von boosts multiindexcontainer gut beraten - aber vielleicht verstehe ich das Problem auch nicht richtig.

audacia

Mittlerweile ist mir selbst etwas eingefallen, nämlich, direkte Zeiger auf die Objekte statt Iteratoren (und zwecks Übersichtlichkeit Multisets statt Multimaps) zu verwenden. So kann ich zwar die Einträge aus der Prioritätsliste nicht entfernen, aber zumindest als ungültig markieren:

struct setentry_t;

    struct termentry_t
    {
        unsigned data;
        setentry_t* setentry;

        bool operator < (const termentry_t& rhs)
        { return (data < rhs.data); }
        termentry_t (setentry_t* se)
         : setentry (se)
        {}
        ~termentry_t (void);
    };

    typedef std::list <termentry_t> term_t;

    struct setentry_t
    {
        int priority;
        term_t::iterator termentry;
    };

    typedef std::multiset <setentry_t> set_t;

...

Expression::termentry_t::~termentry_t (void)
{ setentry->termentry = NULL; }