QRegion will be iterable in Qt 5.8 - seamless integration with C++11 range-for

20.04.2016 Marc Mutz No comments

A novel solution to an old problem

The QRegion class specifies a clip region for a painter. You can also query a QPaintEvent for the region() to limit the paint operations necessary in partial repaints.

A region can be anything from a simple rectangle to a bitmap mask, but virtually all code that inspects a QRegion does so by decomposing the region into non-overlapping rectangles and looping over the rectangle list.

Traditionally, the only way to do this has been by calling rects(), which returns a QVector<QRect>.

But rects() has a problem: In the very common case that the region contains just one rectangle, the QRegion is internally represented by a QRect and not a QVector, and the mere act of calling rects() makes QRegion create one.

Clearly, the memory allocation involved in creating a QVector just to return a single rectangle is not helpful. Indeed, Qt developers usually work around this problem by inspecting QRegion::rectCount() before calling rects() and resolve to calling QRegion::boundingRect() instead for regions with just rectangle.

Lack of efficient computational basis

That is really bad API, but it’s hard to spot.

Alexander Stepanov, the inventor of the STL, tells us that a class should provide an efficient computational basis (Elements of Programming, p.6), and allocating memory in the most common situation squarely fails that test.

We also all know that APIs should be easy to use correctly and hard to use incorrectly. But in this case, the straight-forward way of using the API:

void inspect(const QRegion &region) {
    for (const QRect &rect : region.rects())
        inspect(rect);
}

is different from the correct way of using the API:

void inspect(const QRegion &region) {
    if (region.rectCount() == 1) {
        inspect(region.boundingRect());
    } else {
        const auto rects = region.rects(); // make const to avoid a detach in the implicit begin() call below:
        for (const QRect &rect : rects)
            inspect(rect);
    }
}

Not only is the first version easier to read and maintain, it also expands to a lot less executable code.

But we can do much better…

QRegion as a container of QRect

Realising this problem, I resolved to fix it by exposing to users the fact that QRegion is a container of QRects.

I did this by providing iterators and begin()/end() on QRegion. The functionality has been merged for Qt 5.8.

Unlike rects(), the new functions can be noexcept, saving even more executable code in projects that, unlike Qt itself, don’t switch off exceptions.

The iterator type is just const QRect*, so as to abstract away the difference between iterating over a QVector<QRect> and over a single QRect. Quoting qregion.cpp:

    const QRect *begin() const Q_DECL_NOTHROW
    { return numRects == 1 ? &extents : rects.data(); } // avoid vectorize()

    const QRect *end() const Q_DECL_NOTHROW
    { return begin() + numRects; }

No mutable iterators are provided

Because QRegion maintains a running bounding-rect, a mutable iterator would have to call into QRegion for every change, which doesn’t make sense. Consequently, no mutable iterators are provided for QRegion.

As a nice side-effect, that means that begin() and end() are const and thus do not cause the hidden detaching problem that plagues other Qt container classes.

In particular, QRegions can now be used as an argument to C++ range-for loops without Qt 5.7’s qAsConst() protection:

void inspect(const QRegion &region)
    noexcept(noexcept(inspect(std::declval<QRect&>()))) // noexcept whenever inspect(QRect) is
{
    for (const QRect &rect : region)
        inspect(rect);
}

Benefits

Apart from providing a non-allocating, non-throwing way to inspect a region, there are other positive effects. Because no QVector is returned that needs to be destroyed by the caller, even in projects (such as QtGui) that are compiled with exceptions disabled, porting even a few loops to the new construct saves more than 1KiB in text size on optimized GCC 5.3 Linux AMD64 builds, not to mention countless memory allocations at runtime.