Hi, Habr!
Today I would like to talk about an interesting and useful feature. Her name is the Library of containers. This is not one, but a whole group of useful features. And their purpose - the organization and processing of groups of elements. Sounds interesting, yes? Now let's take a closer look - welcome under cat.
Introduction
I want to say one thing - the article is aimed at novice programmers. We continue.
One of the most common tasks in programming is the organization of processing groups of elements. Programmers with her very much soared. After all, you need to decompose everything on the shelves ... But in Qt there is a wonderful assistant - the Library of containers. This helper is in the QtCore module - so we don’t need any additional inclusions. And so, let's go!
QVector Vector
A vector is a data structure very similar to a regular array. However, using a vector class provides some advantages over a simple array. For example, you can find out the number of elements inside a vector (its size), or dynamically expand it. This container is also more economical than other types of containers. To add elements to the end of a sequential container, you can use the
push_back () method. The elements of the vector can be accessed both through the indexing operator [], and with the help of an iterator. For example:
')
QVector<int> vec; vec.push_back(10);
It will be displayed -
QVector (10,20,30) .
QByteArray byte array
This container is very similar to QVector, but the difference is that it is
not a template class, and it allows storing only elements that are one byte in size. Objects of type QByteArray can be used wherever intermediate data storage is required. The number of array elements can be specified in the constructor, and access to them is obtained using the operator [].
QByteArray arr(3); arr[0] = arr[1] = 0xFF; arr[2] = 0x0;
You can also apply a compress operation and an inverse transform to the data of QByteArray class objects. This is achieved using the two global functions
qCompress () and
qUncompress () . Just compress and expand the data:
QByteArray a = "Some text..."; QByteArray aCompressed = qCompress(a); qDebug << qUncompress(aCompressed);
Some text ... will be displayed.
QBitArray bit array
This class controls the bit (or
boolean ) array. Each of the stored values takes up only one bit, without wasting extra memory. This type is used to store a large number of variables of type
bool .
QBitArray arr(3); arr[0] = arr[1] = true; arr[2] = false;
QList and QLinkedList Lists
A list is a data structure that is an ordered set of related items. The advantage of lists over vectors and queues is that inserting and deleting elements in any position is more efficient, since only the minimum number of pointers is changed to perform these operations, the only exception is inserting an element into the center of the list. But there is a drawback - lists are ill-suited for finding a specific list item by index, and for this purpose it is best to use a vector.
Lists implements the QList template class. In general, this class is an array of pointers to elements.
Specific operations for working with lists:
- move () - Moves an item from one position to another.
- removeFirst () - Removes the first item in the list.
- removeLast () - Removes the last item in the list.
- swap () - Swaps two elements of the list in the specified positions.
- takeAt () - Returns the item at the specified position and removes it from the list.
- takeFirst () - Returns the first item and removes it from the list.
- takeLast () - Returns the last element and removes it from the list.
- toSet () - Returns a QSet container with the data contained in the list.
- toStdList () - Returns the standard STL list std :: List with elements from the list.
- toVector () - Returns a QVector vector with the data contained in the list.
If you are not going to change the values of the elements, then, for efficiency reasons, it is not recommended to use the operator []. Instead, use the
at () method, since it returns a constant element reference.
One of the most common operations is a list traversal for successively obtaining the values of each list item. For example:
QList<int> list; list << 10 << 20 << 30; QValueList<int>::iterator it = list.begin();
The console will display:
Element: 10
Element: 20
Element: 30
If you work with large lists and / or you often need to insert elements, it will be more efficient to use doubly linked
QLinkedList lists. Although this container is gluttonous than a
QList , but the operations of insertion and deletion are reduced to redefining four pointers, regardless of the position of the element being deleted or inserted.
QStack stack
The stack implements a data structure that operates on the principle of Last In First Out - the last to arrive, the first to leave. That is, an element that was inserted later than the rest is removed first from the stack.
The
QStack class is an implementation of the stack structure. This class is inherited from
QVector . The process of putting items on the stack is usually called
pushing , and removing the top element from it is
pushing . Each push operation increases the size of the stack by 1, and each push operation reduces it by 1. For these operations, the
push () and
pop () functions are defined in the
QStack class. The
top () method returns a reference to the top element. Example of using the stack:
QStack<QString> stk; stk.push("Era");
The console will be:
Element: "Gathering"
Element: Corvus Corax
Element: "Era"
QQueue Queue
The queue implements a data structure that operates according to the principle — first come, first go. Implemented a queue in the
QQueue class, which is inherited from
QList .
The following example shows an example of using a queue:
QQueue<QString> que; que.enqueue("Era"); que.enqueue("Corvus Corax"); que.enqueue("Gathering"); while (!que.empty()) { qDebug() << "Element:" << que.dequeue(); }
The console will be:
Element: "Era"
Element: Corvus Corax
Element: "Gathering"
Dictionaries QMap, QMultiMap
Dictionaries, in principle, are similar to ordinary ones used in everyday life. They store items of the same type, indexed by key values. The advantage of the dictionary is that it allows you to quickly get the value associated with a given key. Keys must be unique, with the exception of a multi-dictionary that allows duplicates.
The containers of this type contain elements along with keys, by which they can be found, which can be any type of value. In the case of the
QMap dictionary, it is necessary to ensure that two different elements with the same key are not entered, because then one of these elements cannot be retrieved. Each key must be unique.
When creating a
QMap object, you need to pass its size to the constructor. This size is not, as is customary in other container classes, the size limiting the maximum number of elements, but is the number of positions. The number of positions must be greater than the number of elements expected for storage, otherwise the search for elements in the dictionary will not be carried out efficiently enough. It is desirable that this value belongs to the category of prime numbers, since in this case the placement of elements will be more convenient.
Some methods:
- iowerBound () - Returns to the first element with the given key.
- toStdMap () - Returns an STL dictionary with elements of our dictionary.
- upperBound () - Returns to the last element with the given key.
One of the most common ways to access dictionary elements is to use a key in the operator []. But you can do without it, since the key and value can be obtained through the iterator method
key () and
value () , for example:
QMap<QString,QString> mapPhonebook; mapPhonebook["Piggy"] = "+380 93 785 11 11"; mapPhonebook["Kermit"] = "+7 85 123 65 56"; mapPhonebook["Gonzo"] = "+49 73 631 32 21"; QMap<QString,QString>::iterator it = mapPhonebook.begin(); for(;it != mapPhonebook.end(); ++it) { qDebug() << "Name:" << it.key() << "Phone:" << it.value(); }
The console will be:
Name: Gonzo Phone: +49 73 631 32 21
Name: Kermit Phone: +7 85 123 65 562 21
Name: Piggy Phone: +380 93 785 11 11
QHash and QMultiHash hashes
The hash functionality is very similar to
QMap , with the only difference that instead of sorting by key, this class uses a hash table. This allows it to search for key values much faster than
QMap does.
As in the case of QMap, care must be taken when using the indexing operator [], since specifying a key for which an element does not exist will result in the element being created. Therefore, it is important to always check for the presence of an element bound to the key using the
container's containts () method.
If you intend to place objects of your own classes in
QHash , then you will need to implement the comparison operator == and the specialized function
qHash () for your class. Here is an example of the implementation of the comparison operator:
inline bool operator==(const MyClass& mc1, const MyClass& mc2) { return (mc1.firstName() == mc2.firstName() && mc1.secondName() == mc2.secondName() ); }
The
qHash () function must return a number that must be unique for each element in the hash. For example:
inline uint qHash(const MyClass& mc) { return qHash(mc.firstName()) ^ qHash(mc.secondName()); }
The
QMultiHash class inherits
QHash . It allows you to place values with the same keys and, in general, is similar to
QMultiMap , but takes into account the specifics of its parent class.
QSet set
As the German mathematician Georg Cantor remarked, “Set - this is a lot, mentally implied by us as one”. This single, in the context of Tulip, is nothing more than a
QSet container, which records elements in a certain order and provides an opportunity to very quickly view the values and perform operations with them that are typical of sets, such as union, intersection, and difference. A prerequisite is that the keys must be different. A
QSet container can be used as an unordered list for quick data retrieval.
Operations that can be performed with sets: union, intersection, difference.
Create two sets and write the elements in them:
QSet<QString> set1; QSet<QString> set2; set1 << "Lorem" << "Ipsum" << "Dolor"; set2 << "Sit" << "Amet" << "Lorem";
We perform the operation of combining these two sets, and in order for the elements of the sets to remain unchanged, we introduce the intermediate set
setResult :
QSet<QString> setResult = set1; setResult.unite(set2); qDebug() << " = " << setResult.toList();
The following will appear on the screen:
Association = ("Lorem", "Ipsum", "Dolor", "Sit", "Amet")
In the same way,
intersect () and
subtract () intersect operations are performed.
Results
Today, the reader had to learn how to work with all sorts of Qt containers. Today I told only a small fraction of the whole picture. There are Algorithms, Regular Expressions, QVariant, and much more. Maybe I'll write about them).
Literature
- 1. Max Schlee. Qt 4.5 - Professional C ++ Programming
- 2. Qt Reference Documentation
PS This article is aimed at training novice programmers.