Chapter 04 Containers

    1. Why introduce std::array instead of std::vector directly?
    2. Already have a traditional array, why use std::array?

    First answer the first question. Unlike std::vector, the size of the std::array object is fixed. If the container size is fixed, then the std::array container can be used first. In addition, since std::vector is automatically expanded, when a large amount of data is stored, and the container is deleted, The container does not automatically return the corresponding memory of the deleted element. In this case, you need to manually run shrink_to_fit() to release this part of the memory.

    The second problem is much simpler. Using std::array can make the code more “modern” and encapsulate some manipulation functions, such as getting the array size and checking if it is not empty, and also using the standard friendly. Container algorithms in the library, such as std::sort.

    Using std::array is as simple as specifying its type and size:

    1. std::array<int, 4> arr = {1, 2, 3, 4};
    3. arr.empty(); // check if container is empty
    4. arr.size();  // return the size of the container
    6. // iterator support
    7. for (auto &i : arr)
    8. {
    9.     // ...
    10. }
    12. // use lambda expression for sort
    13. std::sort(arr.begin(), arr.end(), [](int a, int b) {
    14.     return b < a;
    15. });
    17. // array size must be constexpr
    18. constexpr int len = 4;
    19. std::array<int, len> arr = {1, 2, 3, 4};
    21. // illegal, different than C-style array, std::array will not deduce to T*
    22. // int *arr_p = arr;

    When we started using std::array, it was inevitable that we would encounter a C-style compatible interface. There are three ways to do this:

    1. void foo(int *p, int len) {
    2.     return;
    3. }
    5. std::array<int, 4> arr = {1,2,3,4};
    7. // C-stype parameter passing
    8. foo(&arr[0], arr.size());
    9. foo(arr.data(), arr.size());
    11. // use `std::sort`
    12. std::sort(arr.begin(), arr.end());

    std::forward_list is a list container, and the usage is basically similar to std::list, so we don’t spend a lot of time introducing it.

    Need to know is that, unlike the implementation of the doubly linked list of std::list, is implemented using a singly linked list. Provides element insertion of O(1) complexity, does not support fast random access (this is also a feature of linked lists), It is also the only container in the standard library container that does not provide the size() method. Has a higher space utilization than std::list when bidirectional iteration is not required.

    We are already familiar with the ordered container std::map/std::set in traditional C++. These elements are internally implemented by red-black trees. The average complexity of inserts and searches is O(log(size)). When inserting an element, the element size is compared according to the < operator and the element is determined to be the same. And select the appropriate location to insert into the container. When traversing the elements in this container, the output will be traversed one by one in the order of the < operator.

    C++11 introduces two sets of unordered containers: std::unordered_map/std::unordered_multimap and std::unordered_set/std::unordered_multiset.

    Their usage is basically similar to the original std::map/std::multimap/std::set/set::multiset Since these containers are already familiar to us, we will not compare them one by one. Let’s compare std::map and std::unordered_map directly:

    1. #include <iostream>
    2. #include <string>
    3. #include <unordered_map>
    4. #include <map>
    6. int main() {
    7.     // initialized in same order
    8.     std::unordered_map<int, std::string> u = {
    9.         {1, "1"},
    10.         {3, "3"},
    11.         {2, "2"}
    12.     };
    13.     std::map<int, std::string> v = {
    14.         {1, "1"},
    15.         {3, "3"},
    16.         {2, "2"}
    17.     };
    19.     // iterates in the same way
    20.     std::cout << "std::unordered_map" << std::endl;
    21.     for( const auto & n : u)
    22.         std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
    24.     std::cout << std::endl;
    25.     std::cout << "std::map" << std::endl;
    26.     for( const auto & n : v)
    27.         std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
    28. }

    The final output is:

    Programmers who have known Python should be aware of the concept of tuples. Looking at the containers in traditional C++, except for std::pair There seems to be no ready-made structure to store different types of data (usually we will define the structure ourselves). But the flaw of std::pair is obvious, only two elements can be saved.

    There are three core functions for the use of tuples:

    1. std::make_tuple: construct tuple
    2. std::get: Get the value of a position in the tuple
    3. std::tie: tuple unpacking
    1. #include <tuple>
    4. auto get_student(int id) {
    5.     if (id == 0)
    6.     if (id == 1)
    7.         return std::make_tuple(2.9, 'C', "Jack");
    8.     if (id == 2)
    9.         return std::make_tuple(1.7, 'D', "Ive");
    11.     // it is not allowed to return 0 directly
    12.     // return type is std::tuple<double, char, std::string>
    13.     return std::make_tuple(0.0, 'D', "null");
    14. }
    16. int main() {
    17.     auto student = get_student(0);
    18.     std::cout << "ID: 0, "
    19.               << "GPA: "   << std::get<0>(student) << ", "
    20.               << "Grade: " << std::get<1>(student) << ", "
    21.               << "Name: "  << std::get<2>(student) << '\n';
    23.     double gpa;
    24.     char grade;
    25.     std::string name;
    27.     // unpack tuples
    28.     std::tie(gpa, grade, name) = get_student(1);
    29.     std::cout << "ID: 1, "
    30.               << "GPA: "   << gpa << ", "
    31.               << "Grade: " << grade << ", "
    32.               << "Name: "  << name << '\n';
    33. }

    std::get In addition to using constants to get tuple objects, C++14 adds usage types to get objects in tuples:

    1. std::tuple<std::string, double, double, int> t("123", 4.5, 6.7, 8);
    2. std::cout << std::get<std::string>(t) << std::endl;
    3. std::cout << std::get<double>(t) << std::endl; // illegal, runtime error
    4. std::cout << std::get<3>(t) << std::endl;

    If you think about it, you might find the problem with the above code. std::get<> depends on a compile-time constant, so the following is not legal:

    1. int index = 1;
    2. std::get<index>(t);

    So we can:

    1. int i = 1;
    2. std::cout << tuple_index(t, i) << std::endl;

    Another common requirement is to merge two tuples, which can be done with std::tuple_cat:

    1. auto new_tuple = std::tuple_cat(get_student(1), std::move(t));

    You can immediately see how quickly you can traverse a tuple? But we just introduced how to index a tuple by a very number at runtime, then the traversal becomes simpler. First we need to know the length of a tuple, which can:

    1. template <typename T>
    2. auto tuple_len(T &tpl) {
    3.     return std::tuple_size<T>::value;
    4. }

    This will iterate over the tuple:

    This chapter briefly introduces the new containers in modern C++. Their usage is similar to that of the existing containers in C++. It is relatively simple, and you can choose the containers you need to use according to the actual scene, so as to get better performance.

    Although std::tuple is effective, the standard library provides limited functionality and there is no way to meet the requirements of runtime indexing and iteration. Fortunately, we have other methods that we can implement on our own.

    | Previous Chapter |