Search code examples
c++indexingstlconstantsqlist

Why doesn't QList::at() check if index exists and also returns a read-only value?

This question is more of an inquiry then actually seeking a solution for a problem.

QList::at() not only doesn't check if an index is out of bounds but it also returns a const hence it can be used only in a read-only scenario:

const T &QList::at(int i) const

Returns the item at index position i in the list. i must be a valid index position in the list (i.e., 0 <= i < size()).

This function is very fast (constant time).

I've just found out these peculiar implementation details of QList while trying to assign a new value to an element in my list and I'm wondering if there is a reason for doing that.

No check for index validity

In C++ STL if we take std::array or std::vector (I'm not taking std::list since it doesn't have std::list::at() at all) we have the following:

std::vector::at

The function automatically checks whether n is within the bounds of valid elements in the vector, throwing an out_of_range exception if it is not

At first I thought that the check is not included to ensure the "This function is very fast (constant time)." however after looking at the implementation of QList I have to say even if the check was included a constant time (and high speed) is most certainly ensured.

A check for out of bounds would require two things (as far as I know):

  • Check if given index is < 0 - this is a constant time check (O(1) if we use some wacky notation). Obviously we can't have negative index (we can in Python but it has another meaning ;))

  • Check if given index is < QList::size() - constant time is also present here since the way QList::size() is implemented is:

    inline int size() const Q_DECL_NOTHROW { return d->end - d->begin; }

    This is again O(1) (if I'm not mistaken) since both values are stored inside the QList::d parameter which is a pointer to

    struct Data {
  QtPrivate::RefCount ref;
  int alloc, begin, end;
  void *array[1];
};

    so accessing those and calculating their difference is not hurting the performance that much (obviously it has some minor impact since it introduces a couple of access and arithmetic operations plus backing up and restoring the stack due to the jump inside the QList::size() function).

So why dump the check for index validity? Is the performance impact actually that big?

Returning a read-only value

By doing so the QList::at() function offers a hidden and (omho) not very useful feature which makes the difference in using it and QList::[] even more confusing. Also the C++ STL equivalent for std::vector and std::array allows assignment of new values using this function.

Solution

  • There are "3" ways of accessing an item from its index in a QList:

    const T& QList::at(int) const
T& QList::operator[](int)
const T& QList::operator[](int) const

    If you look at the doc, you will see that the last one is simply:

    Same as at(). This function runs in constant time.

    So we are left with the first one (at) and the non-const operator[]. Here is the problem, the documentation of the second one tells you that1:

    If this function is called on a list that is currently being shared, it will trigger a copy of all elements. Otherwise, this function runs in constant time. If you do not want to modify the list you should use QList::at().

    Note: This is also true for QVector:

    Note that using non-const operators can cause QVector to do a deep copy.

    1 For QList, this is actually only true for Qt 5, not for Qt 4 (at least in the documentation), but for QVector it was already true for Qt 4, so the .at method was probably made consistent between all Qt containers.

    This means that you cannot use operator[] directly on a non-const shared QList or on a non-const QVector, you would need to do something like:

    QList<T> &mySharedQList = ...;
const QList<T> &myConstRef = mySharedQList;
myConstRef[0]; // Only ways not to copy the original QList

    My guess is that the purpose of the .at is to provide you with a method that guarantees a constant access time, whatever the QList or QVector is (which operator[] does not guarantee). You do not need such method for standard library containers because non-const operator[] are already guaranteed to run in constant time (they are never going to make a copy).

    Regarding the check on the index, this is probably to keep the behavior of the operator[] since, unlike std::vector, you probably want to use .at everywhere you only need to read data.