pw_containers#

The pw_containers module provides embedded-friendly container classes.

pw::Vector#

Pigweed AI summary: The pw::Vector class is similar to std::vector, but with a fixed-size buffer. Vectors must be declared with an explicit maximum size, but can be used without the max size template parameter. All Vector classes inherit from the generic Vector<T>, which stores the maximum size in a variable, allowing Vectors to be used without knowing their maximum size at compile time and keeping code size small.

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#

template<typename T, size_t kCapacity = containers::internal::kGenericSized> using pw::InlineDeque = BasicInlineDeque<T, uint16_t, kCapacity>#

The InlineDeque class is similar to the STL’s double ended queue (std::deque), except it is backed by a fixed-size buffer. InlineDeque’s must be declared with an explicit maximum size (e.g. InlineDeque<int, 10>>) but deques can be used and referred to without the max size template parameter (e.g. InlineDeque<int>).

To allow referring to a pw::InlineDeque without an explicit maximum size, all InlineDeque classes inherit from the generic InlineDeque<T>, which stores the maximum size in a variable. This allows InlineDeques 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::InlineQueue#

template<typename T, size_t kCapacity = containers::internal::kGenericSized> using pw::InlineQueue = BasicInlineQueue<T, uint16_t, kCapacity>#

The InlineQueue class is similar to std::queue<T, std::deque>, except it is backed by a fixed-size buffer. InlineQueue’s must be declared with an explicit maximum size (e.g. InlineQueue<int, 10>>) but deques can be used and referred to without the max size template parameter (e.g. InlineQueue<int>).

pw::InlineQueue is wrapper around pw::InlineDeque with a simplified API and push_overwrite() & emplace_overwrite() helpers.

pw::IntrusiveList#

Pigweed AI summary: The pw::IntrusiveList is a C++ class that provides an embedded-friendly singly-linked intrusive list implementation. It simplifies the process of creating an intrusive list by providing a class that list elements can inherit from. Objects that will be added to an IntrusiveList must inherit from IntrusiveList::Item. The API of pw::IntrusiveList is similar to a std::forward_list, but there are extra steps to creating objects that can be stored in this data structure. The performance

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#

Pigweed AI summary: The API of pw::IntrusiveList is similar to std::forward_list, but objects that will be added to an IntrusiveList<T> must inherit from IntrusiveList<T>::Item. 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. An instantiated IntrusiveList<T>::Item will be removed from its corresponding IntrusiveList when it goes out of scope, and a linked

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 will be removed from its corresponding IntrusiveList when it goes out of scope.
A linked list item CANNOT be included in two lists. Attempting to do so results in an assert failure.

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());
}

// 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#

Pigweed AI summary: The "Performance Considerations" section explains that the structure of the list means certain operations have linear complexity in terms of the number of items in the list, which can impact performance. These operations include adding to the end of a list, accessing the last item, destroying an item, moving an item, removing an item, and getting the list size. To avoid performance issues, it may be preferable to create items that outlive the list. However, iterating over a list does not incur an additional penalty

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.

pw::containers::FlatMap#

Pigweed AI summary: The pw::containers::FlatMap is a fixed-size associative array that allows for efficient lookup by key. It has similar methods and features as std::map for data lookup, but modification of the underlying data is limited to the mapped values. The underlying array does not need to be sorted as the FlatMap performs a constexpr insertion sort during construction.

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.

pw::containers::FilteredView#

Pigweed AI summary: The pw::containers::FilteredView class provides a view of a container that only contains elements that match a specified filter. It is similar to C++20's std::ranges::filter_view. To create a FilteredView, a container and a filter object must be passed, which can be a lambda or a class that implements operator() for the container's value type. An example code is provided using std::array and a lambda function to filter even numbers.

pw::containers::FilteredView provides a view of a container that only contains elements that match the specified filter. This class is similar to C++20’s std::ranges::filter_view.

To create a FilteredView, pass a container and a filter object, which may be a lambda or class that implements operator() for the container’s value type.

std::array<int, 99> kNumbers = {3, 1, 4, 1, ...};

for (int even : FilteredView(kNumbers, [](int n) { return n % 2 == 0; })) {
  PW_LOG_INFO("This number is even: %d", even);
}

pw::containers::WrappedIterator#

Pigweed AI summary: The pw::containers::WrappedIterator class simplifies the process of wrapping an existing iterator type by providing operator++ and other standard iterator aliases. It does not provide the dereference operator, which 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. WrappedIterator may be used in concert with Filter

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.

// 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 (or filter/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#

Pigweed AI summary: The pw::containers::to_array is a C++14-compatible implementation of C++20's std::to_array, which is an alias for std::to_array. It converts a C array to a std::array.

pw::containers::to_array is a C++14-compatible implementation of C++20’s std::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.

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.

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.

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.

pw::containers::ForEach()#: Container-based version of the <algorithm> std::for_each() function to apply a function to a container’s elements.

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.

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.

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.

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

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.

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

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

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

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)).

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.

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

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

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#

Pigweed AI summary: This section discusses the compatibility of C++17.

C++17

Dependencies#

Pigweed AI summary: This paragraph discusses the dependencies of a certain project, specifically mentioning the "pw_span" module.

pw_span

Zephyr#

Pigweed AI summary: To enable pw_containers for Zephyr, the project's configuration must have CONFIG_PIGWEED_CONTAINERS set to "y".

To enable pw_containers for Zephyr add CONFIG_PIGWEED_CONTAINERS=y to the project’s configuration.