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. It is like an std::const_iterator. 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 = typename ITERATOR_TRAITS::iterator_category
	iterator_category = typename ITERATOR_TRAITS::iterator_category;

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. Bag<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++ ()
	preincrement
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 Done()
nonvirtual bool	Done () const
	Done () means there is nothing left in this iterator (a synonym for (it == container.end ()).
nonvirtual void	reset ()
	Set to done and disassociate with owner.
nonvirtual void	clear ()
	Set to done 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	Invariant () const noexcept
	, 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, typename ITERATOR_TRAITS = DefaultIteratorTraits<forward_iterator_tag, T>>
class Stroika::Foundation::Traversal::Iterator< T, ITERATOR_TRAITS >

An Iterator<T> is a copyable object which allows traversing the contents of some container. It is like an std::const_iterator.

@todo EXPLAIN HOW THIS IS CONNECTED TO c++20 'range' and probably make this work with 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

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.Done (); 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 'done' state all in one object.
        For compatibility with existing C++ idiom, and some C++11 language features
        Stroika iterators inherit from std::iterator<> and allow use of end(),
        and i != end() to check for if an iterator is done. But internally,
        Stroika just checks i.Done(), and so can users of Stroika iterators.

3.      Stroika iterators are not 'random access'. They just go forwards, one step at a
        time. In STL, some kinds of iterators act more like pointers where you can do
        address arithmetic.
        <<<< RETHINK - WE WANT BIDIITERATOR/ETC>>>>

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

Satisfies Concepts: o static_assert (regular<Iterator<T>>); o static_assert (input_iterator<Iterator<T>>); o static_assert (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 225 of file Iterator.h.

Constructor & Destructor Documentation

Iterator()

template<typename T , typename 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. Bag<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 ())

Definition at line 41 of file Iterator.inl.

Member Function Documentation

operator*()

template<typename T , typename 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 163 of file Iterator.inl.

operator->()

template<typename T , typename 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 171 of file Iterator.inl.

operator++()

template<typename T , typename ITERATOR_TRAITS >

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

(

)

preincrement

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 Done () 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 179 of file Iterator.inl.

operator==()

template<typename T , typename 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 Done() are considered Equals (). This is mainly because we use a different representation for 'done' iterators.

@TODO - NOTE - SEE TODO ABOUT ABOUT THIS GUARANTEE??? - NO - TOO STRONG - REVISE!!!

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 211 of file Iterator.inl.

Current()

template<typename T , typename 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 Done()

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.

The value of returned is undefined (Assertion error) if called when Done().

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

Definition at line 139 of file Iterator.inl.

Done()

template<typename T , typename ITERATOR_TRAITS >

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

(

)

const

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

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

Once an iterator is Done(), it can never transition to 'not Done()'.

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

Calling Done() 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 Done(). 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.Done()

Definition at line 147 of file Iterator.inl.

reset()

template<typename T , typename ITERATOR_TRAITS >

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

(

)

Set to done and disassociate with owner.

Equivalent to *this = GetEmptyIterator();

Aliases

clear ()

Definition at line 153 of file Iterator.inl.

clear()

template<typename T , typename ITERATOR_TRAITS >

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

(

)

Set to done and disassociate with owner.

Equivalent to *this = GetEmptyIterator();

Aliases

reset ()

Definition at line 158 of file Iterator.inl.

GetEmptyIterator()

template<typename T , typename 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 247 of file Iterator.inl.

GetRep()

template<typename T , typename 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 112 of file Iterator.inl.

ConstGetRep()

template<typename T , typename ITERATOR_TRAITS >

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

(

)

const

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 118 of file Iterator.inl.

---

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

• Iterator.h
• Iterator.inl