How to properly implement a tree QAbstractModel with a huge number of nodes?

Question

I would like to implement a model with tree structure. I am using python, but I guess the same problem occurs in C++.

As I can read in the documentation and on some forum posts (e.g. https://www.qtcentre.org/threads/10735-deleting-internal-pointer-in-QModelIndex), QModelIndex has been designed to be fast, with copy-construction being basically only copying its fields. This means, there is absolutely no way of knowing when a given model index will be thrown away (in the sense no more views use it), even though the documentation ask the view not to store these model indexes...

In python, the problem is that it's not possible for pyside/pyqt to use ref count on whatever is passed as internalPointer : https://srinikom.github.io/pyside-bz-archive/618.html

In C++, The problem is it's not possible to use smart pointer nor knowing when to safely delete this internal pointer

Given that, I am wondering how would one implement a tree model with data loaded dynamically, and with potentially a huge amount of data (e.g. Even if it's not my current application, imagine some infinite model that would fetch a web page, and build a tree of all linked web page accessed from it...).

I imagine, the memory required just for storing traversal informations would grow to an amount I would call it "memory leak"... Plus you need a container to store all traversal info you create to delete them at the model destruction...

My first question : Is this assumption true (should I worry about the growth of traversal information) ?

Second question : If I have reasons to worry, how to properly deal with it ? (how to know when I can free these)

Answer 1

A basic structure may be (similar to the QFileSystemModel)

struct TreeItem
{
    ~TreeItem() {qDeleteAll(children);}

    TreeItem *parent;
    QVector<TreeItem*> children;  

    // your actual data
    QString url; // f.ex. the url of the link.
    ...
}

class MyTree
{
public:
    TreeItem root;
}

As internalPointer, you can store a pointer to the actual TreeItem.

Note that this pattern does not contain a memory leak, as everything is correctly destructed when MyTree is destructed. It is indeed the case that no memory is released until MyTree itself is destructed. By filling TreeItem::children on the fly (i.e. only when needed), this structure can represent an infinite tree.

If memory usage is a concern, you should keep the footprint of the data stored in TreeItem to a bare minimum, f.ex. only the url and not the content or other metadata of that page.

Another approach may be to store the tree structure in a (temporary) database and use the row index of the database as the internalPointer.

Note that you shouldn't exaggerate the impact of an infinite tree (as long as you only create the needed items), but this depends of course on your use case. A human will probably never open the tree to a depth further than 5 to 10 (and even if he does so, he will probably open only a single branch to this depth).