rbaleksandar rbaleksandar - 3 months ago 19
C++ Question

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.

Answer

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.

Comments