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