Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS > Class Template Reference

An Iterator<T> is a copyable object which allows traversing the contents of some container. More...

#include <Iterator.h>

Inheritance diagram for Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >:

Classes
class	IRep
	Implementation detail for iterator implementors. More...

Public Types
using	difference_type = typename ITERATOR_TRAITS::difference_type
	difference_type = typename ITERATOR_TRAITS::difference_type;
using	value_type = typename ITERATOR_TRAITS::value_type
	value_type = typename ITERATOR_TRAITS::value_type;
using	pointer = typename ITERATOR_TRAITS::pointer
	pointer = typename ITERATOR_TRAITS::pointer;
using	reference = typename ITERATOR_TRAITS::reference
	reference = typename ITERATOR_TRAITS::reference;
using	iterator_category = forward_iterator_tag
	iterator_category = forward_iterator_tag;

Public Member Functions
	Iterator (const unique_ptr< IRep > &rep) noexcept
	This overload is usually not called directly. Instead, iterators are usually created from a container (eg. Sequence<T>{}.begin()).
nonvirtual Iterator &	operator= (Iterator &&rhs) noexcept
	Iterators are safely copyable, preserving their current position. Copy-Assigning could throw since it probably involves a Clone()
nonvirtual const T &	operator* () const
	Return the Current value pointed to by the Iterator<T> (same as Current())
nonvirtual const value_type *	operator-> () const
	Return a pointer to the current value pointed to by the Iterator<T> (like Current())
nonvirtual Iterator &	operator++ ()
	Advance iterator; support for range-based-for, and STL style iteration in general (containers must also support begin, end).
nonvirtual Iterator	operator+ (ptrdiff_t i) const
nonvirtual	operator bool () const
	return not AtEnd ()
nonvirtual bool	operator== (const Iterator &rhs) const
	Equals () checks if two iterators are equal to one another (point to the same position in the sequence).
nonvirtual const T &	Current () const
	Returns the value of the current item visited by the Iterator<T>, and is illegal to call if AtEnd()
nonvirtual bool	AtEnd () const
	AtEnd () means there is nothing left in this iterator (a synonym for (it == container.end ()).
nonvirtual void	reset ()
	Set to AtEnd and disassociate with owner.
nonvirtual void	clear ()
	Set to AtEnd and disassociate with owner.
nonvirtual IRep &	GetRep ()
	Get a reference to the IRep owned by the iterator. This is an implementation detail, mainly intended for implementors.
nonvirtual const IRep &	ConstGetRep () const
	Get a reference to the IRep owned by the iterator. This is an implementation detail, mainly intended for implementors.
nonvirtual void	Refresh ()
	Refresh the current iterator state based on what is in the underlying IRep.
nonvirtual void	Invariant () const noexcept
	Invariant does nothing if !qStroika_Foundation_Debug_AssertionsChecked, but if qStroika_Foundation_Debug_AssertionsChecked, checks internal state and asserts in good shape.

Static Public Member Functions
static constexpr default_sentinel_t	GetEmptyIterator () noexcept
	Used by someContainer::end ()

Detailed Description

template<typename T, Support::IIteratorTraits ITERATOR_TRAITS = Support::DefaultIteratorTraits<T>>
class Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >

An Iterator<T> is a copyable object which allows traversing the contents of some container.

@todo EXPLAIN HOW THIS IS CONNECTED TO c++20 'ranges'

An Iterator<T> is typically associated with some container (that is being iterated over) and which allows traversal from start to finish. (The iterator itself essentially provides a notion of start to finish).

There need not actually be a 'container' object. Other 'iterators' can be created, so long as they act like an iterator.

An Iterator<T> is a copyable object which can safely be used to capture (copy) the state of iteration and continue iterating from that spot.

An Iterator<T> be be thought of as (const) referencing a container (or other information source)

It is (since Stroika 2.1b14) illegal to use an iterator after its underlying container has been modified (rule as in STL, but unlike most STLs, Stroika will automatically detect such illegal use in debug builds).

Iterators CAN be used to MODIFY a container, but not directly - only by passing that iterator as an argument to a container method (such as Remove). Here the iterator cannot actually update the container but acts as an marker/indicator of what element to update. Such APIs will optionally return an updated iterator, so that you can continue with iteration (if desired).

Note

in Stroika 3.0d24, we renamed Done () to AtEnd (), and the old name is deprecated. PLUS, we HAD the rule that once at iterator was DONE, it could NEVER be UNDONE. But that rule is no longer in place. Bidirectional iterators that reach the end, can be moved backward to continue iterating backwards. This will still be often be true of ordinary iterators, but it may not be true for some.

PRIOR to Stroika 2.1b14 it was true that

  "If the underlying container is modified, the iterator will be automatically
  updated to logically account for that update. Iterators are robust in the presence
  of changes to their underlying container. Adding or removing items from a container
  will not invalidate the iteration."

  "Different kinds of containers can make further guarantees about the behavior of iterators
  in the presence of container modifications. For example a SequenceIterator will always
  traverse any items added after the current traversal index, and will never traverse items
  added with an index before the current traversal index.

  But this is NO LONGER TRUE.

Example Usage

for (Iterator<T> i = container.MakeIterator (); not i.AtEnd (); i.Next ())  {
    f (i.Current ());
}

or:

for (Iterator<T> i = container.begin (); i; ++i)  {
    f (*i);
}

or:

for (Iterator<T> i = container.begin (); i != container.end (); ++i)  {
    f (*i);
}

or:

for (T i : container)  {
    f (i);
}

Key Differences between Stroika Iterators and STL Iterators:

1.      Stroika iterators (in debug builds) will detect if they are used after
        the underlying container has changed (some STL's may do this too?)

2.      Stroika iterators carry around their 'AtEnd' state all in one object.
        For compatibility with existing C++ idiom, and some C++11 language features,
        Stroika iterators allow use of container.end() (or i == container.end())
        to check for if an iterator is AtEnd. But internally,
        Stroika just checks i.AtEnd(), and so can users of Stroika iterators.

3.      Stroika iterators are not 'random access' (see BidirectionalIterator, and RandomAccessIterator).
        They just go forwards, one step at a time.

4.      In STL, reverse iterators are a special type, incompatible with regular iterators.
        In Stroika, reverse iterators are also created with rbegin(), rend (), but
        their type is no different than regular iterators.
        <<<< NYI >>>>

Some Rules about Iterators:

 1.      Iterators can be copied. They always refer to the same
         place they did before the copy, and the old iterator is unaffected
         by iteration in the new iterator.

Interesting Design (Implementation) Notes:

-   We considered a design for Current() - where it would dynamically
    grab the current value, as opposed to being defined to be frozen/copied
    at the time of iteration.

    The advantage of the path not taken is that if you iterated several times without
    examining the current value, and if the cost of copying was relatively large, this
    definition would have worked out better.

    However, because I think its far more frequent that the copies are cheap, the
    user will want to look at each value, and the cost in terms of thread locking
    and probably virtual function calls, the current approach of freezing / copying
    on iteration seemed better.

Note

Design Note Until Stroika 2.1d6, Iterator<> used CopyOnWrite (COW) - SharedByValue, instead of unique_ptr.

SharedByValue costs a bit more when the iterators are never copied. But saves a lot of cost when iterators are copied (cuz with unique_ptr they need to actually be cloned).

I DID run some simple tests to see how often we even use the Clone method. It turns out - quite rarely. And most can be eliminated by slightly better Move constructor support on the iterator class.

Note

Requires Concepts: o copyable<T> o constructible_from<optional<T>, T>

Satisfies Concepts: o regular<Iterator<T>> // implies copyable/movable/equality_comparable o forward_iterator<Iterator<T>> o sentinel_for<default_sentinel_t, Iterator<T>>

See also

Iterable<T>

Note

Thread-Safety

    Iterator<T> instances are \em not thread-safe. That is - they cannot be read and
    or written from multiple threads at a time.

    However, given how Iterators are meant to be, and are typically, used, this presents
    no problem.

    They can be safely transferred across threads, and the underlying things being iterated over
    can be safely and transparently read/written from other threads

    <a href="Thread-Safety.md#C++-Standard-Thread-Safety">C++-Standard-Thread-Safety</a>

Definition at line 253 of file Iterator.h.

Member Typedef Documentation

iterator_category

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS = Support::DefaultIteratorTraits<T>>

using Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::iterator_category = forward_iterator_tag

iterator_category = forward_iterator_tag;

Note

The Stroika Iterator class models the forward_iterator concept. Prior to Stroika 3.0d24 this was a templated parameter, never really used.

(note - actually something between input_iterator and forward_iterator - must consider more?s)

Note

Prior to Stroika 3.0d24 we captured the iterator_category as a template parameter, but that caused problems with subclassing (eg. BidirectionalIterator, RandomAccessIterator) and the IRep type.

Definition at line 295 of file Iterator.h.

Constructor & Destructor Documentation

Iterator()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::Iterator ( const unique_ptr< IRep > &  rep )

noexcept

This overload is usually not called directly. Instead, iterators are usually created from a container (eg. Sequence<T>{}.begin()).

Iterators are safely copyable, preserving their current position.

CTOR overload taking nullptr - is the same as GetEmptyIterator ()

Note

since copy constructor calls Clone_, these can throw exceptions but move copies/assignments are no-except

for ranges to work, the return type of Iterable<T>::end () must be a 'sentinel_for' compatible concept which implies it must be default constructible. So interpret default construction of Iterator as meaning empty/end sentinel.

Precondition

RequireNotNull (rep.get ())

Note

constructor with argument default_sentinel_t - creates an end iterator

Definition at line 41 of file Iterator.inl.

Member Function Documentation

operator*()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

const T & Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::operator*

(

)

const

Return the Current value pointed to by the Iterator<T> (same as Current())

Support for range-based-for, and STL style iteration in general (containers must also support begin, end).

This function is a synonym for Current();

Note

Until Stroika 2.1r1, this returned T, and was switched to return const T& on the theory that it might perform better, but testing has not confirmed that (though this does appear to be existing practice in things like STL).

It is illegal (but goes undetected) to hang onto (and use) the reference returned past when the iterator is next modified

use of for (auto& c : Iterable<>) won't work with Stroika Iterator<> classes since operator* returns const reference only as we don't allow updating containers by fiddling with the iterator only.

Definition at line 159 of file Iterator.inl.

operator->()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

auto Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::operator->

(

)

const

Return a pointer to the current value pointed to by the Iterator<T> (like Current())

This function allows you to write i->b, where i is an iterator and b is a member of the type iterated over by i.

Note - the lifetime of this pointer is short - only until the next operation on the wrapper class instance Iterator<T>.

Definition at line 167 of file Iterator.inl.

operator++()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

auto Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::operator++

(

)

Advance iterator; support for range-based-for, and STL style iteration in general (containers must also support begin, end).

Advance iterator; support for range-based-for, and STL style iteration in general (containers must also support begin, end).

operator++ can be called anytime as long as AtEnd () is not true (must be called prior to operator++). It then it iterates to the item in the container (i.e. it changes the value returned by Current).

Note - the value return by Current() is frozen (until the next operator++() call) when this method is called. Its legal to update the underlying container, but those values won't be seen until the next iteration.

Note

As of Stroika v3.0d1, we again support post-increment (operator++ (int)), NOT because its useful, but because its required by std+c++ to be considered an input iterator (see https://en.cppreference.com/w/cpp/iterator/weakly_incrementable).

It is slower, and not recommended. BUT because of this - supported.

Definition at line 175 of file Iterator.inl.

operator+()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

Iterator< T, ITERATOR_TRAITS > Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::operator+

(

ptrdiff_t

i

)

const

Precondition

operator++ can be called 'i' times (on a copy of this), and the result returned.

Note

don't use unsigned 'i' because that works less well with overloads and ambiguity.

similar to std::advance, but allows for simpler usage (i + n) \req i >= 0

Definition at line 191 of file Iterator.inl.

operator bool()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::operator bool ( ) const

explicit

return not AtEnd ()

Design Note: I HATE type punning - which this is. And I may want to lose this.

However, this API works beautifully with Iterable<>::Find - and perhaps other things that return iterators.

also, it allows Iterator<T> n = ...; while (n) { } not sure that's better than while (not n.AtEnd ())???

Definition at line 202 of file Iterator.inl.

operator==()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

bool Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::operator==

(

const Iterator< T, ITERATOR_TRAITS > &

rhs

)

const

Equals () checks if two iterators are equal to one another (point to the same position in the sequence).

NB: Equals () is the same notion of equality as used by STL iterators.

NB: It is

Precondition

required that the two iterators being compared must come from the same source, or from the special source nullptr.

Very roughly, the idea is that to be 'equal' - two iterators must be iterating over the same source, and be up to the same position. The slight exception to this is that any two iterators that are AtEnd() are considered Equals (). This is mainly because we use a different representation for 'AtEnd' iterators.

Note - for Equals. The following assertion will succeed:

    Iterator<T> x = getIterator();
    Iterator<T> y = x;
    x++;
    y++;
    Assert (Equals (x, y));     // assume x and y not already 'at end' then...
                                // will always succeed (x++ and y++ )

However, Iterator<T> x = getIterator(); Iterator<T> y = x; x++; modify_underlying_container() y++; if (Equals (x, y)) { may or may not be so }

Note that Equals is commutative.

Definition at line 207 of file Iterator.inl.

Current()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

const T & Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::Current

(

)

const

Returns the value of the current item visited by the Iterator<T>, and is illegal to call if AtEnd()

Current () returns the value of the current item visited by the Iterator<T>.

Only one things can change the current value of Current(): o any non-const method of the iterator

Two subsequent calls to it *cannot return different values with no intervening (non-const) calls on the iterator.

Precondition

not AtEnd ()

operator*() is a common synonym for Current().

See also

operator*()

operator++()

Note

Until Stroika 2.1r1, this returned T, and was switched to return const T& on the theory that it might perform better, but testing has not confirmed that (though this does appear to be existing practice in things like STL).

It is illegal (but goes undetected) to hang onto (and use) the reference returned past when the iterator is next modified

IRep::Current () returns optional<T>, and can be called while AtEnd

Definition at line 135 of file Iterator.inl.

AtEnd()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

bool Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::AtEnd

(

)

const

AtEnd () means there is nothing left in this iterator (a synonym for (it == container.end ()).

AtEnd () means there is nothing left to visit in this iterator.

When an iterator is AtEnd(), it is illegal to call Current().

Calling AtEnd() may change (initialize) the value which would be returned by the next call to Current().

NB: There are *no* modifications to an underlying container which will directly change
the value of AtEnd(). This value only changes the next time the cursor is advanced
via a call to operator++();

if it comes from container, then (it == container.end ()) is true iff it.AtEnd()

Definition at line 143 of file Iterator.inl.

reset()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

void Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::reset

(

)

Set to AtEnd and disassociate with owner.

Equivalent to *this = GetEmptyIterator();

Aliases

clear ()

Definition at line 149 of file Iterator.inl.

clear()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

void Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::clear

(

)

Set to AtEnd and disassociate with owner.

Equivalent to *this = GetEmptyIterator();

Aliases

reset ()

Definition at line 154 of file Iterator.inl.

GetEmptyIterator()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

constexpr default_sentinel_t Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::GetEmptyIterator ( )

staticconstexprnoexcept

Used by someContainer::end ()

GetEmptyIterator () returns a special iterator which is always empty - always 'at the end'. This is handy in implementing STL-style 'if (a != b)' style iterator comparisons.

Note

this is something like the c++20 ranges sentinel idea, except that we don't use a separate type (perhaps a mistake on my part).

Definition at line 243 of file Iterator.inl.

GetRep()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

Iterator< T, ITERATOR_TRAITS >::IRep & Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::GetRep

(

)

Get a reference to the IRep owned by the iterator. This is an implementation detail, mainly intended for implementors.

Get a reference to the IRep owned by the iterator. This is an implementation detail, mainly intended for implementors.

Definition at line 107 of file Iterator.inl.

Refresh()

template<typename T , Support::IIteratorTraits ITERATOR_TRAITS>

void Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >::Refresh

(

)

Refresh the current iterator state based on what is in the underlying IRep.

Useful when you change the rep directly. This should VERY RARELY be needed - just in implementing iterator patching (say during a remove).

Definition at line 119 of file Iterator.inl.

---

The documentation for this class was generated from the following files:

• Iterator.h
• Iterator.inl