Erasing QHash while iterating the hash table?



  • The Qt 4.8 documentation on QHash suggested erase keys in hash table like this:

    QHash<QString, int>::iterator i = hash.begin();
    while (i != hash.end()) {
        QHash<QString, int>::iterator prev = i;
        ++i;
        if (prev.key().startsWith("_"))
            hash.erase(prev);
    }
    

    But isn't this snippet of code equivalent to the following:

    QHash<QString, int>::iterator i = hash.begin();
    while (i != hash.end()) {
        if (i.key().startsWith("_"))
            hash.erase(i++);
        else
            i++;
    }
    

    Why bother using the temporary variable prev ? I did some research online and find that the compiler would sometimes reorder the instruction so that it's not that easy to tell when exactly will i get increased. But I think even in the worst case the variable i should get increased before the hash table erase the key? Thus there is no need to use the Qt recommended style.


  • Lifetime Qt Champion

    Hi and welcome to devnet,

    To discuss that kind of design recommendation you should rather post your question on the interest mailing list You'll find there Qt's developers/maintainers. This forum is more user oriented.


  • Moderators

    Your version is incorrect. It only increases i when an item is erased. If there is at least one item not starting with _ in your hash then the while loop is infinite.

    The reason the iterator is preserved is that the value pointed by it is possibly erased. You can't then increment an iterator that points to erased value. Thus a copy is made and increased before an item is erased. As an alternative you could use the value returned from erase like this:

    QHash<QString, int>::iterator i = hash.begin();
    while (i != hash.end()) {
        if (i.key().startsWith("_"))
            i = hash.erase(i);
        else
            ++i;
    }
    


  • @Chris-Kawa Thank you. Sorry I made the silly mistake here. I have corrected the logic so that the loop will increase the iterator every time.

    I don't agree with what you said about the iterator. The postfix increment is supposed to first increase the iterator i and return the value of the expression `i++' which is the iterator before the increment. I think it's equivalent to:

    //defined inside template QHash<K, V>
    iterator operator++( int ) {
        iterator ret = *this;
        ++*this;
        return ret;
    }
    


  • Thanks @SGaist for letting me know . I'll definitely do it for my future posts.


  • Moderators

    True. I got carried away.
    So the only difference is that if you use prefix increment you do the iterator ret = *this; part manually. With inlining and whatnot I'm pretty sure the optimized result would be almost, if not exactly, the same.



  • Thanks @Chris-Kawa. Just wanna confirm the correctness.


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.