QMap::contains() VS QMap::find()

Question

I often see code like:

if(myQMap.contains("my key")){
    myValue = myQMap["my key"];
}

which theoretically performs two look-up's in the QMap.

My first reaction is that it should be replaced by the following, which performs one lookup only and should be two times faster:

auto it = myQMap.find("my key");
if(it != myQMap.end()){
    myValue = it.value();
}

I am wondering if QMap does this optimization automatically for me? In other words, I am wondering if QMap saves the position of the last element found with QMap::contains() and checks it first before performing the next lookup?

Allamerican

Pretty sure it does not. You can use the same const QMap from multiple threads which would cause serious trouble if it were caching anything (and even in the best caching would only work for one thread) – Helsinki

Here is the source code for QMap: qt.gitorious.org/qt/qt/source/… it isn't trivial to read, but it should help you get an answer if you really want it. – Dayledaylight

Answer 1

I would expect that QMap provides both functions for a better interface to the class. It's more natural to ask if the map 'contains' a value with a specified key than it is to call the 'find' function.

As the code shows, both find and contains call the following internal function: -

Node *n = d->findNode(akey);

So if you're going to use the returned iterator, then using find and checking the return value will be more efficient, but if you just want to know if the value exists in the map, calling contains is better for readability.

If you look at the source code, you'll see that QMap is implemented as a binary tree structure of nodes. Calling findNode iterates through the nodes and does not cache the result.

Bullate

How do you know that findNode(akey) don't do some caching itself ? if (akey == lastKey){return lastNode;} – Allamerican

@nbilal, please correct me if I'm wrong, but looking at the source code, it doesn't appear to do so. – Bullate

I wouldn't ask here if I knew the answer :) You half answered my question, maybe you can improve your answer by explaining and giving some kind of proof that findNode itself doesn't do any caching. Thanks. – Allamerican

If you look at the source code, you'll see that QMap is implemented as a binary tree structure of nodes. Calling findNode iterates through the nodes and does not cache the result. – Bullate

Can you edit your answer and add this information ? copying and pasting some code from QMap that shows that there is no caching done would also help. – Allamerican

Really?! You're kidding, right? You want me to post Qt code to show you something isn't there? In addition, the link in the answer by @hluk is the source code. Click that and follow the function calls. – Bullate

Well your edit is useful, it wasn't easy to convince you to add this sentence at the end of your post. I was just trying to make your answer more convincing for the next person who is asking the same question and end up here. – Allamerican

But how much of a hit is iterator allocation? You will have to store it as a local variable. – Videlicet

Answer 2

QMap source code reveals that there is no special code in QMap::contains() method.

In some cases you can use QMap::value() or QMap::values() to get value for a key and check if it is correct. These methods (and const operator[]) will copy the value, although this is probably OK for most Qt types since their underlying data are copied-on-write (notably QMap itself).

Plutonian