pw_containers/docs.rst

.. _module-pw_containers:

-------------
pw_containers
-------------
The ``pw_containers`` module provides embedded-friendly container classes.

pw::Vector
==========
The Vector class is similar to ``std::vector``, except it is backed by a
fixed-size buffer. Vectors must be declared with an explicit maximum size
(e.g. ``Vector<int, 10>``) but vectors can be used and referred to without the
max size template parameter (e.g. ``Vector<int>``).

To allow referring to a ``pw::Vector`` without an explicit maximum size, all
Vector classes inherit from the generic ``Vector<T>``, which stores the maximum
size in a variable. This allows Vectors to be used without having to know
their maximum size at compile time. It also keeps code size small since
function implementations are shared for all maximum sizes.

pw::IntrusiveList
=================
IntrusiveList provides an embedded-friendly singly-linked intrusive list
implementation. An intrusive list is a type of linked list that embeds the
"next" pointer into the list object itself. This allows the construction of a
linked list without the need to dynamically allocate list entries.

In C, an intrusive list can be made by manually including the "next" pointer as
a member of the object's struct. ``pw::IntrusiveList`` uses C++ features to
simplify the process of creating an intrusive list. ``pw::IntrusiveList``
provides a class that list elements can inherit from. This protects the "next"
pointer from being accessed by the item class, so only the ``pw::IntrusiveList``
class can modify the list.

Usage
-----
While the API of ``pw::IntrusiveList`` is similar to a ``std::forward_list``,
there are extra steps to creating objects that can be stored in this data
structure. Objects that will be added to a ``IntrusiveList<T>`` must inherit
from ``IntrusiveList<T>::Item``. They can inherit directly from it or inherit
from it through another base class. When an item is instantiated and added to a
linked list, the pointer to the object is added to the "next" pointer of
whichever object is the current tail.

That means two key things:

 - An instantiated ``IntrusiveList<T>::Item`` must remain in scope for the
   lifetime of the ``IntrusiveList`` it has been added to.
 - A linked list item CANNOT be included in two lists. Attempting to do so
   results in an assert failure.

.. code-block:: cpp

  class Square
     : public pw::IntrusiveList<Square>::Item {
   public:
    Square(unsigned int side_length) : side_length(side_length) {}
    unsigned long Area() { return side_length * side_length; }

   private:
    unsigned int side_length;
  };

  pw::IntrusiveList<Square> squares;

  Square small(1);
  Square large(4000);
  // These elements are not copied into the linked list, the original objects
  // are just chained together and can be accessed via
  // `IntrusiveList<Square> squares`.
  squares.push_back(small);
  squares.push_back(large);

  {
    // When different_scope goes out of scope, it removes itself from the list.
    Square different_scope = Square(5);
    squares.push_back(&different_scope);
  }

  for (const auto& square : squares) {
    PW_LOG_INFO("Found a square with an area of %lu", square.Area());
  }

pw::containers::FlatMap
=======================
FlatMap provides a simple, fixed-size associative array with lookup by key or
value. ``pw::containers::FlatMap`` contains the same methods and features for
looking up data as std::map. However, there are no methods that modify the
underlying data.  The underlying array in ``pw::containers::FlatMap`` does not
need to be sorted. During construction, ``pw::containers::FlatMap`` will
perform a constexpr insertion sort.

Compatibility
=============
* C
* C++17

Dependencies
============
* ``pw_span``