Order of QObject children (strategy question)

Question

For one of my projects I have a tree of QObject derived objects, which utilize QObject's parent/child functionality to build the tree.

This is very useful, since I make use of signals and slots, use Qt's guarded pointers and expect parent objects to delete children when they are deleted.

So far so good. Unfortunately now my project requires me to manage/change the order of children. QObject does not provide any means of changing the order of its children (exception: QWidget's raise() function - but that's useless in this case). So now I'm looking for a strategy of controlling the order of children. I had a few ideas, but I'm not sure about their pros & cons:

Option A: Custom sort index member variable

Use a int m_orderIndex member variable as a sort key and provide a sortedChildren() method which returns a list of QObjects sorted by this key.

• Easy to implement into existing object structure.
• Problematic when QObject::children() method is overriden - will lead to problems during loops when items' order is changed, also is more expensive than default implementation.
• Should fall back to QObject object order if all sort keys are equal or 0/default.

---

Option B: Redundant list of children

Maintain a redundant list of children in a QList, and add children to it when they are created and destroyed.

• Requires expensive tracking of added/deleted objects. This basically leads to a second child/parent tracking and lot of signals/slots. QObject does all of this internally already, so it might not be a good idea to do it again. Also feels like a lot of bloat is added for a simple thing like changing the order of children.
• Good flexibility, since a QList of children can be modified as needed.
• Allows a child to be in the QList more than one time, or not at all (even though it might be still a child of the QObject)

---

Option C: ...?

Any ideas or feedback, especially from people who already solved this in their own projects, is highly appreciated. Happy new year!

Answer 1

What about something like...

1. QList listChildren = (QList)children();
2. sort listChildren
3. foreach listChildren setParent( TempParent )
4. foreach listChildren setParent( OriginalParent )

Answer 2

I spent a lot of time going through all these options in the past days and discussed them carefully with some other programmers. We decided to go for Option A.

Each of the objects we are managing is a child of a parent object. Since Qt does not provide any means of re-ordering these objects, we decided to add a int m_orderIndex property to each object, which defaults to 0.

Each object has an accessor function sortedChildren() which returns a QObjectList of the children. What we do in that function is:

1. Use the normal QObject::chilren() function to get a list of all available child objects.
2. dynamic_cast all objects to our "base class", which provides the m_orderIndex property.
3. If the object is castable, add it to a temporary object list.
4. use qSort with a custom LessThan function to find out if qSort needs to change the order of two objects.
5. Return the temporary object list.

We did this for the following reasons:

• Existing code (especially Qt's own code) can continue using children() without having to worry about side effects.
• We can use the normal children() function in places where the order does not matter, without having any performance loss.
• In the places where we need the ordered list of children, we simply replace children() by sortedChildren() and get the desired effect.

One of the good things about this approach is, that the order of children does not change if all sort indices are set to zero.

Sorry for answering my own question, hope that enlightens people with the same problem. ;)

Answer 3

I had the same problem and I solved it by Option B. Tracking isn't that difficult, just create a method "void addChild(Type *ptr);" and another one to delete a childitem.

You don't suffer from evil redundancy if you exclusivly store the children within the private/public childlist (QList) of each item and drop the QObject base. Its actually quite easy to implement auto-child-free on free (though that requires an extra parent pointer).

Answer 4

I do not have an separate option C, but comparing option A and B, you are speaking ~4 bytes (32-bit pointer, 32-bit integer) in either case, so I'd go with option B, as you can keep that list sorted.

To avoid the additional complexity of tracking children, you could cheat and keep your list sorted and tidy, but combine it with a sortedChildren method that filters out all the non-children. Complexity wise, this aught to end up around O(nlogm) (n = children, m = list entries, assuming that m >= n, i.e. children are always added) unless you have a large turnaround on children. Let's call this option C.

Quicksort, in your suggested option A, gives you O(n2) (wc), but also requires you to retreive pointers, trace them, retreive an integer, etc. The combined method only needs a list of the pointers (aught to be O(n)).

Answer 5

A nasty hack: QObject::children() returns a reference-to-const. You could cast away the const-ness and thus manipulate the internal list directly.

This is pretty evil though, and has the risk of invalidating iterators which QObject keeps internally.