Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

STL or Qt containers?

Tags:

c++

stl

qt

This is a difficult to answer question. It can really boil down to a philosophical/subjective argument.

That being said...

I recommend the rule "When in Rome... Do as the Romans Do"

Which means if you are in Qt land, code as the Qt'ians do. This is not just for readability/consistency concerns. Consider what happens if you store everything in a stl container then you have to pass all that data over to a Qt function. Do you really want to manage a bunch of code that copies things into/out-of Qt containers. Your code is already heavily dependent on Qt, so its not like you're making it any more "standard" by using stl containers. And whats the point of a container if everytime you want to use it for anything useful, you have to copy it out into the corresponding Qt container?


I started by using std::(w)string and the STL containers exclusively and converting to/from the Qt equivalents, but I have already switched to QString and I find that I'm using Qt's containers more and more.

When it comes to strings, QString offers much more complete functionality compared to std::basic_string and it is completely Unicode aware. It also offers an efficient COW implementation, which I've come to rely on heavily.

Qt's containers:

  • offer the same COW implementation as in QString, which is extremely useful when it comes to using Qt's foreach macro (which does a copy) and when using meta-types or signals and slots.
  • can use STL-style iterators or Java-style iterators
  • are streamable with QDataStream
  • are used extensively in Qt's API
  • have a stable implementation across operating systems. A STL implementation must obey the C++ standard, but is otherwise free to do as it pleases (see the std::string COW controversy). Some STL implementations are especially bad.
  • provide hashes, which are not available unless you use TR1

The QTL has a different philosophy from the STL, which is well summarized by J. Blanchette: "Whereas STL's containers are optimized for raw speed, Qt's container classes have been carefully designed to provide convenience, minimal memory usage, and minimal code expansion."
The above link provides more details about the implementation of the QTL and what optimizations are used.


The Qt containers are more limited than the STL ones. A few examples of where the STL ones are superior (all of these I have hit in the past):

  • STL is standardized, doesn't change with every Qt version (Qt 2 had QList (pointer-based) and QValueList (value-based); Qt 3 had QPtrList and QValueList; Qt 4 now has QList, and it's nothing at all like QPtrList or QValueList). Qt 6 will have a QList that's QVector while QVector will be deprecated. Even if you end up using the Qt containers, use the STL-compatible API subset (ie. push_back(), not append(); front(), not first(), ...) to avoid porting yet again come Qt 6. In both Qt2->3 and Qt3->4 transitions, the changes in the Qt containers were among those requiring the most code churn. I expect the same for Qt5->6.
  • STL bidirectional containers all have rbegin()/rend(), making reverse iteration symmetric to forward iteration. Not all Qt containers have them (the associative ones don't), so reverse iteration is needlessly complicated.
  • STL containers have range-insert() from different, but compatible, iterator types, making std::copy() much less often needed.
  • STL containers have an Allocator template argument, making custom memory management trivial (typedef required), compared with Qt (fork of QLineEdit required for s/QString/secqstring/). EDIT 20171220: This cuts Qt off of advances in allocator design following C++11 and C++17, cf. e.g. John Lakos' talk (part 2).
  • There's no Qt equivalent to std::deque.
  • std::list has splice(). Whenever I find myself using std::list, it's because I need splice().
  • std::stack, std::queue properly aggregate their underlying container, and don't inherit it, as QStack, QQueue do.
  • QSet is like std::unordered_set, not like std::set.
  • QList is a just weird.

Many of the above could be solved quite easily in Qt, but the container library in Qt seems to experience a lack of development focus at the moment.

EDIT 20150106: After having spent some time trying to bring C++11-support to Qt 5 container classes, I have decided that it's not worth the work. If you look at the work that is being put into C++ standard library implementations, it's quite clear that the Qt classes will never catch up. We've released Qt 5.4 now and QVector still doesn't move elements on reallocations, doesn't have emplace_back() or rvalue-push_back()... We also recently rejected a QOptional class template, waiting for std::optional instead. Likewise for std::unique_ptr. I hope that trend continues.

EDIT 20201009: Come Qt 6, they will again rewrite their containers in incompatible ways:

  • QVector will be renamed QList, so you lose stabiliy-of-reference when using QList.
  • QVector (the name) will be deprecated. QLinkedList will be removed.
  • QHash and QSet are now Open-Addressing Hash Tables, also losing stability-of-reference guarantees
  • QMap will be backed by std::map, possibly changing insertion behaviour and, for QMultiMap, order of equivalent elements.
  • Qt container sizes and indexes will become qsizetype (more or less std::ptrdiff_t) (was: int).

So, if you want to rewrite your container-using code, then go ahead with the Qt containers. Everyone else enjoys decades of stability with the STL containers.


Let's break down these claims into actual measurable phenomena:

  • Lighter: Qt containers use less memory than STL containers
  • Safer: Qt containers have less opportunity to be improperly used
  • Easier: Qt containers present less of an intellectual burden

Easier

The claim made in this context is that java-style iteration is somehow "easier" than STL style, and therefore Qt is easier to use because of this additional interface.

Java Style:

QListIterator<QString> i(list);
while (i.hasNext())
    qDebug() << i.next();

STL Style:

QList<QString>::iterator i;
for (i = list.begin(); i != list.end(); ++i)
    qDebug << *i;

The Java iterator style has the benefit of being a little smaller and cleaner. The problem is, this isn't actually STL style anymore.

C++11 STL Style

for( auto i = list.begin(); i != list.end(); ++i)
    qDebug << *i;

or

C++11 foreach style

for (QString i : list)
    qDebug << i;

Which is so drastically simple that there's no reason to ever use anything else (unless you don't support C++11).

My favorite, however, is:

BOOST_FOREACH(QString i, list)
{
    qDebug << i;
}

So, as we can see, this interface gains us nothing except an additional interface, on top of an already sleek, streamlined, and modern interface. Adding an unnecessary level of abstraction on top of an already stable and usable interface? Not my idea of "easier".

Also, Qt foreach and java interfaces add overhead; they copy the structure, and provide an unnecessary level of indirection. This might not seem like much, but why add a layer of overhead to provide a not-that-much-simpler interface? Java has this interface because java doesn't have operator overloading; C++ does.

Safer

The justification that Qt gives is the implicit sharing problem, which is neither implicit nor a problem. It does involve sharing, however.

QVector<int> a, b;
a.resize(100000); // make a big vector filled with 0.

QVector<int>::iterator i = a.begin();
// WRONG way of using the iterator i:
b = a;
/*
Now we should be careful with iterator i since it will point to shared data
If we do *i = 4 then we would change the shared instance (both vectors)
The behavior differs from STL containers. Avoid doing such things in Qt.
*/

First, this isn't implicit; you are explicitly assigning one vector to another. The STL iterator specification clearly indicates that iterators belong to the container, so we've clearly introduced a shared container between b and a. Second, this isn't a problem; as long as all the rules of the iterator specification are followed, absolutely nothing will go wrong. The only time something goes wrong is here:

b.clear(); // Now the iterator i is completely invalid.

Qt specifies this as if it means something, like a problem arises de novo from this scenario. It doesn't. The iterator is invalidated, and just like anything that can be accessed from multiple disjoint areas, this is just how it works. In fact, this will occur readily with Java style iterators in Qt, thanks to it's heavily reliance on implicit sharing, which is an antipattern as documented here, and at many other areas. It seems especially strange for this "optimization" to be put into use in a framework moving more and more towards multithreading, but that's marketing for you.

Lighter

This one is a bit trickier. The use of Copy-On-Write and Implicit Sharing and Growth Strategies makes it very difficult to actually make guarantees about how much memory your container will use at any given time. This is unlike the STL, which gives you strong algorithmic guarantees.

We know the minimal bound of wasted space for a vector is the square root of the length of the vector, but there seems to be no way to implement this in Qt; the various "optimizations" they support would preclude this very important space saving feature. The STL does not require this feature (and most use a doubling growth, which is more wasteful), but it's important to note that you could at least implement this feature, if need be.

The same is true of doubly linked lists, which could use XOr linking to drastically reduce space used. Again, this is impossible with Qt, due to it's requirements for growth and COW.

COW can indeed make something lighter, but so can Intrusive Containers, such as supported by boost, and Qt used these frequently in the earlier versions, but they are not used as much anymore because they are hard to use, unsafe, and impose a burden on the programmer. COW is a much less intrusive solution, but unattractive for the reasons posed above.

There is no reason why you could not use STL containers with the same memory cost or less than Qt's containers, with the added benefit of actually knowing how much memory you will waste at any given time. It is, unfortunately, impossible to compare the two in raw memory usage, because such benchmarks would show wildly different results in different use cases, which is the exact sort of problem that the STL was designed to correct.

In Conclusion

Avoid use of Qt Containers when ever possible to do so without imposing a copying cost, and use STL type iteration (perhaps through a wrapper or the new syntax), whenever possible.


STL containers:

  • Have performance guarantees
  • Can be used in STL algorithms which also have performance guarantees
  • Can be leveraged by third-party C++ libraries like Boost
  • Are standard, and likely to outlive proprietary solutions
  • Encourage generic programming of algorithms and data structures. If you write new algorithms and data structures that conform to STL you can leverage what STL already provides at no cost.

Qt containers use copy-on-write idiom.


One of the main issues is that Qt's API expects you to provide data in Qt's containers, so you may as well simply use the Qt containers rather than transforming back and forth between the two.

Also, if you're already using the Qt containers, it might be slightly more optimal to use them exclusively, as you would not have to include the STL header files and potentially link in the STL libraries. However, depending on your toolchain, that may happen anyway. Purely from a design perspective, consistency is generally a good thing.