Menu
I am developing a small library for my work, and I derived a few classes from the standard random-access iterator category. This allows me to use things like iterator traits and to not worry too much when I use standard libraries like algorithm for example. Of course I know I don't have to, and that I could either chose the bidirectional category instead or even implement my own. But that is not the point.
IMO, the "gap" between the bidirectional and random-access categories is too large, and I don't understand the necessity for the subtraction and comparison operators between iterators -- that is: a-b, a<b and a>b (and the loose variants thereof).
Why does the standard force the implementation of these operators, and could someone please give me an example where the (in)equality test, mixed iterator-scalar artithmetic (compound or not) operators and the offset dereference operator are not sufficient?
953
If two unrelated iterators (including pointers) are subtracted, the operation results in undefined behavior [ISO/IEC 14882-2014]. Do not subtract two iterators (including pointers) unless both point into the same container or one past the end of the same container.
Operator== and Operator!= To compare the values that two iterators are pointing at, dereference the iterators first, and then use a comparison operator. Operator= -- Assign the iterator to a new position (typically the start or end of the container's elements).
Random-access iterators are iterators that can be used to access elements at an arbitrary offset position relative to the element they point to, offering the same functionality as pointers. Random-access iterators are the most complete iterators in terms of functionality.
Bidirectional iterators are the iterators used to access the elements in both the directions, i.e., towards the end and towards the beginning. A random access iterator is also a valid bidirectional iterator. Many containers implement the bidirectional iterator such as list, set, multiset, map, multimap.
One common case where you need a difference between iterators is binary search: without knowing the distance, you would not know how much you need to add to the iterator on the left side in order to get to the midpoint in O(1) time. Once you know the distance, you could apply mixed iterator-scalar arithmetic to get to the middle, also in constant time.
Note that you could find the distance by repetitively incrementing one iterator until you get to the other one, but that would take O(n) time.
You also need the a < b comparison to know which iterator is on the left side, and which one is on the right. Without this comparison you would not be able to validate the input to your binary search algorithm.
I find confusing [that] the subtraction operator should return an int, and not an iterator, even though "logically" I would expect that an arithmetic operation between two objects of the same type returns an object of that type too.
Subtraction gives you the distance - the number of steps from one point to the other. This is a scalar number, independent of the type of the iterator. The symmetry here is straightforward: since
iteratorA + scalar = iteratorB
simple arithmetic rules tell us that
scalar = iteratorB - iteratorA
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
