| # Iterators | |
| So far, examples that have been presented have shown many uses of `fbl::` | |
| iterators. Iterators in `fbl::` use an API very similar to the API used in the | |
| `std::` containers, so hopefully this will feel very familiar to you. It is, | |
| however, worth taking a small amount of time to mention the things that all | |
| `fbl::` iterators support, in addition to places where they differ slightly from | |
| `std::` iterators. | |
| ## `iterator` and `const_iterator` | |
| As with `std::` iterators, `fbl::` iterators come in two flavors, a non-constant | |
| and a constant version. Operations such as `begin()` or `find()` will return a | |
| simple iterator in the case that the reference to the container the user has is | |
| non-`const`, and a `const_iterator` otherwise. Dereference operations performed | |
| on `const_iterators` give a `const T&` and therefore `const` access to the | |
| underlying object. | |
| ## `begin()`/`end()` | |
| Just like in `std::`, the `begin()` method on a container returns an iterator to | |
| the first element in the container while `end()` returns an iterator to an | |
| element one past the last element in the container. Both begin and end will | |
| automatically return a `const_iterator` when called on a `const` reference to | |
| the container, but `cbegin()`/`cend()` may be used in the case that a | |
| `const_iterator` is explicitly desired from a mutable reference to the | |
| container. | |
| ## Iterator comparison and default initialized iterators vs. `end()` | |
| Like `std::`, all fbl:: iterators support testing for equality using the `==` | |
| and `!=` operators. Unlike `std::`, none of the iterators have random access | |
| iterator semantics, and the `>`, `>=`, `<`, and `<=` operators are not supported | |
| for any of the `fbl::` containers' iterator types. | |
| In addition, there is a slight internal difference between a default initialized | |
| iterator and an iterator returned from a call to a container's `end()` method. | |
| Semantically, they are the same. Both a default initialized iterator and the | |
| value of `end()` are invalid, so comparison between the two will return `true`. | |
| The bits contained in the two instances, however are different. Always use the | |
| comparison operators when testing for equality between two iterators. | |
| ```cpp | |
| fbl::DoublyLinkedList<Obj*> the_list; | |
| fbl::DoublyLinkedList<Obj*>::iterator default_init; | |
| auto end_init = the_list.end(); | |
| if (default_init == end_init) { } // This comparison is true | |
| if (!memcmp(&default_init, &end_init, sizeof(end_init))) { } // This is not. | |
| ``` | |
| ## Iterator advancement | |
| All iterators support both the pre and post-fix forms of the `++` operator. The | |
| pre-fix form will move the iterator to the next element in the sequence, and | |
| return a copy of the iterator now pointing to the next element. The post-fix | |
| form will move the iterator to the next element in the sequence while returning | |
| a copy of the pre-advanced iterator. | |
| ```cpp | |
| // Assuming that the list starts containing objects with values | |
| // "5 7 9", in that order. | |
| fbl::DoublyLinkedList<Obj*> the_list; | |
| auto iter = the_list.begin(); // iter points to "5". | |
| auto second = iter++; // iter points to "7", but second points to "5" | |
| auto third = ++iter; // iter points to "9", and so does third | |
| ++iter; // iter is now equal to the_list.end() | |
| ``` | |
| Iterators for `DoublyLinkedList`s, `HashTable`s with doubly linked list buckets, | |
| and `WAVLTree`s all support bidirectional iteration via the `--` operator, again | |
| in both its pre and post fix forms. `SinglyLinkedList`s and `HashTable`s with | |
| singly linked list buckets do not. | |
| Advancing an iterator past the end of a container gives `container.end()`. | |
| Attempting to advance further is legal, but does not change the value of the | |
| iterator. Backing up a bi-directional iterator that is currently set to | |
| `container.end()` using the `--` operator will produce an iterator that points | |
| to the last element in the list, _however backing up an iterator that has been | |
| default initialized does not_. Instead, executing either `++` or `--` on a | |
| default initialized leaves the iterator in the default initialized state. | |
| Finally, backing up an iterator whose value is equal to `container.begin()` will | |
| produce an iterator whose value is equal to `container.end()`. Subsequent | |
| applications of `--` will walk through the elements in reverse order starting | |
| with the last element. | |
| ## Dereferencing iterators | |
| Elements in `fbl::` containers are always objects, therefore they always support | |
| the `->` operator in addition to the unary `*` operator. Both produce either a | |
| `T&` or a `const T&` (which `->` then accesses a member of) based on if the | |
| iterator was a `const_iterator` or not. | |
| It is illegal to attempt to deference an invalid iterator and will either | |
| trigger a `ZX_DEBUG_ASSERT` or undefined behavior, depending on the nature of | |
| the build. | |
| ## Creating an iterator from an object using container::make_iterator() | |
| Because of the intrusive nature of the containers, it is possible to create a | |
| container iterator using an existing reference to an object. For example, given | |
| a tree of objects ordered by key, a function that takes an object, and returns a | |
| reference to the object before it, in key sequence, could be written by saying | |
| something like: | |
| ``` | |
| using ObjectTree = fbl::WAVLTree<uint64_t, fbl::RefPtr<Object>>; | |
| fbl::RefPtr<Object> FetchPrior(ObjectTree& tree, Object& obj) { | |
| ZX_DEBUG_ASSERT(obj.InContainer()); | |
| auto iter = tree.make_iterator(obj); | |
| return (--iter).IsValid() ? iter.CopyPointer() : nullptr; | |
| } | |
| ``` | |
| ## iterator::IsValid() | |
| All `fbl::` iterator instances may be tested for validity using the `IsValid` | |
| method of the iterator instance itself. Testing an iterator for validity in this | |
| way is equivalent to testing `iter != container.end()`, however the `IsValid` | |
| approach may produce _slightly_ more efficient code, depending on how smart the | |
| compiler is and how much visibility it has into the implementation of the | |
| container's `end()` method. | |
| ## iterator::CopyPointer() | |
| Finally, `fbl::` iterators provide a method called `CopyPointer`, which can be | |
| used to produce a copy of the pointer type being used by the container. For | |
| containers of raw pointers, this is nothing special. It is simply a `T*` copy of the | |
| pointer to the object. In fact, `iter.CopyPointer() == &(*iter)` should always | |
| be true for raw pointers. | |
| `CopyPointer` is not legal for managed pointers with unique semantics. Attempting | |
| to call `CopyPointer` on a container of objects tracked using `std::unique_ptr` | |
| will produce an error. | |
| Finally, when `CopyPointer` is executed on an iterator for a container of | |
| copyable managed pointers, a new copy of the pointer will be produced using the | |
| copy constructor of the pointer type. In other words, it will produce a new | |
| managed reference to the object. | |
| Attempting to call `CopyPointer` on an invalid iterator to a copyable pointer | |
| type will produce `nullptr`. |