pw_containers/docs.rst - pigweed/pigweed - Git at Google

 .. _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::InlineDeque
 ---------------
 .. doxygentypedef:: pw::InlineDeque

 ---------------
 pw::InlineQueue
 ---------------
 .. doxygentypedef:: pw::InlineQueue

 --------------------------
 pw::InlineVarLenEntryQueue
 --------------------------
 .. doxygenfile:: pw_containers/inline_var_len_entry_queue.h
    :sections: detaileddescription

 Example
 =======
 .. tab-set::

    .. tab-item:: C++
       :sync: c++

       Queues are declared with their max size
       (``InlineVarLenEntryQueue<kMaxSize>``) but may be used without
       specifying the size (``InlineVarLenEntryQueue<>&``).

       .. code-block:: c++

          // Declare a queue with capacity sufficient for one 10-byte entry or
          // multiple smaller entries.
          pw::InlineVarLenEntryQueue<10> queue;

          // Push an entry, asserting if the entry does not fit.
          queue.push(queue, data)

          // Use push_overwrite() to push entries, overwriting older entries
          // as needed.
          queue.push_overwrite(queue, more_data)

          // Remove an entry.
          queue.pop();

       Alternately, a ``InlineVarLenEntryQueue`` may be initialized in an
       existing ``uint32_t`` array.

       .. code-block:: c++

          // Initialize a InlineVarLenEntryQueue.
          uint32_t buffer[32];
          auto& queue = pw::InlineVarLenEntryQueue<>::Init(buffer);

          // Largest supported entry is 114 B (13 B overhead + 1 B prefix)
          assert(queue.max_size_bytes() == 114u);

          // Write data
          queue.push_overwrite(data);

    .. tab-item:: C
       :sync: c

       A ``InlineVarLenEntryQueue`` may be declared and initialized in C with the
       :c:macro:`PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE` macro.

       .. code-block:: c

          // Declare a queue with capacity sufficient for one 10-byte entry or
          // multiple smaller entries.
          PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(queue, 10);

          // Push an entry, asserting if the entry does not fit.
          pw_InlineVarLenEntryQueue_Push(queue, "12345", 5);

          // Use push_overwrite() to push entries, overwriting older entries
          // as needed.
          pw_InlineVarLenEntryQueue_PushOverwrite(queue, "abcdefg", 7);

          // Remove an entry.
          pw_InlineVarLenEntryQueue_Pop(queue);

       Alternately, a ``InlineVarLenEntryQueue`` may be initialized in an
       existing ``uint32_t`` array.

       .. code-block:: c

          // Initialize a InlineVarLenEntryQueue.
          uint32_t buffer[32];
          pw_InlineVarLenEntryQueue_Init(buffer, 32);

          // Largest supported entry is 114 B (13 B overhead + 1 B prefix)
          assert(pw_InlineVarLenEntryQueue_MaxSizeBytes(buffer) == 114u);

          // Write some data
          pw_InlineVarLenEntryQueue_PushOverwrite(buffer, "123", 3);

 Queue vs. deque
 ===============
 This module provides :cpp:type:`InlineVarLenEntryQueue`, but no corresponding
 ``InlineVarLenEntryDeque`` class. Following the C++ Standard Library style,
 the deque class would provide ``push_front()`` and ``pop_back()`` operations in
 addition to ``push_back()`` and ``pop_front()`` (equivalent to a queue's
 ``push()`` and ``pop()``).

 There is no ``InlineVarLenEntryDeque`` class because there is no efficient way
 to implement ``push_front()`` and ``pop_back()``. These operations would
 necessarily be O(n), since each entry knows the position of the next entry, but
 not the previous, as in a single-linked list. Given that these operations would
 be inefficient and unlikely to be used, they are not implemented, and only a
 queue class is provided.

 API Reference
 =============
 C++
 ---
 .. doxygengroup:: inline_var_len_entry_queue_cpp_api
    :content-only:
    :members:

 C
 -
 .. doxygengroup:: inline_var_len_entry_queue_c_api
    :content-only:

 Python
 ------
 .. automodule:: pw_containers.inline_var_len_entry_queue
    :members:

 -----------------
 pw::IntrusiveList
 -----------------
 ``pw::IntrusiveForwardList`` and ``pw::IntrusiveList`` provide embedded-friendly
 singly- and doubly-linked intrusive list implementations, respectively. An
 intrusive list is a type of linked list that embeds list metadata, such as a
 "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::IntrusiveForwardList`` and
 ``pw::IntrusiveList`` uses C++ features to simplify the process of creating an
 intrusive list. They provide classes that list elements can inherit from,
 protecting the list metadata from being accessed by the item class.

 API Reference
 =============
 IntrusiveForwardList
 --------------------
 This class is similar to ``std::forward_list<T>``, except that the type of items
 to be added must derive from ``pw::IntrusiveForwardList<T>::Item``.

 .. doxygenclass:: pw::IntrusiveForwardList
    :members:

 IntrusiveList
 -------------
 This class is similar to ``std::list<T>``, except that the type of items to be
 added must derive from ``pw::IntrusiveList<T>::Item``.

 .. doxygenclass:: pw::containers::future::IntrusiveList
    :members:

 .. note::
    Originally, ``pw::IntrusiveList<T>`` was implemented as a singly-linked list.
    To facilitate migration to ``pw::IntrusiveForwardList<T>::Item``, this
    original implementation can still be temporarily used by enabling the
    ``PW_CONTAINERS_USE_LEGACY_INTRUSIVE_LIST`` module configuration option.

 Example
 =======
 .. code-block:: cpp

    class Square
       : public pw::IntrusiveForwardList<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::IntrusiveForwardList<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
    // `IntrusiveForwardList<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());
    }

    // Like std::forward_list, an iterator is invalidated when the item it refers
    // to is removed. It is *NOT* safe to remove items from a list while iterating
    // over it in a range-based for loop.
    for (const auto& square_bad_example : squares) {
      if (square_bad_example.verticies() != 4) {
        // BAD EXAMPLE of how to remove matching items from a singly linked list.
        squares.remove(square_bad_example);  // NEVER DO THIS! THIS IS A BUG!
      }
    }

    // To remove items while iterating, use an iterator to the previous item.
    auto previous = squares.before_begin();
    auto current = squares.begin();

    while (current != squares.end()) {
      if (current->verticies() != 4) {
        current = squares.erase_after(previous);
      } else {
        previous = current;
        ++current;
      }
    }

 Performance Considerations
 ==========================
 Items only include pointers to the next item. To reach previous items, the list
 maintains a cycle of items so that the first item can be reached from the last.
 This structure means certain operations have linear complexity in terms of the
 number of items in the list, i.e. they are "O(n)":

 - Adding to the end of a list with ``pw::IntrusiveList<T>::push_back(T&)``.
 - Accessing the last item in a list with ``pw::IntrusiveList<T>::back()``.
 - Destroying an item with ``pw::IntrusiveList<T>::Item::~Item()``.
 - Moving an item with either ``pw::IntrusiveList<T>::Item::Item(Item&&)`` or
   ``pw::IntrusiveList<T>::Item::operator=(Item&&)``.
 - Removing an item from a list using ``pw::IntrusiveList<T>::remove(const T&)``.
 - Getting the list size using ``pw::IntrusiveList<T>::size()``.

 When using a ``pw::IntrusiveList<T>`` in a performance critical section or with
 many items, authors should prefer to avoid these methods. For example, it may be
 preferrable to create items that together with their storage outlive the list.

 Notably, ``pw::IntrusiveList<T>::end()`` is constant complexity (i.e. "O(1)").
 As a result iterating over a list does not incur an additional penalty.

 Size report
 ===========
 .. include:: intrusive_list_size_report

 -----------------------
 pw::containers::FlatMap
 -----------------------
 ``FlatMap`` provides a simple, fixed-size associative array with `O`\ (log `n`)
 lookup by key.

 ``pw::containers::FlatMap`` contains the same methods and features for looking
 up data as ``std::map``. However, modification of the underlying data is limited
 to the mapped values, via ``.at()`` (key must exist) and ``mapped_iterator``
 objects returned by ``.mapped_begin()`` and ``.mapped_end()``.
 ``mapped_iterator`` objects are bidirectional iterators that can be dereferenced
 to access and mutate the mapped value objects.

 The underlying array in ``pw::containers::FlatMap`` does not need to be sorted.
 During construction, ``pw::containers::FlatMap`` will perform a constexpr
 insertion sort.

 To create a ``FlatMap``, there are some options. The following example defines
 a ``FlatMap`` with two items.

 .. code-block:: cpp

    // Initiates by a std::array of Pair<K, V> objects.
    FlatMap<int, char, 2> map({{
        {1, 'a'},
        {-3, 'b'},
    }});

    FlatMap map(std::array{
        Pair<int, char>{1, 'a'},
        Pair<int, char>{-3, 'b'},
    });

    // Initiates by Pair<K, V> objects.
    FlatMap map = {
        Pair<int, char>{1, 'a'},
        Pair<int, char>{-3, 'b'},
    };

 ----------------------------
 pw::containers::FilteredView
 ----------------------------
 .. doxygenclass:: pw::containers::FilteredView

 -------------------------------
 pw::containers::WrappedIterator
 -------------------------------
 ``pw::containers::WrappedIterator`` is a class that makes it easy to wrap an
 existing iterator type. It reduces boilerplate by providing ``operator++``,
 ``operator--``, ``operator==``, ``operator!=``, and the standard iterator
 aliases (``difference_type``, ``value_type``, etc.). It does not provide the
 dereference operator; that must be supplied by a derived class.

 To use it, create a class that derives from ``WrappedIterator`` and define
 ``operator*()`` and ``operator->()`` as appropriate. The new iterator might
 apply a transformation to or access a member of the values provided by the
 original iterator. The following example defines an iterator that multiplies the
 values in an array by 2.

 .. code-block:: cpp

    // Divides values in a std::array by two.
    class DoubleIterator
        : public pw::containers::WrappedIterator<DoubleIterator, const int*, int> {
     public:
      constexpr DoubleIterator(const int* it) : WrappedIterator(it) {}

      int operator*() const { return value() * 2; }

      // Don't define operator-> since this iterator returns by value.
    };

    constexpr std::array<int, 6> kArray{0, 1, 2, 3, 4, 5};

    void SomeFunction {
      for (DoubleIterator it(kArray.begin()); it != DoubleIterator(kArray.end()); ++it) {
        // The iterator yields 0, 2, 4, 6, 8, 10 instead of the original values.
      }
    };

 ``WrappedIterator`` may be used in concert with ``FilteredView`` to create a
 view that iterates over a matching values in a container and applies a
 transformation to the values. For example, it could be used with
 ``FilteredView`` to filter a list of packets and yield only one field from the
 packet.

 The combination of ``FilteredView`` and ``WrappedIterator`` provides some basic
 functional programming features similar to (though much more cumbersome than)
 `generator expressions <https://www.python.org/dev/peps/pep-0289/>`_ (or `filter
 <https://docs.python.org/3/library/functions.html#filter>`_/`map
 <https://docs.python.org/3/library/functions.html#map>`_) in Python or streams
 in Java 8. ``WrappedIterator`` and ``FilteredView`` require no memory
 allocation, which is helpful when memory is too constrained to process the items
 into a new container.

 ------------------------
 pw::containers::to_array
 ------------------------
 ``pw::containers::to_array`` is a C++14-compatible implementation of C++20's
 `std::to_array <https://en.cppreference.com/w/cpp/container/array/to_array>`_.
 In C++20, it is an alias for ``std::to_array``. It converts a C array to a
 ``std::array``.

 -------------------------
 pw_containers/algorithm.h
 -------------------------
 Pigweed provides a set of Container-based versions of algorithmic functions
 within the C++ standard library, based on a subset of
 ``absl/algorithm/container.h``.

 .. cpp:function:: bool pw::containers::AllOf()

    Container-based version of the <algorithm> ``std::all_of()`` function to
    test if all elements within a container satisfy a condition.

 .. cpp:function:: bool pw::containers::AnyOf()

    Container-based version of the <algorithm> ``std::any_of()`` function to
    test if any element in a container fulfills a condition.

 .. cpp:function:: bool pw::containers::NoneOf()

    Container-based version of the <algorithm> ``std::none_of()`` function to
    test if no elements in a container fulfill a condition.

 .. cpp:function:: pw::containers::ForEach()

    Container-based version of the <algorithm> ``std::for_each()`` function to
    apply a function to a container's elements.

 .. cpp:function:: pw::containers::Find()

    Container-based version of the <algorithm> ``std::find()`` function to find
    the first element containing the passed value within a container value.

 .. cpp:function:: pw::containers::FindIf()

    Container-based version of the <algorithm> ``std::find_if()`` function to find
    the first element in a container matching the given condition.

 .. cpp:function:: pw::containers::FindIfNot()

    Container-based version of the <algorithm> ``std::find_if_not()`` function to
    find the first element in a container not matching the given condition.

 .. cpp:function:: pw::containers::FindEnd()

    Container-based version of the <algorithm> ``std::find_end()`` function to
    find the last subsequence within a container.

 .. cpp:function:: pw::containers::FindFirstOf()

    Container-based version of the <algorithm> ``std::find_first_of()`` function
    to find the first element within the container that is also within the options
    container.

 .. cpp:function:: pw::containers::AdjacentFind()

    Container-based version of the <algorithm> ``std::adjacent_find()`` function
    to find equal adjacent elements within a container.

 .. cpp:function:: pw::containers::Count()

    Container-based version of the <algorithm> ``std::count()`` function to count
    values that match within a container.

 .. cpp:function:: pw::containers::CountIf()

    Container-based version of the <algorithm> ``std::count_if()`` function to
    count values matching a condition within a container.

 .. cpp:function:: pw::containers::Mismatch()

    Container-based version of the <algorithm> ``std::mismatch()`` function to
    return the first element where two ordered containers differ. Applies ``==``
    to the first ``N`` elements of ``c1`` and ``c2``, where
    ``N = min(size(c1), size(c2)).`` the function's test condition. Applies
    ``pred`` to the first N elements of ``c1``  and ``c2``, where
    ``N = min(size(c1), size(c2))``.

 .. cpp:function:: bool pw::containers::Equal()

    Container-based version of the <algorithm> ``std::equal()`` function to
    test whether two containers are equal.

    .. note::

       The semantics of ``Equal()`` are slightly different than those of
       ``std::equal()``: while the latter iterates over the second container only
       up to the size of the first container, ``Equal()`` also checks whether the
       container sizes are equal.  This better matches expectations about
       ``Equal()`` based on its signature.

 .. cpp:function:: bool pw::containers::IsPermutation()

    Container-based version of the <algorithm> ``std::is_permutation()`` function
    to test whether a container is a permutation of another.

 .. cpp:function:: pw::containers::Search()

    Container-based version of the <algorithm> ``std::search()`` function to
    search a container for a subsequence.

 .. cpp:function:: pw::containers::SearchN()

    Container-based version of the <algorithm> ``std::search_n()`` function to
    search a container for the first sequence of N elements.

 -------------
 Compatibility
 -------------
 - C++17

 ------
 Zephyr
 ------
 To enable ``pw_containers`` for Zephyr add ``CONFIG_PIGWEED_CONTAINERS=y`` to
 the project's configuration.
	.. _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::InlineDeque
	---------------
	.. doxygentypedef:: pw::InlineDeque

	---------------
	pw::InlineQueue
	---------------
	.. doxygentypedef:: pw::InlineQueue

	--------------------------
	pw::InlineVarLenEntryQueue
	--------------------------
	.. doxygenfile:: pw_containers/inline_var_len_entry_queue.h
	:sections: detaileddescription

	Example
	=======
	.. tab-set::

	.. tab-item:: C++
	:sync: c++

	Queues are declared with their max size
	(``InlineVarLenEntryQueue<kMaxSize>``) but may be used without
	specifying the size (``InlineVarLenEntryQueue<>&``).

	.. code-block:: c++

	// Declare a queue with capacity sufficient for one 10-byte entry or
	// multiple smaller entries.
	pw::InlineVarLenEntryQueue<10> queue;

	// Push an entry, asserting if the entry does not fit.
	queue.push(queue, data)

	// Use push_overwrite() to push entries, overwriting older entries
	// as needed.
	queue.push_overwrite(queue, more_data)

	// Remove an entry.
	queue.pop();

	Alternately, a ``InlineVarLenEntryQueue`` may be initialized in an
	existing ``uint32_t`` array.

	.. code-block:: c++

	// Initialize a InlineVarLenEntryQueue.
	uint32_t buffer[32];
	auto& queue = pw::InlineVarLenEntryQueue<>::Init(buffer);

	// Largest supported entry is 114 B (13 B overhead + 1 B prefix)
	assert(queue.max_size_bytes() == 114u);

	// Write data
	queue.push_overwrite(data);

	.. tab-item:: C
	:sync: c

	A ``InlineVarLenEntryQueue`` may be declared and initialized in C with the
	:c:macro:`PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE` macro.

	.. code-block:: c

	// Declare a queue with capacity sufficient for one 10-byte entry or
	// multiple smaller entries.
	PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(queue, 10);

	// Push an entry, asserting if the entry does not fit.
	pw_InlineVarLenEntryQueue_Push(queue, "12345", 5);

	// Use push_overwrite() to push entries, overwriting older entries
	// as needed.
	pw_InlineVarLenEntryQueue_PushOverwrite(queue, "abcdefg", 7);

	// Remove an entry.
	pw_InlineVarLenEntryQueue_Pop(queue);

	Alternately, a ``InlineVarLenEntryQueue`` may be initialized in an
	existing ``uint32_t`` array.

	.. code-block:: c

	// Initialize a InlineVarLenEntryQueue.
	uint32_t buffer[32];
	pw_InlineVarLenEntryQueue_Init(buffer, 32);

	// Largest supported entry is 114 B (13 B overhead + 1 B prefix)
	assert(pw_InlineVarLenEntryQueue_MaxSizeBytes(buffer) == 114u);

	// Write some data
	pw_InlineVarLenEntryQueue_PushOverwrite(buffer, "123", 3);

	Queue vs. deque
	===============
	This module provides :cpp:type:`InlineVarLenEntryQueue`, but no corresponding
	``InlineVarLenEntryDeque`` class. Following the C++ Standard Library style,
	the deque class would provide ``push_front()`` and ``pop_back()`` operations in
	addition to ``push_back()`` and ``pop_front()`` (equivalent to a queue's
	``push()`` and ``pop()``).

	There is no ``InlineVarLenEntryDeque`` class because there is no efficient way
	to implement ``push_front()`` and ``pop_back()``. These operations would
	necessarily be O(n), since each entry knows the position of the next entry, but
	not the previous, as in a single-linked list. Given that these operations would
	be inefficient and unlikely to be used, they are not implemented, and only a
	queue class is provided.

	API Reference
	=============
	C++
	---
	.. doxygengroup:: inline_var_len_entry_queue_cpp_api
	:content-only:
	:members:

	C
	-
	.. doxygengroup:: inline_var_len_entry_queue_c_api
	:content-only:

	Python
	------
	.. automodule:: pw_containers.inline_var_len_entry_queue
	:members:

	-----------------
	pw::IntrusiveList
	-----------------
	``pw::IntrusiveForwardList`` and ``pw::IntrusiveList`` provide embedded-friendly
	singly- and doubly-linked intrusive list implementations, respectively. An
	intrusive list is a type of linked list that embeds list metadata, such as a
	"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::IntrusiveForwardList`` and
	``pw::IntrusiveList`` uses C++ features to simplify the process of creating an
	intrusive list. They provide classes that list elements can inherit from,
	protecting the list metadata from being accessed by the item class.

	API Reference
	=============
	IntrusiveForwardList
	--------------------
	This class is similar to ``std::forward_list<T>``, except that the type of items
	to be added must derive from ``pw::IntrusiveForwardList<T>::Item``.

	.. doxygenclass:: pw::IntrusiveForwardList
	:members:

	IntrusiveList
	-------------
	This class is similar to ``std::list<T>``, except that the type of items to be
	added must derive from ``pw::IntrusiveList<T>::Item``.

	.. doxygenclass:: pw::containers::future::IntrusiveList
	:members:

	.. note::
	Originally, ``pw::IntrusiveList<T>`` was implemented as a singly-linked list.
	To facilitate migration to ``pw::IntrusiveForwardList<T>::Item``, this
	original implementation can still be temporarily used by enabling the
	``PW_CONTAINERS_USE_LEGACY_INTRUSIVE_LIST`` module configuration option.

	Example
	=======
	.. code-block:: cpp

	class Square
	: public pw::IntrusiveForwardList<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::IntrusiveForwardList<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
	// `IntrusiveForwardList<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());
	}

	// Like std::forward_list, an iterator is invalidated when the item it refers
	// to is removed. It is NOT safe to remove items from a list while iterating
	// over it in a range-based for loop.
	for (const auto& square_bad_example : squares) {
	if (square_bad_example.verticies() != 4) {
	// BAD EXAMPLE of how to remove matching items from a singly linked list.
	squares.remove(square_bad_example); // NEVER DO THIS! THIS IS A BUG!
	}
	}

	// To remove items while iterating, use an iterator to the previous item.
	auto previous = squares.before_begin();
	auto current = squares.begin();

	while (current != squares.end()) {
	if (current->verticies() != 4) {
	current = squares.erase_after(previous);
	} else {
	previous = current;
	++current;
	}
	}

	Performance Considerations
	==========================
	Items only include pointers to the next item. To reach previous items, the list
	maintains a cycle of items so that the first item can be reached from the last.
	This structure means certain operations have linear complexity in terms of the
	number of items in the list, i.e. they are "O(n)":

	- Adding to the end of a list with ``pw::IntrusiveList<T>::push_back(T&)``.
	- Accessing the last item in a list with ``pw::IntrusiveList<T>::back()``.
	- Destroying an item with ``pw::IntrusiveList<T>::Item::~Item()``.
	- Moving an item with either ``pw::IntrusiveList<T>::Item::Item(Item&&)`` or
	``pw::IntrusiveList<T>::Item::operator=(Item&&)``.
	- Removing an item from a list using ``pw::IntrusiveList<T>::remove(const T&)``.
	- Getting the list size using ``pw::IntrusiveList<T>::size()``.

	When using a ``pw::IntrusiveList<T>`` in a performance critical section or with
	many items, authors should prefer to avoid these methods. For example, it may be
	preferrable to create items that together with their storage outlive the list.

	Notably, ``pw::IntrusiveList<T>::end()`` is constant complexity (i.e. "O(1)").
	As a result iterating over a list does not incur an additional penalty.

	Size report
	===========
	.. include:: intrusive_list_size_report

	-----------------------
	pw::containers::FlatMap
	-----------------------
	``FlatMap`` provides a simple, fixed-size associative array with `O`\ (log `n`)
	lookup by key.

	``pw::containers::FlatMap`` contains the same methods and features for looking
	up data as ``std::map``. However, modification of the underlying data is limited
	to the mapped values, via ``.at()`` (key must exist) and ``mapped_iterator``
	objects returned by ``.mapped_begin()`` and ``.mapped_end()``.
	``mapped_iterator`` objects are bidirectional iterators that can be dereferenced
	to access and mutate the mapped value objects.

	The underlying array in ``pw::containers::FlatMap`` does not need to be sorted.
	During construction, ``pw::containers::FlatMap`` will perform a constexpr
	insertion sort.

	To create a ``FlatMap``, there are some options. The following example defines
	a ``FlatMap`` with two items.

	.. code-block:: cpp

	// Initiates by a std::array of Pair<K, V> objects.
	FlatMap<int, char, 2> map({{
	{1, 'a'},
	{-3, 'b'},
	}});

	FlatMap map(std::array{
	Pair<int, char>{1, 'a'},
	Pair<int, char>{-3, 'b'},
	});

	// Initiates by Pair<K, V> objects.
	FlatMap map = {
	Pair<int, char>{1, 'a'},
	Pair<int, char>{-3, 'b'},
	};

	----------------------------
	pw::containers::FilteredView
	----------------------------
	.. doxygenclass:: pw::containers::FilteredView

	-------------------------------
	pw::containers::WrappedIterator
	-------------------------------
	``pw::containers::WrappedIterator`` is a class that makes it easy to wrap an
	existing iterator type. It reduces boilerplate by providing ``operator++``,
	``operator--``, ``operator==``, ``operator!=``, and the standard iterator
	aliases (``difference_type``, ``value_type``, etc.). It does not provide the
	dereference operator; that must be supplied by a derived class.

	To use it, create a class that derives from ``WrappedIterator`` and define
	``operator*()`` and ``operator->()`` as appropriate. The new iterator might
	apply a transformation to or access a member of the values provided by the
	original iterator. The following example defines an iterator that multiplies the
	values in an array by 2.

	.. code-block:: cpp

	// Divides values in a std::array by two.
	class DoubleIterator
	: public pw::containers::WrappedIterator<DoubleIterator, const int*, int> {
	public:
	constexpr DoubleIterator(const int* it) : WrappedIterator(it) {}

	int operator() const { return value() 2; }

	// Don't define operator-> since this iterator returns by value.
	};

	constexpr std::array<int, 6> kArray{0, 1, 2, 3, 4, 5};

	void SomeFunction {
	for (DoubleIterator it(kArray.begin()); it != DoubleIterator(kArray.end()); ++it) {
	// The iterator yields 0, 2, 4, 6, 8, 10 instead of the original values.
	}
	};

	``WrappedIterator`` may be used in concert with ``FilteredView`` to create a
	view that iterates over a matching values in a container and applies a
	transformation to the values. For example, it could be used with
	``FilteredView`` to filter a list of packets and yield only one field from the
	packet.

	The combination of ``FilteredView`` and ``WrappedIterator`` provides some basic
	functional programming features similar to (though much more cumbersome than)
	`generator expressions <https://www.python.org/dev/peps/pep-0289/>`_ (or `filter
	<https://docs.python.org/3/library/functions.html#filter>`_/`map
	<https://docs.python.org/3/library/functions.html#map>`_) in Python or streams
	in Java 8. ``WrappedIterator`` and ``FilteredView`` require no memory
	allocation, which is helpful when memory is too constrained to process the items
	into a new container.

	------------------------
	pw::containers::to_array
	------------------------
	``pw::containers::to_array`` is a C++14-compatible implementation of C++20's
	`std::to_array <https://en.cppreference.com/w/cpp/container/array/to_array>`_.
	In C++20, it is an alias for ``std::to_array``. It converts a C array to a
	``std::array``.

	-------------------------
	pw_containers/algorithm.h
	-------------------------
	Pigweed provides a set of Container-based versions of algorithmic functions
	within the C++ standard library, based on a subset of
	``absl/algorithm/container.h``.

	.. cpp:function:: bool pw::containers::AllOf()

	Container-based version of the <algorithm> ``std::all_of()`` function to
	test if all elements within a container satisfy a condition.

	.. cpp:function:: bool pw::containers::AnyOf()

	Container-based version of the <algorithm> ``std::any_of()`` function to
	test if any element in a container fulfills a condition.

	.. cpp:function:: bool pw::containers::NoneOf()

	Container-based version of the <algorithm> ``std::none_of()`` function to
	test if no elements in a container fulfill a condition.

	.. cpp:function:: pw::containers::ForEach()

	Container-based version of the <algorithm> ``std::for_each()`` function to
	apply a function to a container's elements.

	.. cpp:function:: pw::containers::Find()

	Container-based version of the <algorithm> ``std::find()`` function to find
	the first element containing the passed value within a container value.

	.. cpp:function:: pw::containers::FindIf()

	Container-based version of the <algorithm> ``std::find_if()`` function to find
	the first element in a container matching the given condition.

	.. cpp:function:: pw::containers::FindIfNot()

	Container-based version of the <algorithm> ``std::find_if_not()`` function to
	find the first element in a container not matching the given condition.

	.. cpp:function:: pw::containers::FindEnd()

	Container-based version of the <algorithm> ``std::find_end()`` function to
	find the last subsequence within a container.

	.. cpp:function:: pw::containers::FindFirstOf()

	Container-based version of the <algorithm> ``std::find_first_of()`` function
	to find the first element within the container that is also within the options
	container.

	.. cpp:function:: pw::containers::AdjacentFind()

	Container-based version of the <algorithm> ``std::adjacent_find()`` function
	to find equal adjacent elements within a container.

	.. cpp:function:: pw::containers::Count()

	Container-based version of the <algorithm> ``std::count()`` function to count
	values that match within a container.

	.. cpp:function:: pw::containers::CountIf()

	Container-based version of the <algorithm> ``std::count_if()`` function to
	count values matching a condition within a container.

	.. cpp:function:: pw::containers::Mismatch()

	Container-based version of the <algorithm> ``std::mismatch()`` function to
	return the first element where two ordered containers differ. Applies ``==``
	to the first ``N`` elements of ``c1`` and ``c2``, where
	``N = min(size(c1), size(c2)).`` the function's test condition. Applies
	``pred`` to the first N elements of ``c1`` and ``c2``, where
	``N = min(size(c1), size(c2))``.

	.. cpp:function:: bool pw::containers::Equal()

	Container-based version of the <algorithm> ``std::equal()`` function to
	test whether two containers are equal.

	.. note::

	The semantics of ``Equal()`` are slightly different than those of
	``std::equal()``: while the latter iterates over the second container only
	up to the size of the first container, ``Equal()`` also checks whether the
	container sizes are equal. This better matches expectations about
	``Equal()`` based on its signature.

	.. cpp:function:: bool pw::containers::IsPermutation()

	Container-based version of the <algorithm> ``std::is_permutation()`` function
	to test whether a container is a permutation of another.

	.. cpp:function:: pw::containers::Search()

	Container-based version of the <algorithm> ``std::search()`` function to
	search a container for a subsequence.

	.. cpp:function:: pw::containers::SearchN()

	Container-based version of the <algorithm> ``std::search_n()`` function to
	search a container for the first sequence of N elements.

	-------------
	Compatibility
	-------------
	- C++17

	------
	Zephyr
	------
	To enable ``pw_containers`` for Zephyr add ``CONFIG_PIGWEED_CONTAINERS=y`` to
	the project's configuration.