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.

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,

API reference#

This class is similar to std::set<T>. Items to be added must derive from pw::IntrusiveSet<T>::Item or an equivalent type.

template<typename T>
class IntrusiveSet#

A std::set<Key, Compare>-like class that uses intrusive items as keys.

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

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

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

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

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

    • std::set<T>::get_allocator

    • std::set<T>::insert_or_assign

    • std::set<T>::emplace

    • std::set<T>::emplace_hint

    • std::set<T>::try_emplace

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

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

    • std::set<T>::insert

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

    • std::set<T>::insert

    • std::set<T>::merge

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

    • std::set<T>::insert

    • std::set<T>::erase

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

Template Parameters:

T – Type of data stored in the set.

Public Types

using Item = typename Tree::Item#

IntrusiveSet items must derive from Item.

Public Functions

inline explicit constexpr IntrusiveSet()#

Constructs an empty set of items.

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

Constructs an empty set 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(T, T) that is used to order items.

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

Constructs an IntrusiveSet 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 IntrusiveSet(std::initializer_list<T*> items, Functors&&... functors)#

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

inline bool empty() const noexcept#

Returns whether the set has zero items or not.

inline size_t size() const#

Returns the number of items in the set.

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 set 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 set.

The item will be added if the set does not already contain an equivalent item.

Returns:

A pointer to the inserted item and true, or a pointer to the equivalent item and false.

inline iterator erase(iterator pos)#

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

The items themselves are not destructed.

inline void swap(IntrusiveSet<T> &other)#

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

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

Splices items from the other set into this one.

The receiving set’s Compare function is used when inserting items.

inline size_t count(const T &item) const#

Returns the number of equivalent items in the set.

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

inline iterator find(const T &item)#

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

inline std::pair<iterator, iterator> equal_range(const T &item)#

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

inline iterator lower_bound(const T &item)#

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

inline iterator upper_bound(const T &item)#

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

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

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.

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#

This class is similar to std::multiset<T>. Items to be added must derive from pw::IntrusiveMultiSet<T>::Item or an equivalent type.

template<typename T>
class IntrusiveMultiSet#

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

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

This set does not require unique keys. Multiple equivalent items may be added.

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

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

    • std::multiset<T>::get_allocator

    • std::multiset<T>::emplace

    • std::multiset<T>::emplace_hint

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

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

    • std::multiset<T>::insert

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

    • std::multiset<T>::insert

    • std::multiset<T>::merge

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

    • std::multiset<T>::insert

    • std::multiset<T>::erase

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

Template Parameters:

T – Type of items stored in the set.

Public Types

using Item = typename Tree::Item#

IntrusiveMultiSet items must derive from Item.

Public Functions

inline explicit constexpr IntrusiveMultiSet()#

Constructs an empty set of items.

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

Constructs an empty set 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(T, T) that is used to order items.

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

Constructs an IntrusiveMultiSet 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 IntrusiveMultiSet(std::initializer_list<T*> items, Functors&&... functors)#

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

inline bool empty() const noexcept#

Returns whether the multiset has zero items or not.

inline size_t size() const#

Returns the number of items in the multiset.

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 multiset and leaves it empty.

The items themselves are not destructed.

inline iterator insert(T &item)#

Adds the given item to the multiset.

inline iterator erase(iterator pos)#

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

The items themselves are not destructed.

inline void swap(IntrusiveMultiSet<T> &other)#

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

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

Splices items from the other set into this one.

The receiving set’s Compare function is used when inserting items.

inline size_t count(const T &item) const#

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

inline iterator find(const T &item)#

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 T &item)#

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 T &item)#

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 T &item)#

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 IntrusiveSet:

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

    • The memory and code size cost incurred by adding another IntrusiveSet with a different type. As IntrusiveSet is 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 IntrusiveMultiSet with a different type. As IntrusiveMultiSet is templated on type, this results in additional code being generated.

  • The memory and code size cost incurred by a adding both an IntrusiveSet and an IntrusiveMultiSet 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