[Erledigt] list::const_iterator crasht beim Vergleich

Konrad Rudolph

Hallo,

ich iteriere (in einer Methode einer Klasse) durch eine (Member-)Liste ('std::list') und führe dabei einen Vergleich von Iteratoren aus. Das klappt auch recht gut.

Nun brauche ich von der besagten Methode aber auch eine const-Version. Um nicht alles neuschreiben zu müssen, const-caste ich einfach 'this' und rufe die non-const-Version auf. Das ist sicher, da keine Schreiboperationen ausgeführt werden. Dachte ich. Leider crasht der Code bei dem Vergleich zweier Iteratoren; der Debugger sagt mit, die beiden Iteratoren seien inkompatibel. Und in der Tat scheinen die Iteratoren zu unterschiedlichen 'std::list'-Instanzen zu gehören (sie besitzen beide einen Zeiger auf ihren Container, der unterschiedlich ist).

Woran kann das liegen? Ich bin sicher, dass der Container *kein* anderer ist.

Hier mal der Code, wobei ich befürchte, dass er nicht viel bringt:

typename list_type::iterator skip_list_find(key_type const& key) {
    // 'm_nodes' ist definiert als list_type.
    typename list_type::iterator p = m_nodes.begin();

    if (empty())
        return p;

    int y = m_height;

    while (y > 0) {
        --y;
        while (
            // In der nächsten Zeile erfolgt der Crash:
            p->next[y] != m_nodes.end() and
            not m_comp(key, p->next[y]->value.first)
        )
            p = p->next[y];
    }

    return p;
}

typename list_type::const_iterator skip_list_find(key_type const& key) const {
    // This is well-defined because we will not use write access at any time.
    skip_list* mutable_this = const_cast<skip_list*>(this);
    return static_cast<list_type::const_iterator>(mutable_this->skip_list_find(key));
}

Die Definition von 'list_type' sieht folgendermaßen aus:

struct node;

typedef std::list<
    node, typename allocator_type::rebind<node>::other
> list_type;

struct node {
    value_type value;
    std::vector<typename list_type::iterator> next;
};

Ach ja, ich habe jetzt die Const-Version doch mal neugeschrieben (einfach den Code kopiert und 'iterator' durch 'const_iterator' ersetzt. Ändert nichts: gleicher Fehler).

camper

Kann an dem Code nichts finden, allerdings machst du ja ein paar Annahmen über den Inhalt, die verletzt sein könnten. Ein paar zusätzliche asserts wären möglicherweise hilfreich.
Ganz nebenbei:

typedef std::list<
    node, typename allocator_type::template rebind<node>::other
> list_type;

wenn, wie ich annehme, allocator_type von einem Templateargument abhängt.

Konrad Rudolph

camper schrieb:

Kann an dem Code nichts finden, allerdings machst du ja ein paar Annahmen über den Inhalt, die verletzt sein könnten. Ein paar zusätzliche asserts wären möglicherweise hilfreich.

Hmm, werde mal schauen. Allerdings sind die Annahmen über den Inhalt doch sehr begrenzt. Die einzige (theoretisch) verletzbare Annahme, die ich im Moment sehe, ist der Array-Index von 'next' und past-the-end 'p'.

Ganz nebenbei:
typedef std::list<
    node, typename allocator_type::template rebind<node>::other
> list_type;
wenn, wie ich annehme, allocator_type von einem Templateargument abhängt.

Ja, dachte ich mir schon. So hatte ich's ursprünglich auch, da der VC++ es aber auch ohne akzeptiert hat, habe ich's wieder rausgelassen. Tests mit dem GCC und Comeau (soweit möglich) folgen eh noch.

Konrad Rudolph

Okay, ich habe den Fehler gefunden.

Die konstante Instanz der Klasse, für welche diese Methode aufgerufen wird, ist die Kopie einer nicht-konstanten Instanz. Im Kopierkonstruktor wird selbstverständlich die 'm_nodes'-Liste kopiert. Die 'next'-Zeiger seiner Elemente hingegen habe ich nicht angepasst.

Ba, widerlich. Jetzt muss ich das auch noch manuell implementieren.