0

I would like to know how insert into QSet exactly works. Does QSet compare all items with the new item while inserting? Because if it does, i would use QHash with a simple ID as key instead of using QSet with a container class, which has more complex = operator. In that way, would it faster for QHash to compare while inserting. I'm not sure if i'm thinking right.

mySet.insert(proxy); //1. QSet Insertion 
myHash.insert(id, proxy); //2. QHash Insertion

Which one would be faster?

dce_54
  • 1
  • 1
  • I'm fairly certain that the internal logic of QSet is on public display in its header file, so, if one has any questions about how it works, then perusing the contents of the header file would answer all questions. Have you tried doing that? – Sam Varshavchik May 16 '23 at 13:22
  • 1
    ["Internally, QSet is implemented as a QHash."](https://doc.qt.io/qt-6/qset.html#details) – molbdnilo May 16 '23 at 13:27

1 Answers1

2

The algorithmic complexity of Qt containers is documented here. QSet and QHash have the same complexity for all operations. (Amort. O(1), in the worst case O(n)).

In fact and at least in Qt6, similarities go beyond that; documented in the helppage for QSet:
QSet<T> is one of Qt's generic container classes. It stores values in an unspecified order and provides very fast lookup of the values. Internally, QSet<T> is implemented as a QHash.

I am fairly certain the O complexity will stay the same in future versions of Qt, but the fact that QSet is internally a QHash may not have always been true (I have not checked in Qt5) / may not stay true in the future.

Then, the difference really is only about the template parameters for the 2 classes.

Atmo
  • 2,281
  • 1
  • 2
  • 21