Storing QList QLinkedList Iterators for automatic deletion

[N3O]

Hi everyone,

I have a serious question about the usage of Iterators in Qt. I want to have a resource manager for some project and I thought the following data structure would be great:

Each resource should be in memory only once. Whenever a resource is requested, we just get a data pointer to this resource. The data pointer will automatically register itself to the resource, so that we can find out, how often it was used and also WHERE it was used. The "WHERE" is the main difference to only using shared or weak pointers. The great thing about this data structure is not only, that whenever the data itself becomes invalid, all data pointers become invalid (like with weak pointers), but also, that we can register a callback function to the data pointer that will be called on invalidation. So whenever the data itself is deleted it will go through its registered list of data pointers and call the registered callback function before the data pointer becomes invalid. By doing so, the program can directly react on the decision of the resource manager. Another thing is, that whenever a data pointer is deleted it has to unregister itself from the resource.

Now here comes the problem: In the resource itself I just want to use a light weight collector for the data pointer registration like a list or a linked list. Please note, that we never need to access a single element directly by ID, so a linked list fits much better than a vector in this scenario. The only thing we want to do is calling all the callbacks of the registered daa pointers, so just iterating over the list in the resource in O(n). On the other hand, if just a data pointer becomes invalid (deleted), we have to unregister it from the resource. Since the resource might be used thousands of times, we do not want go through the whole list and search for the current deleted data pointer. Instead, we could store an iterator to the corresponding element in the list directly in the data pointer, whenever a new data pointer is created. So when a data pointer is deleted, we can just erase the stored iterator from that list in O(1).

From the theory point of view, this should be no problem, because a linked list iterator should just point to an element and since it is linked, this element will not move in memory. The problem is now, that QList is internally implemented as some kind of std::deque, so storing an iterator to this data structure will cause problems, because if some element is deleted another iterator might point to some invalid memory sections. My question is now, if I am really right, when I say that an Iterator to a QLinkedList behaves completely different and remains stable, also if other elements from this linked list are removed.

I am sorry, that I could not create a smaller example, but at least I wrote it in one file for simplicity of testing. The code demonstrates the general idea. You can try the different data structures by changing the MyList define to QList (will crash because of instable iterators) or QLinkedList (will not crash because of stable iterators- if I am right and this is not only an unhappy coincidence).

I'm looking forward for your great answers.

Greetz,
N3O

[N3O]

Hi again,

I might post the essential problem in a short code snippet. Is the following code guaranteed to evaluate right for MyList = QLinkedList?

#include <QtCore/QList>
#include <QtCore/QLinkedList>
#include <QtCore/QString>
#include <QtCore/QDebug>
 
#define MyList QLinkedList
 
int main(int argc, char *argv[])
{
    MyList<QString> qList;
    qList.append("One");
    MyList<QString>::iterator qListElement1 = qList.end() - 1;
    qList.append("Two");
    MyList<QString>::iterator qListElement2 = qList.end() - 1;
    qList.append("Three");
    MyList<QString>::iterator qListElement3 = qList.end() - 1;
    qList.append("Four");
    MyList<QString>::iterator qListElement4 = qList.end() - 1;
 
    //This will crash for QList, but not for QLinkedList
    qList.erase(qListElement2);
 
    for(MyList<QString>::iterator i = qList.begin();
        i != qList.end();
        ++i)
    {
        qDebug() << *i;
    }
 
    return 0;
}

#include <QtCore/QList>
#include <QtCore/QLinkedList>
#include <QtCore/QString>
#include <QtCore/QDebug>

#define MyList QLinkedList

int main(int argc, char *argv[])
{
    MyList<QString> qList;
    qList.append("One");
    MyList<QString>::iterator qListElement1 = qList.end() - 1;
    qList.append("Two");
    MyList<QString>::iterator qListElement2 = qList.end() - 1;
    qList.append("Three");
    MyList<QString>::iterator qListElement3 = qList.end() - 1;
    qList.append("Four");
    MyList<QString>::iterator qListElement4 = qList.end() - 1;

    //This will crash for QList, but not for QLinkedList
    qList.erase(qListElement2);

    for(MyList<QString>::iterator i = qList.begin();
        i != qList.end();
        ++i)
    {
        qDebug() << *i;
    }

    return 0;
}

To copy to clipboard, switch view to plain text mode 

I assume that it does not work with QList, because it is somehow implemented like a kind of std::deque, which means it allocates a whole memory block. When deleting an element in such a data structure, other Iterators might point to some illegal position in memory. But: Can I be sure that this is not the case with a QLinkedList, because each element always remains at the same position in memory, no matter if new elements are inserted or some elements are deleted?

Greetz,
N3O