QLinkedList operator+ efficiency

Question

I am finding myself concatenating QLinkedLists a lot, so I am getting concerned about the efficiency of Qt's QLinkedList::operator+( const QLinkedList<T> &other ) const

I tried to look up the source code for the operator+, but I couldn't make much sense of it. I've asked for help on that in a different question.

Is using the operator+() operator to concatenate two QLinkedLists of the same type efficient? Does the implementation just have the iterator skip from the first list to the second list, so basically there is no penalty for calling operator+()?

score 4 · Accepted Answer · edited May 23 '17 at 11:50

This is what I found:

template <typename T>
QLinkedList<T> QLinkedList<T>::operator+(const QLinkedList<T> &l) const
{
    QLinkedList<T> n = *this;
    n += l;
    return n;
}

So it makes a copy of the entire list, uses the operator+=() and returns the new list. For a const method, it's as straight-forward as it gets.

But I do have concerns:

If you're trying to merge large lists... I would personally use std::list instead. In other words, there are many cases where you don't need to keep a copy of both lists (the subsets) and this is where the penalties are.

QList a, b, c;
// ... etc.. assumes a & b grow to great sizes
c = a + b;

From the example above, if you need to keep a & b around, then it's clearly a necessary cost to create a new list from the subsets. But if you don't need a & b after list c has been created... then using the operator+ is not optimal. And of course - for really small lists this is all trivial.

The std::list container that is similar to QLinkedList.

For std::list, I'd use something like splice to merge two lists together. I can't find anything similar for QLinkedList, but like I already said, I do tend to favor STL containers in my own code.

QLinkedList operator+ efficiency

1 Answers1