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.
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
|
+528 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+324 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IntrusiveMap |
FLASH
|
+3,200 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+244 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveMap with different key type |
(ALL) |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveMap with different key and value types |
FLASH
|
+648 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+276 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IntrusiveMultiMap |
FLASH
|
+3,200 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+244 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveMultiMap with different key type |
(ALL) |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveMultiMap with different key and value types |
FLASH
|
+616 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+36 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IntrusiveMap and IntrusiveMultiMap |
FLASH
|
+3,848 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+472 |