Trees, tree models and tree views in Qt

published at 30.07.2015 17:27 by Jens Weller
Save to Instapaper Pocket

On Tuesday I've announced this new series, this is the first installment showing the progress. The first thing I did when I started to work on my new application, was to implement a generic tree class, that then is exposed through not so generic tree model to Qt. The QTreeView then simply displays the data in the tree. My goals are, that the class containing the tree it self, is independent from Qt. Yet as its used in Qt, there are a few design decisions which reflect the needs of the Qt Model View system.

There is a very nice example in the Qt documentation which I did use for guidance in how to implement a tree model for Qt correctly. The simple tree model example implements only two classes, TreeItem for the tree, and TreeModel for plugging the tree later in a QTreeView. QTreeViews can have more then one column, where there first column always contains the tree. For my uses, the other columns are useless, so that is the first difference to the example from Qt.

Building a tree in C++

But for my TreeItem class, I have a different set of needs. It should be a template, and also have no dependency to Qt. I'd like to avoid raw pointers in my interface and have the actual tree data as a template parameter. The children of a node are stored in a std::vector, also each node needs to know its parent:

template< class NameVisitor, class TypeIdVisitor, class IdVisitor, class ...types>
class TreeItem : public std::enable_shared_from_this< TreeItem< NameVisitor, TypeIdVisitor, IdVisitor,types... > >
{
public:
    using variant = boost::variant< types...>;
private:
    using item_t = std::shared_ptr< TreeItem< NameVisitor, TypeIdVisitor, IdVisitor, types... > >;
    using self = TreeItem< NameVisitor, TypeIdVisitor, IdVisitor, types...>;
    using const_item_t = std::shared_ptr< const TreeItem< NameVisitor, TypeIdVisitor, IdVisitor, types... > >;
    using weak_item_t = std::weak_ptr< TreeItem< NameVisitor, TypeIdVisitor, IdVisitor, types...> >;
    variant node;
    std::vector< item_t > children;
    weak_item_t parent;
...

I opted for using std::shared_ptr for each TreeNode, as I need to expose raw pointers later to the TreeModel, which stores them in the QModelIndex class. There is the need to ensure, that all pointers to TreeItem instances stay valid through out the run time of the application. A vector<TreeItem> or recursive_variant would not be able to guarantee this, as when the vector grows, it will move its content around in memory, invalidating old pointers. As I also need to be able to get the shared_ptr of the current instance, this class derives from enable_shared_from_this.

The variadic template parameters are used to declare a boost::variant type with those parameters. I need three different visitors to access data of the types stored in the variant, which I simply added as template parameters. Currently only NameVisitor is needed, as its used to extract the name of each node for displaying in the TreeView.

Implementation details

The public interface of the tree class:

TreeItem(weak_item_t p = weak_item_t()):parent(p){}
TreeItem(weak_item_t p,variant value ):node(value),parent(p){}

int row()const
int childCount()const
item_t getParent()const{return parent.lock();}
item_t getChild(int row)const
size_t type_id()const
int id()const
std::string name()const
template<class T>
void emplace_back(T &&t)

The first constructor is mainly for constructing the root node of a tree, the second constructor is the one called by emplace_back. Some methods return int instead of size_t simply because Qt uses int for sizes (e.g. childCount). Some of the interface is returning the results of the visitors (id,name, type_id), but there are 3 interesting methods:

childPos is the only private method in this template, it is called inside of row:

int row()const
{
    if(parent.expired())
        return 0;
    return parent.lock()->childPos( self::shared_from_this());
}

So for root row returns 0, otherwise it will access the parent and call childPos:

int childPos(const const_item_t& item)const
{
    auto it = std::find(std::begin(children),std::end(children),item);
    if(it != children.end())
        return it - children.begin();
    return -1;
}

Then, childPos calls std::find to obtain the iterator of the child, and returns the position in the container by simply doing some iterator math. This only works of course, because vector has random access iterators. In case its not found, the method returns -1, which is required by Qt. Leaves emplace_back:

template<class T>
void emplace_back(T &&t)
{
    children.emplace_back(std::make_shared< self >(self::shared_from_this(),std::forward<T>(t)));
}

Its a good question how to add elements to the tree. I decided to do this via a template method, as the actual types are hidden in the variadic template parameters, and making it possible to move temporary elements into the tree seemed a good idea. With a forwarding reference I can do both now. Also, the actual element in the vector is a shared_ptr, and not t, so that a call to make_shared is used to construct the actual shared_ptr containing the variant that actually holds t.

A few words on boost::variant, I recently showed how a generic visitor class with lambdas could look like in C++14, unfortunately I work with C++11. So, currently, all my visitor classes are just copy & paste creations, instead of using a generic version, which isn't available until C++14. Also, with boost 1.58, one can use lambdas as visitors, but this feature is again, C++14 only. So, as an example, this is the NameVisitor class, which imlpements a generic call operator to call the getName method:

struct NameVisitor : public boost::static_visitor< std::string >
{
    template< class T >
    std::string operator()(const T& t)const
    {
        return t.getName();
    }
};

Building the TreeModel for Qt

With the generic tree class in place, I have one task left: writing the actual model. Qt has a standard system to expose data to views: the model/view system. I already wrote a good overview on the topic in my introduction to Qt series, but omitted tree like models. The interface is the same, the ItemTreeModel class is derived from QAbstractItemModel:

class ItemTreeModel : public QAbstractItemModel
{
    Q_OBJECT
    using MyTreeItem = TreeItem< NameVisitor, TypeInfoVisitor,IdVisitor, Dir,Page>;
    std::shared_ptr< MyTreeItem > root;
    boost::container::flat_map<size_t,QIcon> type2icon;
public:
    using ItemPtr = MyTreeItem*;
    using constItemPtr = const MyTreeItem*;
    explicit ItemTreeModel(QObject *parent = 0);

    QModelIndex index(int row, int column, const QModelIndex &parent= QModelIndex()) const;
    QModelIndex parent(const QModelIndex &child) const;
    int rowCount(const QModelIndex &parent = QModelIndex()) const;
    int columnCount(const QModelIndex &parent= QModelIndex()) const;
    QVariant data(const QModelIndex &index, int role) const;
    
    std::shared_ptr< MyTreeItem > getRoot()const{return root;}
    template<class T>
    void emplace_back(QModelIndex &index, T && t);
    void insertIcon(size_t type, QIcon icon){type2icon[type]=icon;}
};

This model holds the root shared_ptr of the model, and a boost flat_map to store icons for the corresponding node type. The class has the "Qt standard constructor", taking a QObject parent pointer. Followed by the 5 methods, that need to be implemented to expose the tree to a potential view:

Since there is always only one column, columnCount simply returns 1. While rowCount either returns 0 or calls childCount() on the current node:

int ItemTreeModel::rowCount(const QModelIndex &parent) const
{
    if(!parent.isValid())
        return root->childCount();
    if(parent.column()>0)
        return 0;
    ItemPtr p =static_cast(parent.internalPointer());
    return p->childCount();
}

This also shows that raw pointers are kind of important for the model, they are stored in the QModelIndex class, which are created in the index method:

QModelIndex ItemTreeModel::index(int row, int column, const QModelIndex &parent) const
{
    if(!hasIndex(row, column, parent))
        return QModelIndex();

    ItemPtr item = root.get();
    if(parent.isValid())
        item = static_cast(parent.internalPointer());

    auto child = item->getChild(row);
    if(child)
        return createIndex(row,column,(void*)child.get());
    return QModelIndex();
}

ItemPtr is a typedef to the TreeItem class. So, the Index is constructed from the coordinates and a raw void*, which is obtained by calling shared_ptr::get. The parent method is very similar:

QModelIndex ItemTreeModel::parent(const QModelIndex &child) const
{
    if(!child.isValid())
        return QModelIndex();
    ItemPtr c = static_cast(child.internalPointer());
    auto p = c->getParent().get();
    if(p == root.get())
        return QModelIndex();
    return createIndex(p->row(),0,(void*)p);
}

Its simply creating the QModelIndex instance for a parent item. Last method to override is data:

QVariant ItemTreeModel::data(const QModelIndex &index, int role) const
{
    if(!index.isValid())
        return QVariant();
    ItemPtr item = static_cast(index.internalPointer());
    if(item)
    {
        switch(role)
        {
        case Qt::DisplayRole:
            return QString::fromStdString(item->name());
            break;
        case Qt::DecorationRole:
            {
                auto it = type2icon.find(item->type_id());
                if(it != type2icon.end())
                    return it->second;
            }
        }
    }
    return QVariant();
}

The data method is responsible for the actual data access stored in the treeitem class. As I handle two different roles (Display and Decoration), I simply use a switch to return the correct data, either a QIcon or the name of the node. Which I have to convert from std::string to QString. I made the decision, that the actual data classes are implemented without Qt, using the C++ Standard and boost.

In my first attempt to implement the data function you see above, I made a silly mistake, which caused a bug I hunted almost a full day long: returning QModelIndex() instead of QVariant(), which of course isn't the same, and the nature of the conversion to QVariant made the bug silent. The result was that the tree wasn't showing up in the QTreeView, no matter what I did, until I realized, that I returned the wrong type in data.

Seems like everything is in place, except the emplace_back method. The TreeItem class already has one, so why is another emplace method needed here? Lets have a look:

template<class T>
void emplace_back(QModelIndex &index, T&& t)
{
    if(!index.isValid())
        return;
    ItemPtr item = static_cast(index.internalPointer());
    if(!item)
        return;
    beginInsertRows(index,item->childCount(),item->childCount());
    item->emplace_back(std::forward<T>(t));
    endInsertRows();
}

Once a model is displayed inside a view, there is the need to notify the view when new items are added. This is done by calling beginInsertRows and endInsertRows. Its mandatory that endInsertRows is called, for exception safety, BOOST_SCOPE_EXIT could be used to ensure this is also done when an exception is thrown.

Last, but not least, the code which plugs the tree model into the QTreeView:

auto style = this->style();
ui->setupUi(this);

size_t dir_typeid = typeid(Dir).hash_code();
size_t page_typeid = typeid(Page).hash_code();
treemodel = new ItemTreeModel(this);
treemodel->insertIcon(dir_typeid,style->standardIcon(QStyle::SP_DirClosedIcon));
treemodel->insertIcon(page_typeid,style->standardIcon(QStyle::SP_FileIcon));
auto root = treemodel->getRoot();
root->emplace_back(Dir("foo"));
//root = root->getChild(0);
root->emplace_back(Dir("foo"));
root->emplace_back(Dir("foo"));
root->emplace_back(Dir("foo"));
root->emplace_back(Dir("foo"));
root->emplace_back(Dir("foo"));
auto c1 = root->getChild(2);
c1->emplace_back(Dir("foo"));
c1->emplace_back(Dir("foo"));
c1->emplace_back(Dir("foo"));
c1->emplace_back(Dir("foo"));//*/
ui->treeView->setModel(treemodel);

This code is from the constructor of the MainWindow class, first I access the QStyle element of the MainWindow instance, to later obtain some instances of Qt Standard Icons, which are displayed in the tree view. Next, I get the type hashes from Dir and Page, the currently used classes for the datamodel. Then the actual ItemTreeModel is constructed. Followed by a little bit of setup code that creates a mockup for the tree. The code to actually create a node in the tree does not yet exist. This is what the next part will be about: factories and displaying menus.

 

Part 3: Building factories in C++ with boost::factory

Join the Meeting C++ patreon community!
This and other posts on Meeting C++ are enabled by my supporters on patreon!

Copyright Meetingcpp GmbH 2024 ImprintPrivacy Policy