C++ STL and Qt container comparison

〇、Preface

  • In daily development, it is often necessary to use some data structures to store data. In pure C++ development, you only need to choose the appropriate data structure according to your needs. But for the Qt/C++ mixed scenario, which data structure to choose becomes a problem, so in order to solve this doubt, I wrote a blog post to compare the differences between the two in detail for future reference.

1. Data structure comparison

1.1, QCache and QContiguousCache

  • When developing a graphical interface, a problem that cannot be ignored is memory optimization. For example, how to load a large number of lists, an obvious optimization idea is to only display the data that the user can see, and reclaim the memory in time if it exceeds the display area.
  • Then, based on such requirements, QCache came into being. It provides a memory management method based on key-value pairs. When an element is added, QCache will automatically obtain its memory management permission, and when needed Automatically release them to make room for newly inserted objects, the template prototype is as follows:
template <class Key, class T>
class QCache
  • As the name suggests, QContiguousCache is a continuous cache space, that is, the elements in the cache are continuous. This has the advantage of consuming less memory and processor cycles than QCache.

1.2, deque and QList

  • One of the advantages of deque lies in efficient header insertion and tail insertion. Its internal implementation mechanism is to use multiple consecutive arrays to “piece together” to create the illusion of continuous memory space as a whole, thereby providing random subscript access to the outside world.
  • Qt does not provide a double-ended queue type, but there is a data structure QList that implements similar functions, and it also has efficient head insertion and tail insertion operations. The Qt official website documentation also suggests that QList should be the default first choice.

1.3, QList, QVector, QLinkedList

  • It should be noted that QList is actually not a linked list, but an optimized vector. The official description is an array list. Its storage method is to allocate continuous nodes, and the data members of each node are not larger than the size of a pointer, so for basic types such as int and char, it is directly stored (so according to memory alignment, memory consumption should be greater), For types such as Class and Struct, it is a storage object pointer.

  • The implementation mode of QList mainly has the advantage of fast insertion. Because its element size will not exceed sizeof(void*), you only need to move the pointer when inserting, instead of moving the object like vector. Moreover, since QList stores void*, it can be expanded directly with realloc() simply and rudely.

  • The growth strategy of QList is two-way growth, so the support for prepend is much better than vector, and the flexibility of use is higher than that of Vector and LinkedList. The disadvantage is that every time an object is stored, a Node object needs to be constructed, which brings additional heap overhead.

  • The complexity comparison given by the official document is as follows:

Interpretation Qt C++ STL
String QString string
Double linked list that encapsulates the index QList ×
Double Linked List QLinkedList list
Dynamic Array QVector vector
Stack QStack stack
queue QQueue queue
double-ended queue × deque
priority queue × priority_queue priority_queue priority_queue td>
Set QSet set
dictionary/map QMap map
Key-value repeatable dictionary/map QMultiMap multimap
Hash dictionary/map QHash unordered_map
Key value Repeatable Hash Dictionary/Map QMultiHash unordered_multimap
Cache QCache ×
Continuous Cache QContiguousCache ×
Index lookup Insertion Prepending Appending
QLinkedList O(n) O(1) O(1) O(1)
QList O(1) O(n) Amort. O(1) Amort. O(1)
QVector O(1) O(n) O(n) Amort. O(1)

2. Implementation method

  • Qt’s container is based on C++’s pure template and inheritance implementation. For example, for the two data structures of queue and stack, they are actually based on QList and QVector. Doing so can greatly simplify the code, but it also means more coupling.
class QQueue : public QList<T>
class QStack : public QVector<T>
  • A simple example is that when using QStack, both ends can even be popped up at the same time, which obviously does not conform to the design concept of the stack as a data structure first in last out.
QStack<int>s;
s. pop_front();
s. pop_back();
  • At this point, the design of STL is more reasonable. It is also the inheritance of queue and stack. The source code of STL is as follows:
template<class_Ty,
class _Container = deque<_Ty>>
class queue
{ // FIFO queue implemented with a container
        void push(const value_type & _Val)
{ // insert element at beginning
c.push_back(_Val);
}

void pop()
{ // erase element at end
c. pop_front();
}
    protected:
_Container c; // the underlying container
};

template<class_Ty,
class _Container = deque<_Ty>>
class stack
{ // LIFO queue implemented with a container
        void push(const value_type & _Val)
{ // insert element at end
c.push_back(_Val);
}

void pop()
{ // erase last element
c. pop_back();
}
    protected:
_Container c; // the underlying container
};
  • It can be seen that another template _Container is actually used as a member variable inside the corresponding container, and the external interfaces are all encapsulated products. This not only guarantees the rationality of the data structure, but also provides the internal container as a template parameter, which can more flexibly adapt to various needs.
std::stack<int, std::vector<int> > ss;
ss. pop();

3. Interface functionality

  • At the level of the external interface, Qt’s container can be said to be full of STL. Qt’s interface is not only fully functional, but also provides many types of conversion interfaces.
  • For example, the list of all keys or values can be obtained through the following interface. Although the internal logic is simple creation + copy, it provides great convenience for users.
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T & amp;avalue, const Key & amp;defaultKey) const
{
    const_iterator i = begin();
    while (i != end()) {
        if (i. value() == avalue)
            return i.key();
         + + i;
    }

    return defaultKey;
}

template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
{
    QList<T> res;
    res.reserve(size());
    const_iterator i = begin();
    while (i != end()) {
        res.append(i.value());
         + + i;
    }
    return res;
}
  • But at the same time, because of the powerful functionality of the Qt interface, many non-standard writing methods are born. The more typical writing methods are as follows. First query once and then obtain the subscript. In fact, it can be judged directly by the return value of indexOf.
/* Contains and indexOf of QList are used together */
if (calibSavedList_.contains(pSelectedButton) & amp; & amp; i == calibSavedList_.indexOf(pSelectedButton))
  • Compared with the completeness of the Qt container interface, C++ does not provide many highly complex interfaces due to the cleanliness requirements of performance, such as the insertion and popping of header data.

4. Iterator access method

  • Both support iterator access methods, but Qt provides two styles of iterators, Java and STL.
  • java style
Containers Read-only iterator Read-write iterator
QList, QQueue QListIterator QMutableListIterator
QLinkedList QLinkedListIterator QMutableLinkedListIterator
QVector, QStack QVectorIterator QMutableVectorIterator
QSet QSetIterator QMutableSetIterator
QMap, QMultiMap QMapIterator QMutableMapIterator
QHash, QMultiHash QHashIterator QMutableHashIterator
  • STL style
Containers Read-only iterator Read-write iterator
QList, QQueue QList::const_iterator QList::iterator
QLinkedList QLinkedList::const_iterator QLinkedList::iterator
QVector, QStack QVector::const_iterator QVector::iterator
QSet QSet::const_iterator QSet::iterator
QMap, QMultiMap QMap::const_iterator QMap ::iterator
QHash, QMultiHash QHash::const_iterator QHash::iterator

5. Conclusion

  • Referring to the test conclusions in blog post ① and blog post ②, in general, the efficiency of Qt containers is similar to that of C ++ STL containers. So the performance considerations are almost negligible.

  • In the case of caring about the encapsulation of data structures, use the containers in C++ STL.

  • When concerned with specific demand scenarios, the containers in STL are more comprehensive (such as priority queues, red-black tree collections that maintain order)

  • When concerned about the scalability and ease of use of the interface of the data structure itself, the Qt container is used.

  • When you need to use Qt’s linear container, unless there is a need for frequent insertion in the middle of the list (QLinkedList is selected at this time), otherwise it is generally brainless to choose QList.

6. Reference

QList Class | Qt Core 5.15.10

Sequential containers in Qt: QList, QVector – Zhihu (zhihu.com)

Qt container class – 1. QList class, QLinkedList class and QVector class – Zero Excuse – 博客园 (cnblogs.com)

Introduction to STL (Standard Template Library) of C ++

Performance characteristic test series 1 – STL container, QT container performance comparison and summary