Maps#

pw_containers: Generic collections of objects for embedded devices

A map is an associative collection of keys that map to values. Pigweed provides an implementation of a constant “flat” map that can find values by key in constant time. It also provides implementations of dynamic maps that can insert, find, and remove key-value pairs in logarithmic time.

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.

Examples#

A FlatMap can be created in one of several ways. Each of the following examples defines a FlatMap with two items.

 1using pw::containers::FlatMap;
 2using pw::containers::Pair;
 3
 4// Initialized by an initializer list.
 5FlatMap<int, char, 2> my_flat_map1({{
 6    {1, 'a'},
 7    {-3, 'b'},
 8}});
 9
10// Initialized by a std::array of Pair<K, V> objects.
11std::array<Pair<int, char>, 2> my_array{{
12    {1, 'a'},
13    {-3, 'b'},
14}};
15FlatMap my_flat_map2(my_array);
16
17// Initialized by Pair<K, V> objects.
18FlatMap my_flat_map3 = {
19    Pair<int, char>{1, 'a'},
20    Pair<int, char>{-3, 'b'},
21};

pw::IntrusiveMap#

pw::IntrusiveMap provides an embedded-friendly, tree-based, intrusive map implementation. The intrusive aspect of the map is very similar to that of pw::IntrusiveList.

See also Using items with multiple containers.

Example#

 1struct Book : public pw::IntrusiveMap<uint32_t, Book>::Pair {
 2 private:
 3  using Pair = pw::IntrusiveMap<uint32_t, Book>::Pair;
 4
 5 public:
 6  Book(const char* name, uint32_t oclc) : Pair(oclc), name_(name) {}
 7  const char* name() const { return name_; }
 8
 9 private:
10  const char* name_;
11};
12
13std::array<Book, 8> books = {{
14    {"A Tale of Two Cities", 20848014u},
15    {"The Little Prince", 182537909u},
16    {"The Alchemist", 26857452u},
17    {"Harry Potter and the Philosopher's Stone", 44795766u},
18    {"And Then There Were None", 47032439u},
19    {"Dream of the Red Chamber", 20692970u},
20    {"The Hobbit", 1827184u},
21    {"Alice's Adventures in Wonderland", 5635965u},
22}};
23
24pw::IntrusiveMap<uint32_t, Book> library(books.begin(), books.end());
25
26void VisitLibrary(pw::IntrusiveMap<uint32_t, Book>& book_bag) {
27  // Return any books we previously checked out.
28  library.merge(book_bag);
29
30  // Pick out some new books to read to the kids, but only if they're available.
31  std::array<uint32_t, 3> oclcs = {
32      1827184u,   // The Hobbit
33      11914189u,  // Curious George
34      44795766u,  // Harry Potter
35  };
36  for (uint32_t oclc : oclcs) {
37    auto iter = library.find(oclc);
38    if (iter != library.end()) {
39      Book& book = *iter;
40      library.erase(iter);
41      book_bag.insert(book);
42    }
43  }
44}

If you need to add this item to containers of more than one type, see Using items with multiple containers,

API reference#

This class is similar to std::map<K, V>. Items to be added must derive from pw::IntrusiveMap<K, V>::Item or an equivalent type.

template<typename Key, typename T>
class IntrusiveMap#

A std::map<Key, T, Compare>-like class that uses intrusive items.

Since the map structure is stored in the items themselves, each item must outlive any map it is a part of and must be part of at most one map.

This map requires unique keys. Attempting to add an item with same key as an item already in the map will fail.

  • Since items are not allocated by this class, the following methods have no analogue:

    • std::map<T>::operator=

    • std::map<T>::operator[]

    • std::map<T>::get_allocator

    • std::map<T>::insert_or_assign

    • std::map<T>::emplace

    • std::map<T>::emplace_hint

    • std::map<T>::try_emplace

  • Methods corresponding to the following take initializer lists of pointer to items rather than the items themselves:

    • std::map<T>::(constructor)

    • std::map<T>::insert

  • There are no overloads corresponding to the following methods that take r-value references.:

    • std::map<T>::insert

    • std::map<T>::merge

  • Since modifying the map modifies the items themselves, methods corresponding to those below only take iterators and not const_iterators:

    • std::map<T>::insert

    • std::map<T>::erase

  • An additional overload of erase is provided that takes a direct reference to an item.

  • C++23 methods are not (yet) supported.

Template Parameters:

  • Key – Type to sort items on

  • T – Type of values stored in the map.

Public Types

using Item = typename Tree::Item#

IntrusiveMap items must derive from either Item or Pair. Use Pair to automatically provide storage for a Key. Use Item when the derived type has a key() accessor method or when the map provides a custom GetKey function object.

Public Functions

inline explicit constexpr IntrusiveMap()#

Constructs an empty map of items.

template<typename Comparator>
inline explicit constexpr IntrusiveMap(Comparator &&compare)#

Constructs an empty map of items.

SFINAE is used to disambiguate between this constructor and the one that takes an initializer list.

Parameters:

compare – Function with the signature bool(Key, Key) that is used to order items.

template<typename Comparator, typename KeyRetriever>
inline constexpr IntrusiveMap(Comparator &&compare, KeyRetriever &&get_key)#

Constructs an empty map of items.

Parameters:

  • compare – Function with the signature bool(Key, Key) that is used to order items.

  • get_key – Function with signature Key(const T&) that returns the value that items are sorted on.

template<typename Iterator, typename ...Functors>
inline IntrusiveMap(Iterator first, Iterator last, Functors&&... functors)#

Constructs an IntrusiveMap from an iterator over Items.

The iterator may dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. from std::initializer_list<Item*>).

template<typename ...Functors>
inline explicit IntrusiveMap(std::initializer_list<T*> items, Functors&&... functors)#

Constructs an IntrusiveMap from a std::initializer_list of pointers to items.

inline T &at(const key_type &key)#

Returns a reference to the item associated with the given key.

Pre:

The map must contain an item associated with the key.

inline bool empty() const noexcept#

Returns whether the map has zero items or not.

inline size_t size() const#

Returns the number of items in the map.

inline constexpr size_t max_size() const noexcept#

Returns how many items can be added.

As an intrusive container, this is effectively unbounded.

inline void clear()#

Removes all items from the map and leaves it empty.

The items themselves are not destructed.

inline std::pair<iterator, bool> insert(T &item)#

Attempts to add the given item to the map.

The item will be added if the map does not already contain an item with the given item’s key.

Returns:

A pointer to the inserted item and true, or a pointer to the existing item with same key and false.

inline iterator erase(T &item)#

Removes an item from the map and returns an iterator to the item after the removed item..

The items themselves are not destructed.

inline void swap(IntrusiveMap<Key, T> &other)#

Exchanges this map’s items with the other map’s items.

template<typename MapType>
inline void merge(MapType &other)#

Splices items from the other map into this one.

inline size_t count(const key_type &key) const#

Returns the number of items in the map with the given key.

Since the map requires unique keys, this is always 0 or 1.

inline iterator find(const key_type &key)#

Returns a pointer to an item with the given key, or null if the map does not contain such an item.

inline std::pair<iterator, iterator> equal_range(const key_type &key)#

Returns a pair of iterators where the first points to the item with the smallest key that is not less than the given key, and the second points to the item with the smallest key that is greater than the given key.

inline iterator lower_bound(const key_type &key)#

Returns an iterator to the item in the map with the smallest key that is greater than or equal to the given key, or end() if the map is empty.

inline iterator upper_bound(const key_type &key)#

Returns an iterator to the item in the map with the smallest key that is strictly greater than the given key, or end() if the map is empty.

class const_iterator : public containers::internal::AATreeIterator<std::add_const_t<T>>#
class iterator : public containers::internal::AATreeIterator<T>#

pw::IntrusiveMultiMap#

pw::IntrusiveMultiMap provides an embedded-friendly, tree-based, intrusive multimap implementation. This is very similar to pw::IntrusiveMap, except that the tree may contain multiple items with equivalent keys.

See also Using items with multiple containers.

Example#

 1struct Book : public pw::IntrusiveMultiMap<uint32_t, Book>::Pair {
 2 private:
 3  using Pair = pw::IntrusiveMultiMap<uint32_t, Book>::Pair;
 4
 5 public:
 6  Book(const char* name, uint32_t oclc) : Pair(oclc), name_(name) {}
 7  const char* name() const { return name_; }
 8
 9 private:
10  const char* name_;
11};
12
13std::array<Book, 12> books = {{
14    {"The Little Prince", 182537909u},
15    {"Harry Potter and the Philosopher's Stone", 44795766u},
16    {"Harry Potter and the Philosopher's Stone", 44795766u},
17    {"Harry Potter and the Philosopher's Stone", 44795766u},
18    {"Harry Potter and the Philosopher's Stone", 44795766u},
19    {"Harry Potter and the Philosopher's Stone", 44795766u},
20    {"The Hobbit", 1827184u},
21    {"The Hobbit", 1827184u},
22    {"The Hobbit", 1827184u},
23    {"The Hobbit", 1827184u},
24    {"Alice's Adventures in Wonderland", 5635965u},
25    {"Alice's Adventures in Wonderland", 5635965u},
26}};
27pw::IntrusiveMultiMap<uint32_t, Book> library(books.begin(), books.end());
28
29void VisitLibrary(pw::IntrusiveMultiMap<uint32_t, Book>& book_bag) {
30  // Pick out some new books to read to the kids, but only if they're available.
31  std::array<uint32_t, 3> oclcs = {
32      1827184u,    // The Hobbit
33      5635965u,    // Alice's Adventures in Wonderland
34      182537909u,  // The Little Prince
35  };
36  for (uint32_t oclc : oclcs) {
37    auto iter = library.find(oclc);
38    if (iter != library.end()) {
39      Book& book = *iter;
40      library.erase(iter);
41      book_bag.insert(book);
42    }
43  }
44}

If you need to add this item to containers of more than one type, see Using items with multiple containers,

API reference#

This class is similar to std::multimap<K, V>. Items to be added must derive from pw::IntrusiveMultiMap<K, V>::Item or an equivalent type.

template<typename Key, typename T>
class IntrusiveMultiMap#

A std::multimap<Key, T, Compare>-like class that uses intrusive items.

Since the map structure is stored in the items themselves, each item must outlive any map it is a part of and must be part of at most one map.

This map requires unique keys. Attempting to add an item with same key as an item already in the map will fail.

  • Since items are not allocated by this class, the following methods have no analogue:

    • std::multimap<T>::operator=

    • std::multimap<T>::get_allocator

    • std::multimap<T>::emplace

    • std::multimap<T>::emplace_hint

  • Methods corresponding to the following take initializer lists of pointer to items rather than the items themselves:

    • std::multimap<T>::(constructor)

    • std::multimap<T>::insert

  • There are no overloads corresponding to the following methods that take r-value references.:

    • std::multimap<T>::insert

    • std::multimap<T>::merge

  • Since modifying the map modifies the items themselves, methods corresponding to those below only take iterators and not const_iterators:

    • std::multimap<T>::insert

    • std::multimap<T>::erase

  • An additional overload of erase is provided that takes a direct reference to an item.

  • C++23 methods are not (yet) supported.

Template Parameters:

  • Key – Type to sort items on

  • T – Type of values stored in the map.

Public Types

using Item = typename Tree::Item#

IntrusiveMultiMap items must derive from either Item or Pair. Use Pair to automatically provide storage for a Key. Use Item when the derived type has a key() accessor method or when the map provides a custom GetKey function object.

Public Functions

inline explicit constexpr IntrusiveMultiMap()#

Constructs an empty map of items.

template<typename Comparator>
inline explicit constexpr IntrusiveMultiMap(Comparator &&compare)#

Constructs an empty map of items.

SFINAE is used to disambiguate between this constructor and the one that takes an initializer list.

Parameters:

  • compare – Function with the signature bool(Key, Key) that is used to order items.

  • get_key – Function with signature Key(const T&) that returns the value that items are sorted on.

template<typename Comparator, typename KeyRetriever>
inline constexpr IntrusiveMultiMap(
Comparator &&compare,
KeyRetriever &&get_key,
)#

Constructs an empty map of items.

Parameters:

  • compare – Function with the signature bool(Key, Key) that is used to order items.

  • get_key – Function with signature Key(const T&) that returns the value that items are sorted on.

template<typename Iterator, typename ...Functors>
inline IntrusiveMultiMap(
Iterator first,
Iterator last,
Functors&&... functors,
)#

Constructs an IntrusiveMultiMap from an iterator over Items.

The iterator may dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. from std::initializer_list<Item*>).

template<typename ...Functors>
inline IntrusiveMultiMap(std::initializer_list<T*> items, Functors&&... functors)#

Constructs an IntrusiveMultiMap from a std::initializer_list of pointers to items.

inline bool empty() const noexcept#

Returns whether the multimap has zero items or not.

inline size_t size() const#

Returns the number of items in the multimap.

inline constexpr size_t max_size() const noexcept#

Returns how many items can be added.

As an intrusive container, this is effectively unbounded.

inline void clear()#

Removes all items from the multimap and leaves it empty.

The items themselves are not destructed.

inline iterator insert(T &item)#

Adds the given item to the multimap.

inline iterator erase(T &item)#

Removes an item from the multimap and returns an iterator to the item after the removed item.

The items themselves are not destructed.

inline void swap(IntrusiveMultiMap<Key, T> &other)#

Exchanges this multimap’s items with the other multimap’s items.

template<typename MapType>
inline void merge(MapType &other)#

Splices items from the other map into this one.

inline size_t count(const Key &key) const#

Returns the number of items in the multimap with the given key.

inline iterator find(const Key &key)#

Returns a pointer to an item with the given key, or null if the multimap does not contain such an item.

inline std::pair<iterator, iterator> equal_range(const Key &key)#

Returns a pair of iterators where the first points to the item with the smallest key that is not less than the given key, and the second points to the item with the smallest key that is greater than the given key.

inline iterator lower_bound(const Key &key)#

Returns an iterator to the item in the multimap with the smallest key that is greater than or equal to the given key, or end() if the multimap is empty.

inline iterator upper_bound(const Key &key)#

Returns an iterator to the item in the multimap with the smallest key that is strictly greater than the given key, or end() if the multimap is empty.

class const_iterator : public containers::internal::AATreeIterator<std::add_const_t<T>>#
class iterator : public containers::internal::AATreeIterator<T>#

Size reports#

The tables below illustrate the following scenarios:

  • Scenarios related to FlatMap:

    • The memory and code size cost incurred by adding another FlatMap

    • The memory and code size cost incurred by adding another FlatMap with different key and value types. As FlatMap is templated on both key and value types, this results in additional code being generated.

  • Scenarios related to IntrusiveMap:

    • The memory and code size cost incurred by a adding a single IntrusiveMap.

    • The memory and code size cost incurred by adding another IntrusiveMap with the same key type, but a different value type. As IntrusiveMap is templated on both key and value types, this results in additional code being generated.

    • The memory and code size cost incurred by adding another IntrusiveMap with the same value type, but a different key type. As IntrusiveMap is templated on both key and value types, this results in additional code being generated.

  • Scenarios related to IntrusiveMultiMap:

    • The memory and code size cost incurred by a adding a single IntrusiveMultiMap.

    • The memory and code size cost incurred by adding another IntrusiveMultiMap with the same key type, but a different value type. As IntrusiveMultiMap is templated on both key and value types, this results in additional code being generated.

    • The memory and code size cost incurred by adding another IntrusiveMultiMap with the same value type, but a different key type. As IntrusiveMultiMap is templated on both key and value types, this results in additional code being generated.

  • The memory and code size cost incurred by a adding both an IntrusiveMap and an IntrusiveMultiMap of the same type. These types reuse code, so the combined sum is less than the sum of its parts.

Note

The size report that is usually displayed here is temporarily unavailable while we migrate the pigweed.dev build system from GN to Bazel. See b/388905812 for updates.

On this page