1.. _module-pw_containers: 2 3------------- 4pw_containers 5------------- 6The ``pw_containers`` module provides embedded-friendly container classes. 7 8pw::Vector 9========== 10The Vector class is similar to ``std::vector``, except it is backed by a 11fixed-size buffer. Vectors must be declared with an explicit maximum size 12(e.g. ``Vector<int, 10>``) but vectors can be used and referred to without the 13max size template parameter (e.g. ``Vector<int>``). 14 15To allow referring to a ``pw::Vector`` without an explicit maximum size, all 16Vector classes inherit from the generic ``Vector<T>``, which stores the maximum 17size in a variable. This allows Vectors to be used without having to know 18their maximum size at compile time. It also keeps code size small since 19function implementations are shared for all maximum sizes. 20 21 22pw::IntrusiveList 23================= 24IntrusiveList provides an embedded-friendly singly-linked list implementation. 25An intrusive list is a type of linked list that embeds the "next" pointer into 26the list object itself. This allows the construction of a linked list without 27the need to dynamically allocate list entries to point to the actual in-memory 28objects. In C, an intrusive list can be made by manually including the "next" 29pointer as a member of the object's struct. `pw::IntrusiveList` uses C++ 30features to simplify the process of creating an intrusive list and intrusive 31list objects by providing a class that list elements can inherit from. This 32protects the "next" pointer from being accessed by the actual item that is 33stored in the linked list; only the `pw::IntrusiveList` class can modify the 34list. 35 36 37pw::containers::FlatMap 38======================= 39FlatMap provides a simple, fixed-size associative array with lookup by key or 40value. ``pw::containers::FlatMap`` contains the same methods and features for 41looking up data as std::map. However, there are no methods that modify the 42underlying data. The underlying array in ``pw::containers::FlatMap`` does not 43need to be sorted. During construction, ``pw::containers::FlatMap`` will 44perform a constexpr insertion sort. 45 46 47Usage 48----- 49While the API of `pw::IntrusiveList` is relatively similar to a 50``std::forward_list``, there are extra steps to creating objects that can be 51stored in this data structure. Objects that will be added to a 52``IntrusiveList<T>`` must inherit from ``IntrusiveList<T>::Item``. When an item 53is instantiated and added to a linked list, the pointer to the object is added 54to the "next" pointer of whichever object is the current tail. 55 56 57That means two key things: 58 59 - An instantiated IntrusiveList::Item must remain in scope for the lifetime of 60 the IntrusiveList it has been added to. 61 - A linked list item CANNOT be included in two lists, as it is part of a 62 preexisting list and adding it to another implicitly breaks correctness 63 of the first list. 64 65.. code-block:: cpp 66 67 class Square 68 : public pw::IntrusiveList<Square>::Item { 69 public: 70 Square(unsigned int side_length) : side_length(side_length) {} 71 unsigned long Area() { return side_length * side_length; } 72 73 private: 74 unsigned int side_length; 75 }; 76 77 pw::IntrusiveList<Square> squares; 78 79 Square small(1); 80 Square large(4000); 81 // These elements are not copied into the linked list, the original objects 82 // are just chained together and can be accessed via 83 // `IntrusiveList<Square> squares`. 84 squares.push_back(small); 85 squares.push_back(large); 86 87 { 88 // ERROR: When this goes out of scope, it will break the linked list. 89 Square different_scope = Square(5); 90 squares.push_back(&different_scope); 91 } 92 93 for (auto& square : squares) { 94 PW_LOG_INFO("Found a square with an area of %ul", square.Area()); 95 } 96 97 98Compatibility 99============= 100* C 101* C++17 102 103Dependencies 104============ 105* ``pw_span`` 106