Sets#
pw_containers: Generic collections of objects for embedded devices
A set is an unordered collection of items. Pigweed provides implementations that can insert, find, and remove items in logarithmic time.
pw::IntrusiveSet#
pw::IntrusiveSet provides an embedded-friendly, tree-based, intrusive
set implementation. The intrusive aspect of the set is very similar to that of
pw::IntrusiveList.
This class is similar to std::set<T>. Items to be added must derive from
pw::IntrusiveSet<T>::Item or an equivalent type.
See also Using items with multiple containers.
Example#
1class Book : public pw::IntrusiveSet<Book>::Item {
2 private:
3 using Item = pw::IntrusiveSet<Book>::Item;
4
5 public:
6 explicit Book(const char* name) : name_(name) {}
7 const char* name() const { return name_; }
8 bool operator<(const Book& rhs) const {
9 return strcmp(name_, rhs.name()) < 0;
10 }
11
12 private:
13 const char* name_;
14};
15
16std::array<Book, 8> books = {
17 Book("A Tale of Two Cities"),
18 Book("The Little Prince"),
19 Book("The Alchemist"),
20 Book("Harry Potter and the Philosopher's Stone"),
21 Book("And Then There Were None"),
22 Book("Dream of the Red Chamber"),
23 Book("The Hobbit"),
24 Book("Alice's Adventures in Wonderland"),
25};
26
27pw::IntrusiveSet<Book> library(books.begin(), books.end());
28
29void VisitLibrary(pw::IntrusiveSet<Book>& book_bag) {
30 // Return any books we previously checked out.
31 library.merge(book_bag);
32
33 // Pick out some new books to read to the kids, but only if they're available.
34 std::array<const char*, 3> titles = {
35 "The Hobbit",
36 "Curious George",
37 "Harry Potter and the Philosopher's Stone",
38 };
39 for (const char* title : titles) {
40 Book requested(title);
41 auto iter = library.find(requested);
42 if (iter != library.end()) {
43 Book& book = *iter;
44 library.erase(iter);
45 book_bag.insert(book);
46 }
47 }
48}
If you need to add this item to containers of more than one type, see Using items with multiple containers,
pw::IntrusiveMultiSet#
pw::IntrusiveMultiSet provides an embedded-friendly, tree-based, intrusive
multiset implementation. This is very similar to
pw::IntrusiveSet, except that the tree may contain
multiple items with equivalent keys.
This class is similar to std::multiset<T>. Items to be added must derive
from pw::IntrusiveMultiSet<T>::Item or an equivalent type.
See also Using items with multiple containers.
Example#
1class Book : public pw::IntrusiveMultiSet<Book>::Item {
2 private:
3 using Item = pw::IntrusiveMultiSet<Book>::Item;
4
5 public:
6 explicit Book(const char* name) : name_(name) {}
7 const char* name() const { return name_; }
8 bool operator<(const Book& rhs) const {
9 return strcmp(name_, rhs.name()) < 0;
10 }
11
12 private:
13 const char* name_;
14};
15
16std::array<Book, 12> books = {
17 Book("The Little Prince"),
18 Book("Harry Potter and the Philosopher's Stone"),
19 Book("Harry Potter and the Philosopher's Stone"),
20 Book("Harry Potter and the Philosopher's Stone"),
21 Book("Harry Potter and the Philosopher's Stone"),
22 Book("Harry Potter and the Philosopher's Stone"),
23 Book("The Hobbit"),
24 Book("The Hobbit"),
25 Book("The Hobbit"),
26 Book("The Hobbit"),
27 Book("Alice's Adventures in Wonderland"),
28 Book("Alice's Adventures in Wonderland"),
29};
30pw::IntrusiveMultiSet<Book> library(books.begin(), books.end());
31
32void VisitLibrary(pw::IntrusiveMultiSet<Book>& book_bag) {
33 // Pick out some new books to read to the kids, but only if they're available.
34 std::array<const char*, 3> titles = {
35 "The Hobbit",
36 "Alice's Adventures in Wonderland",
37 "The Little Prince",
38 };
39 for (const char* title : titles) {
40 Book requested(title);
41 auto iter = library.find(requested);
42 if (iter != library.end()) {
43 Book& book = *iter;
44 library.erase(iter);
45 book_bag.insert(book);
46 }
47 }
48}
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_sets
Size reports#
The tables below illustrate the following scenarios:
Scenarios related to
IntrusiveSet:The memory and code size cost incurred by a adding a single
IntrusiveSet.The memory and code size cost incurred by adding another
IntrusiveSetwith a different type. AsIntrusiveSetis templated on type, this results in additional code being generated.
Scenarios related to
IntrusiveMultiSet:The memory and code size cost incurred by a adding a single
IntrusiveMultiSet.The memory and code size cost incurred by adding another
IntrusiveMultiSetwith a different type. AsIntrusiveMultiSetis templated on type, this results in additional code being generated.
The memory and code size cost incurred by a adding both an
IntrusiveSetand anIntrusiveMultiSetof the same type. These types reuse code, so the combined sum is less than the sum of its parts.
Label |
Segment |
Delta |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
IntrusiveSet |
FLASH
|
+3,040 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+196 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveSet with different item type |
FLASH
|
+1,368 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+276 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IntrusiveMultiSet |
FLASH
|
+3,040 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+196 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveMultiSet with different item type |
FLASH
|
+1,352 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+276 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IntrusiveSet and IntrusiveMultiSet |
FLASH
|
+4,392 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+392 |