{"id":5685,"date":"2019-05-24T07:33:37","date_gmt":"2019-05-24T07:33:37","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/c-core-guidelines-std-array-and-std-vector-are-your-friends\/"},"modified":"2023-06-26T10:10:40","modified_gmt":"2023-06-26T10:10:40","slug":"c-core-guidelines-std-array-and-std-vector-are-your-friends","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/c-core-guidelines-std-array-and-std-vector-are-your-friends\/","title":{"rendered":"C++ Core Guidelines: std::array and std::vector are your Friends"},"content":{"rendered":"

In 99 % of your use cases for a sequential container, you are outstanding with a std::array<\/span> or a std::vector.<\/span> What? If you don’t believe me, read this post.<\/p>\n

<\/p>\n

 \"rules<\/p>\n

Okay, I can make it short today. Here is a rule of thumb: If you want to add elements to your container or remove elements from your container, use a std::vector;<\/span> if not, use a std::array. <\/span><\/strong><\/p>\n

If you are busy, you can stop to read; if not, continue. <\/span><\/p>\n

The Details<\/h2>\n

Here is the reason for the rule of thumb from the guideline: SL.con.2: Prefer using STL vector<\/code> by default, unless you have a reason to use a different container<\/a><\/p>\n

std::array<\/span> and std::vector<\/span> offer the following advantages:<\/p>\n

    \n
  1. the fastest general-purpose access (random access, including being vectorization-friendly);<\/li>\n
  2. the fastest default access pattern (begin-to-end or end-to-begin is prefetcher-friendly);<\/li>\n
  3. the lowest space overhead (contiguous layout has zero per-element overhead, which is cache-friendly).<\/li>\n<\/ol>\n

    I already wrote in my last post C++ Core Guidelines: The Standard Library<\/a>, about the third point. The first point of random access via the index operator is apparent. So, if you don’t like proof by authority, let me talk about the second point. To get the complete picture, here are the sequential containers of the STL.<\/p>\n

     \"sequentialOverview\"<\/p>\n

    You see, we have five sequential containers in the standard template library. Depending on your use case, std::vector<\/span> may be a 95% fit because you must often add or remove elements to your std::vector<\/span>. Let me add a few additional remarks to the table.<\/p>\n

    O(i) stands for an operation’s complexity (runtime). So O(1) means that the runtime of an operation on a container is constant and independent of the container’s size. On opposite to that, O(n) means that the runtime depends linearly on the number of elements of the container. What does that mean for a std::vector <\/span>or a std::array.<\/span> The access time on an element is independent of the size of the std::vector <\/span>or a std::array<\/span>, but the insertion or deletion of an arbitrary element with k-times more elements is k-times slower. Of course, the modification is only possible for a std::vector<\/span>.<\/p>\n

    std::array<\/span> and std::vector<\/span> provide similar access time guarantees, but there is one big difference between them, which many developers ignore. The std::array i<\/span>s typically created on the stack, and the elements of a std::vector<\/span> are created on the heap. This means that a std::array<\/span> can only have a limited number of elements, but a std::vector<\/span> has infinite elements.<\/p>\n

    Although the random access on the elements of a std::vector<\/span> has the same complexity O(1) as the random access on the element of a std::deque<\/span>, that doesn\u2019t mean that both operations are equally fast. I will come to this point later.<\/p>\n

    std::vector<\/span> and std::deque support<\/span> since C++11 the new method shrink_to_fit<\/span>. The number of elements a std::vector<\/span> or a std:.deque<\/span> has (size) is usually smaller than the number of elements for which memory is already reserved (capacity). That is for a simple reason. The size of the std::vector<\/span> or a std::deque<\/span> can increase without an expensive allocation of new memory. The new method shrink_to_fit<\/span> allows it to reduce the capacity of a std::vector<\/span> a std::deque<\/span> to its size. This call is not binding. That means the runtime can ignore it. But on popular platforms, I always observed the desired behavior.<\/p>\n

    The complexity guarantee O(1) for the insertion or deletion into a double (std::list<\/span>) or singly linked list (std::forward_list<\/span>) is only guaranteed if the iterator points to the correct element. std::list and std::forward_list provide an exclusive guarantee, which may sometimes be necessary. When you modify a std::vector or a std::deque, the iterators become invalid. This will not hold for a std::list<\/span> or a std::forward::list<\/span>.<\/p>\n

    You must have an excellent reason to use the very special std::forward_list<\/span> as your sequential container. std::forward_list<\/span> is optimized for memory requirements and performance and is applicable if the insertion, extraction, or movement of elements only affects adjacent elements. The reason for this special behavior is quite apparent. As a singly linked list, std::forward_list<\/span> only supports a forward iterator and doesn’t know its size. This is the reason why you can not use a std::forward_lis<\/span>t ist many algorithms of the STL.<\/p>\n<\/p>\n

    Memory Predictability<\/h2>\n

    I said O(1) for the access time of an element in a std::vector<\/span>, and an element in a std::deque<\/span> does not mean the same. Here is my simple experiment, which I already provided in the post C++ Core Guidelines: The Remaining Rules to Performance<\/a>. This is the reason I make my explanation quite short.<\/p>\n

    If you read an int<\/span> from memory, more than the size of one int<\/span> is read from memory. An entire cache line is read from memory and stored in a cache. On modern architectures, a cache line typically has 64 bytes. If you now request an additional variable from memory and this variable is in the previous cache, the read directly uses this cache, and the operation is much faster.<\/p>\n

    Let’s see what this means for a std::vector, a std::deque, std::list, and std::forward_list<\/span>. I intentionally ignore in my performance test a std::array<\/span> because of its limited size.<\/p>\n

    This was the theory of cache lines. Now I’m curious. Does it make a difference to read and accumulate all elements from std::vector, a std::deque, std::list, and<\/span> std::forward_list<\/span>. The small program should answer.<\/p>\n

    \n
    \/\/ memoryAcess.cpp<\/span>\r\n\r\n#include <forward_list><\/span>\r\n#include <chrono><\/span>\r\n#include <deque><\/span>\r\n#include <iomanip><\/span>\r\n#include <iostream><\/span>\r\n#include <list><\/span>\r\n#include <string><\/span>\r\n#include <vector><\/span>\r\n#include <numeric><\/span>\r\n#include <random><\/span>\r\n\r\nconst<\/span> int<\/span> SIZE =<\/span> 100<\/span>'<\/span>000<\/span>'<\/span>000<\/span>; \r\n\r\ntemplate<\/span> <<\/span>typename<\/span> T><\/span>\r\nvoid<\/span> sumUp(T&<\/span> t, const<\/span> std::<\/span>string&<\/span> cont){            \/\/ (6)<\/span>\r\n  \r\n  std::<\/span>cout <<<\/span> std::<\/span>fixed <<<\/span> std::<\/span>setprecision(10<\/span>);\r\n\r\n  auto<\/span> begin=<\/span> std::<\/span>chrono::<\/span>steady_clock::<\/span>now();\r\n  std::<\/span>size_t<\/span> res =<\/span> std::<\/span>accumulate(t.begin(), t.end(), 0LL<\/span>);\r\n  std::<\/span>chrono::<\/span>duration<<\/span>double<\/span>><\/span> last=<\/span>  std::<\/span>chrono::<\/span>steady_clock::<\/span>now() -<\/span> begin;\r\n  std::<\/span>cout <<<\/span> cont <<<\/span>  std::<\/span>endl;\r\n  std::<\/span>cout <<<\/span> \"time: \"<\/span> <<<\/span> last.count() <<<\/span> std::<\/span>endl;\r\n  std::<\/span>cout <<<\/span> \"res: \"<\/span> <<<\/span> res <<<\/span> std::<\/span>endl;\r\n  std::<\/span>cout <<<\/span> std::<\/span>endl;\r\n \r\n  std::<\/span>cout <<<\/span> std::<\/span>endl;\r\n     \r\n}\r\n\r\nint<\/span> main(){\r\n    \r\n    std::<\/span>cout <<<\/span> std::<\/span>endl;\r\n    \r\n    std::<\/span>random_device seed;                            \/\/ (1)<\/span>\r\n    std::<\/span>mt19937 engine(seed());\r\n    std::<\/span>uniform_int_distribution<<\/span>int<\/span>><\/span> dist(0<\/span>, 100<\/span>);\r\n    std::<\/span>vector<<\/span>int<\/span>><\/span> randNumbers;\r\n    randNumbers.reserve(SIZE);\r\n    for<\/span> (int<\/span> i=<\/span>0<\/span>; i <<\/span> SIZE; ++<\/span>i){\r\n        randNumbers.push_back(dist(engine));\r\n    }\r\n    \r\n    {\r\n      std::<\/span>vector<<\/span>int<\/span>><\/span> myVec(randNumbers.begin(), randNumbers.end());\r\n      sumUp(myVec,\"std::vector<int>\"<\/span>);                 \/\/ (2)<\/span>\r\n    }\r\n\r\n    \r\n    {\r\n      std::<\/span>deque<<\/span>int<\/span>><\/span>myDec(randNumbers.begin(), randNumbers.end());\r\n      sumUp(myDec,\"std::deque<int>\"<\/span>);                 \/\/ (3)<\/span>\r\n    }\r\n    \r\n    {\r\n      std::<\/span>list<<\/span>int<\/span>><\/span>myList(randNumbers.begin(), randNumbers.end());\r\n      sumUp(myList,\"std::list<int>\"<\/span>);                 \/\/ (4)<\/span>\r\n    }\r\n    \r\n    {\r\n      std::<\/span>forward_list<<\/span>int<\/span>><\/span>myForwardList(randNumbers.begin(), randNumbers.end());\r\n      sumUp(myForwardList,\"std::forward_list<int>\"<\/span>);  \/\/ (5)<\/span>\r\n    } \r\n    \r\n}\r\n<\/pre>\n<\/div>\n
     <\/p>\n
    The program memoryAccess.cpp<\/span> creates the first 100 Million random numbers between 0 and 100 (1). Then it accumulates the elements using a std::vector<\/span> (2), a std::deque<\/span> (3), a std::list<\/span> (4), and a std::forward_list<\/span> (5). The actual work is done in the function sumUp (<\/span>6). <\/p>\n
    I compiled the program with maximum optimization and executed it on Linux and Windows. I’m not interested in the comparison between Linux and Windows because that would be a comparison between a desktop PC and a Laptop. I’m interested in the read performance of the four containers. Here it is:\"memoryAccessWin\"<\/p>\n
    \"memoryAccessLinux\"<\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
    To make my performance comparison easy to digest, here is a graphic.<\/p>\n
    \"performaneSequential\"<\/p>\n
    I don’t want to overestimate these performance numbers, but one key observation is obvious. The more cache line aware the container is, the faster the access time of the elements: std::vector > std::deque > (std::list, std::forward_list).<\/strong><\/span><\/p>\n
    What’s next?<\/h2>\n
    I should write a similar post to the associative containers in the standard template library. From my perspective, they are underrepresented in the C++ core guidelines.  My next post<\/a> is about associative containers such as std::map<\/span> and std::unordered_map<\/span>.<\/p>\n
     <\/h2><\/p>\n","protected":false},"excerpt":{"rendered":"
    In 99 % of your use cases for a sequential container, you are outstanding with a std::array or a std::vector. What? If you don’t believe me, read this post.<\/p>\n","protected":false},"author":21,"featured_media":5682,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[372],"tags":[470],"class_list":["post-5685","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-modern-c","tag-performance"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5685","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5685"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5685\/revisions"}],"predecessor-version":[{"id":6787,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5685\/revisions\/6787"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5682"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5685"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5685"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5685"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}