Qt5 container 類別
https://doc.qt.io/qt-5/containers.html
各個 container 類別的簡介：
一般我們使用經常是用 QList，它是最平均最好用的類別。但 QMap 與 QHash 呢？
一般的尋找與插入，QMap 是 O(log n) 而 QHash 是 O(1)。
但在 https://woboq.com/blog/qmap_qhash_benchmark.html 中用 QString 為 key，內容也是 QString 的情況下，發現 Qt5 在 20 個元件以內時，QMap 會比 QHash 尋找的時間快，但我想這會與 QString 的長度有關。
QHash 的部份如果能夠先 reserve 下來元素的數目，那麼在 insert 的時候會是 O(1)，但如果不是，或許最差的情況是 O(n)。而 QMap 縱使不 reserve，最佳與最差的插入複雜度都是 O(log n)
感覺平常使用且元素不是非常多的話 QMap 與 QHash 其實差異並不太大。反而需要在面臨效能瓶頸的時候，再來研究到底使用何者比較實際。
各個 container 類別的簡介：
- QList - 最常用的類別，內部使用陣列實作，所以 index 存取很快
- QLinkedList - 與 QList 很像，除了它使用 iterator 而不是用 index 存取。如果在很大的 list 中間插入，它也提供比 QList 更好的效能
- QVector - 存放記憶體會是連續的，導致由前頭或中間插入都會很慢
- QStack - 便利的 QVector 子類別，提供 lifo 的存取方式
- QQueue - 便利的 QList 子類別，提供 fifo 的存取方式
- QSet
- QMap - key 按照順序排。如果 key 不需要排序，用 QHash 比較快
- QMultiMap
- QHash - 與 QMap 很像，只是它的 key 是不排序的。搜尋來說會比 QMap 快
- QMultiHash
一般我們使用經常是用 QList，它是最平均最好用的類別。但 QMap 與 QHash 呢？
一般的尋找與插入，QMap 是 O(log n) 而 QHash 是 O(1)。
但在 https://woboq.com/blog/qmap_qhash_benchmark.html 中用 QString 為 key，內容也是 QString 的情況下，發現 Qt5 在 20 個元件以內時，QMap 會比 QHash 尋找的時間快，但我想這會與 QString 的長度有關。
QHash 的部份如果能夠先 reserve 下來元素的數目，那麼在 insert 的時候會是 O(1)，但如果不是，或許最差的情況是 O(n)。而 QMap 縱使不 reserve，最佳與最差的插入複雜度都是 O(log n)
感覺平常使用且元素不是非常多的話 QMap 與 QHash 其實差異並不太大。反而需要在面臨效能瓶頸的時候，再來研究到底使用何者比較實際。
留言
張貼留言