Dave
Assistant Engineer
Assistant Engineer
  • UID627
  • Fans3
  • Follows0
  • Posts55
Reads:3170Replies:0

A quick tutorial of standard library in the C++11 era (2) - overview of STL

Created#
More Posted time:Nov 10, 2016 16:20 PM
Abstract: In the second session, we aim to quickly introduce STL in an all-round way, namely to go over the usage of the 13 types of basic containers and the concepts of the iterator and algorithm. If you are interested, you can use them following the manual. There are still many detailed issues, of course, and we need to spend quite some pages on various details.
STL overview
Before entering the world of STL, we can first have an “aerial view” of its main components. Look at this mind map:


From the figure we can see:
STL only has three core components:
• Container
• Iterator
• Algorithm
Of course, such a huge all-embracing C++ standard library has many other components, such as smart pointers, strings, regular expressions, stream I/O and concurrent processing and other components that are not related to the container. But the container library, the core of C++ standard library, only has the three major components.
The container actually has only a few categories. In general, containers can be divided into the basic container and the special container.
The basic containers are divided into three types, namely unordered containers, ordered containers and sorting containers:
• Ordered containers feature a certain sequence of access, such as the array and linked list, but the elements are not sorted by their values. There are five such containers: the array, the vector dynamic array, the deque dynamic array that enables data inserts at both ends, the two-way linked list, and the one-way linked forward_list.
• Sorting containers feature ordered values after the comparison and sorting algorithms. There are a total of four such containers: the set, the multiset which can have repeated values, the map which features non-repeated key-value pairs, and the multimap which can map repeated key-values. The sorting structure is usually implemented by the Binary Sort Tree structure and so on.
• The unordered containers mean that we don't have to care about the order of the elements. We only care about the whether the elements are placed in the container. The unordered set is the set that we aspire to, as it doesn't require us to sort the elements every time we add some elements. The unordered multiset can accommodate repeated values. The unordered map can be used as the hash table. The unordered multimap can be used as the dictionary.
There are only 13 basic containers as above. Very simple. Compared with Java, STL may fall short in terms of functions. For example, Java has ConcurrentHashMap and CopyOnWriteArrayList sets which boast better support for concurrency and the complexity of these sets are not comparable by these containers. Comparatively, the C++ STL containers are just in the initial stage.
People are all familiar with the iteration mode. The so-called iterator refers to the method for traversing the elements in the container. The simplest usage is like a pointer: use the * operator to get the content, ++ to move to the next item, = to assign a value, and == and != to judge whether the values are equal. The additional begin() and end() are there because the access to containers requires a beginning and an end. The cbegin() and cend() are newly introduced to C++11 and often used for the beginning and end represented by constants.
At last, it is the various algorithms, from tiny algorithms for count and value assignment to big algorithms for sorting all elements. There seem to be many algorithms, but they are all useful for container operations. So in this sense, there are not many.
Container overview
The array container is just an array.
The array container is a new member of the STL family starting from TR1. In essence, it is an array. It does not support adding new members, but only supports modifying the values of the existing members. C++11 empowers the array container with the support of uniform initiation. Let's look at an example:
std::array<std::string, 5> sequence_container = {"array","vector","deque","list","forward_list"};
    std::cout<<"Sequence containers are:";
    for(int i=0;i<sequence_container.size();i++){
        std::cout<<sequence_container<<",";
    }
    std::cout<<std::endl;


Like an array, the array container is accessed through the [] operator.
Next, we can bring the iterator onto the stage and take a look at how to traverse the array container using the iterator:
std::cout<<"2.Sequence containers are:";
    for(auto pos = sequence_container.begin();pos!=sequence_container.end();++pos){
        std::cout<<*pos<<",";
    }
    std::cout<<std::endl;


The first element is array.begin(), and the last element is array.end(). The ++ operator is used to get the next element. The auto keyword feature of C++11 plays its strength at this time. With this feature, we don't even need to know the existence of the iterator. Whatever it is, we can just use ++ to get the next element, and use * to get the current value. They should be enough for use in general cases.
Next, C++11 presents us another small gift: simple writing. Let's look at the example:
std::cout<<"3.Sequence containers are:";
    for(auto elem : sequence_container){
        std::cout<<elem<<",";
    }
    std::cout<<std::endl;


You are right. The iteration functions such as begin() and end() and operators such as ++ and * are also encapsulated. What we get is already an element, and in this case, a string.
Then we can apply the algorithm to the array container to sort the container:
sort(sequence_container.begin(),sequence_container.end());
    std::cout<<"4.After sorting,Sequence containers are:";
    for(auto elem : sequence_container){
        std::cout<<elem<<",";
    }
    std::cout<<std::endl;


The output result is sorted, as follows:
3.Sequence containers are:array,vector,deque,list,forward_list,
4.After sorting,Sequence containers are:array,deque,forward_list,list,vector,


Backward-increment dynamic array: vector
Enduring the fix-sized arrays, the backward-expanding array vector is here!
The feature of vector is that the performance of adding elements in the rear, that is, the push_back function, is good. But the performance of adding elements in the front and the middle will cause the elements following to move backward.
Let's look at an example of push_back:
std::vector<std::string> vector_seq_container;
    vector_seq_container.push_back("array");
    vector_seq_container.push_back("vector");
    vector_seq_container.push_back("deque");
    vector_seq_container.push_back("list");
    vector_seq_container.push_back("forward_list");


The usage of the iterator and algorithm is identical with that of the array:
std::cout<<"5.Sequence containers are:";
    for(auto elem : vector_seq_container){
        std::cout<<elem<<",";
    }
    std::cout<<std::endl;
    
    sort(vector_seq_container.begin(),vector_seq_container.end());
    std::cout<<"6.After sorting,Sequence containers are:";
    for(auto elem : vector_seq_container){
        std::cout<<elem<<",";
    }
    std::cout<<std::endl;


Deque: deque
The deque supports both push_back of elements and push_front of elements.
std::deque<std::string> deque_seq_container;
    deque_seq_container.push_front("array");
    deque_seq_container.push_back("vector");
    deque_seq_container.push_front("deque");
    deque_seq_container.push_back("list");
    deque_seq_container.push_front("forward_list");


The usage of the iterator and algorithm is also identical with that of the array and the vector.
Two-way linked list
The list is more powerful. It not only supports push_back and push_front, but also supports inserts in the middle, that is, you can insert an element before a place of the iterator.
One-way linked list - forward list
On the contrary, the capacity of the one-way linked list forward list is limited compared with the list. It only supports push-front, and does not support push-back. So there is no push_back function in the forward list.
Set and unordered_set
The set is usually implemented through the red-black tree.
The ordered structure is not a structure for storing the sequence, so the push_back or similar functions do not make sense. An insert operation is enough for use.
While the unordered_set is usually implemented through the hash table.
But once the element values of the set are put in it, the values cannot be modified directly, or else the sequence will be damaged.
Let's look at an example:
std::set<std::string> sorted_container;
    sorted_container.insert("set");
    sorted_container.insert("multiset");
    sorted_container.insert("map");
    sorted_container.insert("multimap");
    for(auto elem : sorted_container){
        std::cout<<elem<<",";
    }
    std::cout<<std::endl;

    std::unordered_set<std::string> unordered_container;
    unordered_container.insert("set");
    unordered_container.insert("multiset");
    unordered_container.insert("map");
    unordered_container.insert("multimap");
    for(auto elem : unordered_container){
        std::cout<<elem<<",";
    }
    std::cout<<std::endl;


The output is like this:
map,multimap,multiset,set,
multimap,multiset,map,set,


From the output above, we can see that the set is strictly sorted in the alphabetic order. While the unordered_set is not that well-groomed, and the map is even placed after the multiset.
Multiset that supports repeated elements, and unordered_multiset
The elements can be repeated in a multiset. It is basically the same with set in other aspects.
Sort tree map and hash table unordered_map
They are actually similar to the set, only the elements are changed to std::pair.
Let's look at an example:
std::map<int,std::string> map_container;
    map_container.insert(std::make_pair(4,"set"));
    map_container.insert(std::make_pair(1,"multiset"));
    map_container.insert(std::make_pair(2,"map"));
    map_container.insert(std::make_pair(3,"multimap"));
    for(auto elem : map_container){
        std::cout<<elem.first<<":"<<elem.second<<",";
    }
    std::cout<<std::endl;

    std::unordered_map<int,std::string> umap_container;
    umap_container.insert(std::make_pair(4,"set"));
    umap_container.insert(std::make_pair(1,"multiset"));
    umap_container.insert(std::make_pair(2,"map"));
    umap_container.insert(std::make_pair(3,"multimap"));
    for(auto elem : umap_container){
        std::cout<<elem.first<<":"<<elem.second<<",";
    }
    std::cout<<std::endl;


The output is as follows:
1:multiset,2:map,3:multimap,4:set,
3:multimap,2:map,1:multiset,4:set,


The map is strictly sorted by the key value, while the unordered_map hash table is not that rigorous of course.
Multimap sorting tree that supports repeated keys
Sorting tree for repeated values and hash table. I will not talk about it more here.
Summary
Within such a short article, we actually have completed the introduction to the main containers in STL. You may also have experienced the role of the iterator and algorithm. So you should be confident that we can complete the tutorial for the entire C++ standard library.
Common containers:
1. vector: Extended array that adds new elements with push_back.
2. list: Two-way linked list. It supports push_back, push_front and insert operations.
3. unordered_set: A set. It supports element inserts.
4. unordered_map: A hash table. It supports inserts of std::pair.
If you need sorting, you can use the set or map.
If you need to operate on both ends of the container, you can use deque. It supports push_back and push_front, but does not support insert.
If you need repeated elements, you can remember that the set and map both have a version for repeated elements.
C++11 provides the improved for loop which can better wrap the iterator.
The algorithm is a universal tool for operations on the container.
At last, I want to quickly add the idea of algorithms. It is opposite to the idea of object-oriented programming (OOP). The idea of OOP is to encapsulate the attributes and functions of an object together to form an object. But the idea of the algorithm is irrelevant with the container object. It abstracts the universal operations.
Okay. Let's call it an end for today.
Guest