Problem with QStringList - bug or feature?


  • Moderators

    I ran into a problem with QStringList. I have been able to create a small example showing the problem. For comparison I have implemented the same based on stl. Only the Qt implementation does crash.

    @
    #include <QStringList>
    #include <QDebug>

    #include <list>
    #include <string>
    #include <iostream>

    using namespace std;

    int main(int argc, char *argv[])
    {
    list < string > sla;
    sla.push_back ( "one" );
    sla.push_back ( "two" );
    sla.push_back ( "three" );
    sla.push_back ( "four" );
    for ( list < string > :: iterator it = sla.begin(); it != sla.end(); )
    {
    if ( *it == "four" )
    {
    cerr << *it << endl;
    sla.erase ( it++ );
    }
    else
    {
    ++it;
    }
    }

    QStringList qsl;
    qsl << "one" << "two" << "three" << "four";
    qDebug() << qsl;
    for ( QStringList::iterator it = qsl.begin(); it != qsl.end(); )
    {
    if ( *it == "four" )
    {
    qDebug() << *it << endl;
    qsl.erase ( it++ );
    }
    else
    {
    ++it;
    }
    }
    return 0;
    }
    @

    After the forth element is erased. Apparently it is not qsl.end() and it loops again. The crash is in @ if ( *it == "four" )
    @
    since we are beyond the end of the list.
    I am wondering, if this is a feature of stl or a bug in Qt?



  • @qsl.erase ( it++ );@

    I would rather write :

    @it = qsl.erase(it);@ because the iterators may become invalid after erase. It is not clearly stated in the documentation.


  • Moderators

    Thanks for hint. This is certainly solving the problem. I was not aware of the return value for erase in lists.

    Yes, iterators are very often invalidated using erase in such loops. That is the reason of the post increment, which should point to end() when entering erase. Apparently, erase does change the value of end() internally. I am not sure, if this is correct.


  • Moderators

    This problem is in the mean while reported as a "bug report on JIRA":https://bugreports.qt.nokia.com/browse/QTBUG-21475



  • I would say that this is clearly documented. From the documentation of "QList::iterator":/doc/qt-4.8/qlist-iterator.html
    [quote]
    be aware that any non-const function call performed on the QList will render all existing iterators undefined.
    [/quote]
    Because QList::erase() is "clearly":http://developer.qt.nokia.com/doc/qt-4.8/qlist.html#erase non-const, any iterator into the list will be invalid after the call, including the iterator used for the list. However, as octal states, you can continue using the iterator that erase() itself returns.

    [EDIT: fixed Qlist::iterator link, Volker]


  • Moderators

    [quote author="Andre" date="1324635091"]I would say that this is clearly documented. From the documentation of [[doc:QList::iterator]]:
    [quote]
    be aware that any non-const function call performed on the QList will render all existing iterators undefined.
    [/quote]
    Because [[doc:QList#erase]] is clearly non-const, any iterator into the list will be invalid after the call, including the iterator used for the list. However, as octal states, you can continue using the iterator that erase() itself returns. [/quote]

    The program is using a post-increment on the iterator in the call to the erase method. This method is proposed for stl containers as the method avoiding an invalid iterator (e.g. Scott Meyers, Effective STL).
    The method suggested by octal is solving the problem. I have to admit that I have checked only right now.
    It was my misunderstanding that erase is rendering the iterator returned by end() to invalid. Which is not the case.

    IMHO it is not very fortunate to have this different behaviour for QList and its derivatives. If there are not very good reasons (e.g. performance), I still consider it a bug even so it is somehow documented. Well, it is certainly a perfide trap for those using stl containers frequently. I was stumbling into it while using QStringList.



  • Could you point me to the section in Meyers book where that is explained? It goes against all the standard iterator behaviour I am familiar with, but I will admit that I certainly can learn in this area. AFAIK, the standard on iterators is that:

    • Iterators that are invalid have undefined behaviour for all operations except assignment
    • Iterators that are incrementable must be dereferenceble.

    Using it++ in an operation that might invalidate the iterator seems to negate those requirements, at first sight?


  • Moderators

    It is Item 9 on page 49 last example for instance (10th printing Sept 2007). I seem to remember to have read it somewhere else too, but that was the reference I found quickly.
    The page number seem to vary based on the version of the book you have. There are a couple of pdf copies floating around in internet. "lmgtfy":http://lmgtfy.com/?q=effective+stl+scott+meyers+pdf , but the pages numbers are completely different from my hard copy.

    BTW your link is broken. The sentence you mention is not very obvious to find.



  • You can find about your problem and excellent example in the Thinking in C++, 2nd Volume book. This book is free! Download it, and search this string:
    "c.erase(remove(c.begin(), c.end(), value), c.end());"

    Anyway, with Qt use the Java-style iterators, much easier to use.


  • Moderators

    (at) broadpeak: Thanks for the reference

    It became an academic discussion on a bug or not in Qt. Certainly Qt is in that respect not conform with stl.

    (at) Andre: I knew that I read it first somewhere different. In Josuttis, The C++ Standard Library, A Tutorial and Reference, it is also in there in section 6.6.2 the last example right before start of section 6.6.3.



  • I think this is not a bug. The Qt is fully compliant with STL, because based on g++. The Qt "compiler" is a multistep compiler, at the and you will get a simple c++ source code, what the g++ can compile.

    And:
    container.erase is NOT the same as the container.remove

    Read the book what I wrote above, this book will show you the problem.

    (Similar problem exist with QModelIndex, you should ALWAYS query your modelindex validation, BEFORE you use it in an operation.)



  • Thanks for the item number, I have found it.

    The problem is, I think, that Meyers assumes that the remove() operation only invalidates the iterators pointing to that item. Alas, that is not the case for QList. QList (including QStringList) is not a linked list, but basically an array under the hood. So if you remove an item, items around the item removed may shift, thus also invalidating iterators pointing at those items. I am not exactly sure on the implementation details, but I could even imagine that the question which items shift (the ones behind, or the ones before the removed item) depends on the position of the item that was removed for performance reasons.

    I think that your original approach would probably work just fine on a QLinkedList, which is much closer to the std::list container than QList is in terms of structure.


Log in to reply
 

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