pw_containers: Make list iterators consistent with std::forward_list
After discussion, it was decided that since IntrusiveList follows
std::forward_list's interface, its iterators should behave like
std::forward_list. Commit 5733a0e4d599dbc700692d1b04be3bb09030b6a2 added
an extra pointer to the IntrusiveList iterator that made them usable
after the item they point to is removed from the list, which is
useful, but not consistent with std::forward_list.
Code that uses IntrusiveList iterators to removed items (e.g. if
removing items while iterating in a range-based for loop) would result
in undefined behavior if the IntrusiveList were exchanged for a
std::forward_list.
This reverts commit 5733a0e4d599dbc700692d1b04be3bb09030b6a2 and updates
the documentation.
Change-Id: I6092e5ccd6d7a5e1c43f85258ea51ae9cba28fd8
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/pigweed/+/82880
Reviewed-by: Erik Gilling <konkers@google.com>
Commit-Queue: Wyatt Hepler <hepler@google.com>
diff --git a/pw_containers/docs.rst b/pw_containers/docs.rst
index e48958a..07093db 100644
--- a/pw_containers/docs.rst
+++ b/pw_containers/docs.rst
@@ -81,9 +81,27 @@
PW_LOG_INFO("Found a square with an area of %lu", square.Area());
}
- // It is safe to remove items from a list while iterating over it.
- for (const auto& square : squares) {
- squares.remove(item);
+ // Like std::forward_list, an iterator is invalidated when the item it refers
+ // to is removed. It is *NOT* safe to remove items from a list while iterating
+ // over it in a range-based for loop.
+ for (const auto& square_bad_example : squares) {
+ if (square_bad_example.verticies() != 4) {
+ // BAD EXAMPLE of how to remove matching items from a singly linked list.
+ squares.remove(square_bad_example); // NEVER DO THIS! THIS IS A BUG!
+ }
+ }
+
+ // To remove items while iterating, use an iterator to the previous item.
+ auto previous = squares.before_begin();
+ auto current = squares.begin();
+
+ while (current != squares.end()) {
+ if (current->verticies() != 4) {
+ current = squares.erase_after(previous);
+ } else {
+ previous = current;
+ ++current;
+ }
}
pw::containers::FlatMap