〇、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
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 |
QMapIterator |
QMutableMapIterator |
QHash |
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 |
QMap |
QMap |
QHash |
QHash |
QHash |
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