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.
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.
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,
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.
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.
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.
pw::DynamicHashMap#
pw::DynamicHashMap is an unordered associative container, similar to
std::unordered_map, but optimized for memory-constrained environments.
Key features of pw::DynamicHashMap:
Allocator-driven: Uses a pw::Allocator for all memory operations.
- Hybrid Storage:
Nodes: Stored in a dense
pw::DynamicPtrVectorto enable efficient, linear iteration.Buckets: Stored in a
pw::DynamicDequeforO(1)average lookup.
Fallible API: Adds
try_*versions of operations (e.g.,try_insert,try_emplace,try_rehash) that returnstd::nulloptorfalseon allocation failure instead of crashing.Unstable Iteration: Uses “swap-and-pop” erasure for efficiency. Erasing an element moves the last element of the map into the erased position, changing the iteration order.
Flexible Load Factor: Supports a load factor up to 500%. While 75% is standard for speed, higher limits allow shrinking the bucket array’s footprint when RAM is more scarce than CPU cycles.
Example#
1struct Book {
2 Book(const char* n, uint32_t o) : name(n), oclc(o) {}
3
4 const char* name;
5 uint32_t oclc;
6};
7
8void PopulateLibrary(pw::DynamicHashMap<uint32_t, Book>& library) {
9 library.emplace(20848014u, "A Tale of Two Cities", 20848014u);
10 library.emplace(182537909u, "The Little Prince", 182537909u);
11 library.emplace(26857452u, "The Alchemist", 26857452u);
12 library.emplace(
13 44795766u, "Harry Potter and the Philosopher's Stone", 44795766u);
14 library.emplace(47032439u, "And Then There Were None", 47032439u);
15 library.emplace(20692970u, "Dream of the Red Chamber", 20692970u);
16 library.emplace(1827184u, "The Hobbit", 1827184u);
17 library.emplace(5635965u, "Alice's Adventures in Wonderland", 5635965u);
18}
19
20void VisitLibrary(pw::DynamicHashMap<uint32_t, Book>& library,
21 pw::DynamicHashMap<uint32_t, Book>& book_bag) {
22 // Return any books we previously checked out.
23 // The merge function moves elements from book_bag into library if the
24 // key doesn't already exist in library.
25 library.merge(book_bag);
26
27 // Pick out some new books to read to the kids, but only if they're available.
28 std::array<uint32_t, 3> oclcs = {
29 1827184u, // The Hobbit
30 11914189u, // Curious George (Not in library)
31 44795766u, // Harry Potter
32 };
33
34 for (uint32_t oclc : oclcs) {
35 auto iter = library.find(oclc);
36 if (iter != library.end()) {
37 // Move the book from the library into our bag.
38 // *iter refers to a pair<const Key, Value>.
39 if (book_bag.try_insert(*iter)) {
40 library.erase(iter);
41 }
42 }
43 }
44}
API reference#
Moved: pw_containers_maps
Size reports#
The tables below illustrate the following scenarios:
Scenarios related to
FlatMap:The memory and code size cost incurred by adding another
FlatMapThe memory and code size cost incurred by adding another
FlatMapwith different key and value types. AsFlatMapis 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
IntrusiveMapwith the same key type, but a different value type. AsIntrusiveMapis templated on both key and value types, this results in additional code being generated.The memory and code size cost incurred by adding another
IntrusiveMapwith the same value type, but a different key type. AsIntrusiveMapis 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
IntrusiveMultiMapwith the same key type, but a different value type. AsIntrusiveMultiMapis templated on both key and value types, this results in additional code being generated.The memory and code size cost incurred by adding another
IntrusiveMultiMapwith the same value type, but a different key type. AsIntrusiveMultiMapis 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
IntrusiveMapand anIntrusiveMultiMapof the same type. These types reuse code, so the combined sum is less than the sum of its parts.
Label |
Segment |
Delta |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
FlatMap |
FLASH
|
+464 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+164 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional FlatMap with different key and value types |
FLASH
|
+512 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+324 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IntrusiveMap |
FLASH
|
+3,200 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+228 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveMap with different key type |
(ALL) |
0 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveMap with different key and value types |
FLASH
|
+648 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+276 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IntrusiveMultiMap |
FLASH
|
+3,184 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+228 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveMultiMap with different key type |
(ALL) |
0 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveMultiMap with different key and value types |
FLASH
|
+632 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+36 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IntrusiveMap and IntrusiveMultiMap |
FLASH
|
+3,848 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+472 |