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::BitSet#
pw::BitSet is a constexpr-friendly fixed-size sequence of bits,
similar to std::bitset.
This container supports manipulation of a fixed number of bits, including at compile time. It supports common bitwise operations and is optimized for size by using the smallest possible underlying integer type.
Example#
1#include "pw_containers/bitset.h"
2
3#include "pw_assert/assert.h"
4
5namespace examples {
6
7// A BitSet of 8 bits, initialized to 0b10101010.
8constexpr pw::BitSet<8> my_bitset1 = pw::BitSet<8>::Of<0b10101010>();
9
10// BitSets can also be initialized with booleans.
11constexpr pw::BitSet<4> my_bitset2 =
12 pw::BitSet<4>::LittleEndian(true, false, true, false);
13
14constexpr pw::BitSet<8> MergeAndModify() {
15 pw::BitSet<8> bits = my_bitset1 | pw::BitSet<8>(my_bitset2);
16 PW_ASSERT(bits == pw::BitSet<8>::Of<0b10101111>());
17
18 // Bits can be tested, set, flipped, and reset (cleared).
19 PW_ASSERT(!bits.test<6>());
20 bits.set<6>();
21 PW_ASSERT(bits.test<6>());
22
23 bits.flip();
24 PW_ASSERT(bits == pw::BitSet<8>::Of<0b00010000>());
25
26 bits.reset<4>();
27 return bits;
28}
29
30// BitSet is fully constexpr.
31static_assert(MergeAndModify().none());
32
33} // namespace examples
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 |