Comparing/sorting QVariant in Qt6

angela2016

Hi,

I'm trying to move from Qt5 to Qt6 and I'm frustrated with QVariant not being comparable anymore.

Basically I have a file manager with a custom file system model and a custom header widget that provides filtering. For the filtering option I need to retrieve a unique, sorted list of the currently displayed values in the file system model to fill the model I use in the filtering widget.

I used to do this by filling a QMap<QVariant,bool> with all the values, then getting the QList<QVariant> with keys(), which worked nicely and fast.

Now, apparently, I can't use QMap or QSet and I can't sort a QList because QVariant is not comparable. Furthermore, when I try to keep QList unique by checking first whether the list contains the value or not, filling the QList with 5000 values takes 20 secs if the values are QDateTime (strings and numbers work fine, but still no idea how to sort them).

Am I missing something? Can I somehow provide my own comparison for QVariant? Because right now my only idea is to write the exact same code 5 times for integers, dates, strings, etc... which seems insane.

Thanks in advance.

Best wishes,
Angela

angela2016

Ok, I found a solution for my program. I now fill a QMap<QString,QVariant> instead, where QString is retrieved from a different user role of the model and is usually the QVariant.toString() with exceptions for the numeric values to correct the sorting.

JonB

@angela2016 said in Comparing/sorting QVariant in Qt6:

Now, apparently, I can't use QMap or QSet and I can't sort a QList because QVariant is not comparable.

To be exact, QVariant is still equality-comparable (==) but no longer less-than-comparable. Which makes sense to me, I never knew it used to be less-than-comparable and don't see how that ever worked. And QMap orders its keys, so key must be less-than-comparable not just equality-comparable.

Am I missing something? Can I somehow provide my own comparison for QVariant?

I know you have solved this now, but I guess if you really needed that you could sub-class QVariant to something where you implemented < operator and did whatever you considered suitable for at least the types you wanted to support.

Furthermore, when I try to keep QList unique by checking first whether the list contains the value or not, filling the QList with 5000 values takes 20 secs if the values are QDateTime

Hmmm. That sounds slow. A while ago there was a "bug" whereby QDateTimes compared or something really slow, because behind the scenes there was a lot of converting between local time and UTC going on. That should have been removed (back in 5.x IIRC). You are saying 5,000 QDateTimes into a list with comparison for equality check on each insert (I make that average 2,500 * 5,000 == 12.5 million comparisons?) takes 20 seconds? Do you have sample code for that?

BTW, if you really wanted to do this comparing for uniqueness on each insert is not optimal at all. Better is: insert (append) all in whatever order without checking, then sort, then remove adjacent uniques. That should be a lot/vastly fewer comparisons than the 12.5M!

The std::sort() function in C++ performs \(Nlog(N)\) comparisons to sort \(N\) items. This means that in the worst case, the complexity is \(O(Nlog(N))\).

For 5,000 items I make that 18.5K instead of 12.5M, so ~ 1,000 times faster :)

Or, just for the record, if you only want uniqueness you can still use QMap or QHash. But that won't help you with sort order, which I think you want. Or, if you want to stick with QList and uniqueness but don't want to do my store all/sort/unique (e.g. you want to know at insert time whether item is already present) don't forget that since your list is sorted you can do binary search for insertion to reduce comparisons.

The above is for less-than comparable types, like int or QDateTime, else you can't sort. If you have QVariant and need to stick with it, and you have mixed types, presumably equality-only check during insert if you want that is best done via QHash, then convert to list which will now be unique at end.

angela2016

@JonB said in Comparing/sorting QVariant in Qt6:

Hmmm. That sounds slow. A while ago there was a "bug" whereby QDateTimes compared or something really slow, because behind the scenes there was a lot of converting between local time and UTC going on. That should have been removed (back in 5.x IIRC). You are saying 5,000 QDateTimes into a list with comparison for equality check on each insert (I make that average 2,500 * 5,000 == 12.5 million comparisons?) takes 20 seconds? Do you have sample code for that?

    QList<QVariant>vValueList;
    qDebug()<< Q_FUNC_INFO << "test 1 start" << QDateTime::currentDateTime();
    QDateTime vV = QDateTime::currentDateTime();
    for( int row = 0; row < 5000; ++row ){
        vV = vV.addDays(1);
        if(!vValueList.contains(vV)){
            vValueList.append(vV);
        }
    }
    qDebug()<< Q_FUNC_INFO << "test 1 end" << QDateTime::currentDateTime();

BTW, if you really wanted to do this comparing for uniqueness on each insert is not optimal at all. Better is: insert (append) all in whatever order without checking, then sort, then remove adjacent uniques. That should be a lot/vastly fewer comparisons than the 12.5M!

The std::sort() function in C++ performs \(Nlog(N)\) comparisons to sort \(N\) items. This means that in the worst case, the complexity is \(O(Nlog(N))\).

Or, just for the record, if you only want uniqueness you can still use QMap or QHash. But that won't help you with sort order, which I think you want. Or, if you want to stick with QList and uniqueness but don't want to do my store all/sort/unique (e.g. you want to know at insert time whether item is already present) don't forget that since your list is sorted you can do binary search for insertion to reduce comparisons.

No, I can't. It won't compile:

    QMap<QVariant,bool>vTest;
    vTest.insert(35,true);

gives me "invalid operands to binary expression ('const QVariant' and 'const QVariant')" and "static_assert failed due to requirement 'std::__is_invocable<std::less<QVariant> &, const QVariant &, const QVariant &>{}' "comparison object must be invocable with two arguments of key type".
And similar with:

    QList<QVariant> vTest;
    vTest.append(35);
    vTest.append(5);
    vTest.append(50);
    std::sort(vTest.begin(), vTest.end());

The above is for less-than comparable types, like int or QDateTime, else you can't sort. If you have QVariant and need to stick with it, and you have mixed types, presumably equality-only check during insert if you want that is best done via QHash, then convert to list which will now be unique at end.

Yes, I have to stick with QVariant because that's what I get from the data() function of the model. Type is always the same within the column (the function always works on one column only) but not across columns. So plan B would have been to check for the type of the first value and then rewrite the function for each type I need.

JonB

@angela2016 said in Comparing/sorting QVariant in Qt6:

No, I can't. It won't compile:

I don't understand. I said I agreed that Qt6 has removed QVariant less-then-comparison and hence cannot be used with QMap. So QMap<QVariant,bool>vTest;, and equally QList<QVariant> vTest; std::sort(vTest.begin(), vTest.end()); can't compile and none of my suggestions were for that, so I don't know where you got it from.

Yes, I have to stick with QVariant because that's what I get from the data() function of the model.

Which is why I said you could subclass QVariant and add a less-then-comparator for your types & purposes. Then when you store values with setData() pass in an instance of your derived class (created in your "custom file system model") instead of a plain QVariant and declare your QMap with that subclass for key.

Type is always the same within the column (the function always works on one column only) but not across columns.

You can code for this in various ways, depending on where/how you compare/sort. You can have specifically-typed getter/setter for each column (wrapped around data()) and use that getter in the comparison instead of a QVariant if you do your own sorting, or if your model uses plain QVariant and you are using QSortFilterProxyModel you can override its bool QSortFilterProxyModel::lessThan(const QModelIndex &source_left, const QModelIndex &source_right) const to deal with the QVariant types in one function as you see fit.

I will have a look at the timing of your code as-is. However I gave you several ways to drastically reduce the number of comparisons required in your QList-unique code, so it's not surprising your implementation is the slowest there is.

angela2016

I don't understand. I said I agreed that Qt6 has removed QVariant less-then-comparison and hence cannot be used with QMap. So QMap<QVariant,bool>vTest;, and equally QList<QVariant> vTest; std::sort(vTest.begin(), vTest.end()); can't compile and none of my suggestions were for that, so I don't know where you got it from.

Then I misunderstood that part, sorry. I thought you said that I could still use QVariant as a key with QMap but that it just wouldn't sort.

I will have a look at the timing of your code as-is. However I gave you several ways to drastically reduce the number of comparisons required in your QList-unique code, so it's not surprising your implementation is the slowest there is.

I don't disagree with you here and since I've solved the problem in a different way and don't need that code, it's not an issue right now. But I do find it curious that QDateTime takes so much longer than other types.

JonB

@angela2016 said in Comparing/sorting QVariant in Qt6:
You are inserting QDateTimes into the list as QDateTime::currentDateTime(), which is a local time. Under Qt6.4.2, gcc 13.2.0, Ubuntu 22.04, compiled for debug, this takes me about 25 seconds, not dissimilar to you.

This is because of what Qt does when comparing local times. I think it converts the to UTC, or something similar, and that is (apparently, known for other posts) a very slow operation. If I change it to QDateTime::currentDateTimeUtc() it drops to half a second, so 50x faster! Try to store your times in UTC? In any case both Linux and Windows NTFS store file datetimes in UTC anyway, so try to use that if you want to look at file times. Otherwise I wrote above how you can vastly speed up in either case by not doing a contains() check on each append() and instead storing them all then sorting and remove adjacent uniques.

angela2016

Thanks for the explanation, I'll keep that in mind.

Christian Ehrlicher

It looks like there is a small issue when comparing two QDateTime values in the same timezone but different DST settings - see https://bugreports.qt.io/browse/QTBUG-131491

JonB

"It's one small issue for a man, one giant issue for mankind" ! ;-)
Thanks @Christian-Ehrlicher
@angela2016 In your particular code (vital: datetimes span daylight savings) this should make a 50x improvement when patched :)