This chapter is from the book
This chapter is from the book
This chapter is from the book
42.5 stlsoft::filter_iterator
There's a fair bit to do in this class, so we'll tackle iterator refinements in a stepwise fashion. We'll start with input and forward iterators.
42.5.1 Forward Iterator Semantics
The handling of forward iterator semantics is shown in Listing 42.2.
Listing 42.2. Definition of filter_iterator Supporting Forward Iteration
template< typename I // The underlying iterator
, typename P // The unary predicate that will select the items
, typename T = adapted_iterator_traits<I>
>
class filter_iterator
{
public: // Member Types
. . . // All usual member types, most via T (adapted_iterator_traits)
public: // Construction
filter_iterator(I begin, I end, P pr)
: m_it(begin)
, m_end(end)
, m_pr(pr)
{
for(; m_it != m_end; ++m_it)
{
if(m_pr (*m_it))
{
break;
}
}
}
public: // Forward Iterator Methods
class_type& operator ++()
{
STLSOFT_MESSAGE_ASSERT( "Attempting to increment an endpoint
iterator", m_it != m_end);
for(++m_it; m_it != m_end; ++m_it)
{
if(m_pr(*m_it))
{
break;
}
}
return *this;
}
class_type& operator ++(int); // Canonical implementation
effective_reference operator *()
{
return *m_it;
}
effective_const_reference operator *() const; // Same as operator *()
effective_pointer operator ->()
{
enum { is_iterator_pointer_type
= is_pointer_type<base_iterator_type>::value };
typedef typename
value_to_yesno_type<is_iterator_pointer_type>::type yesno_t;
return invoke_member_selection_operator_(yesno_t());
}
effective_const_pointer operator ->() const; // Same as operator ->()
. . .
private: // Member Variables
I m_it;
I m_end;
P m_pr;
};
All member types are defined in terms of those provided by adapted_iterator_traits (just as is the case with index_iterator, described on the CD). The constructor takes the [begin, end) iterator pair defining the iterable range, followed by the predicate used for filtering. Note that the predicate comes last, as a reminder that defaulting the endpoint iterator is a crazy thing to attempt.
The constructor has to assume that the given base iterator instance specifying the start of the iterable range may not be one acceptable to the filter predicate and so tests it, possibly incrementing until finding one that is. Contrast this with the implementation of operator ++(), which knows that the current iteration point is acceptable to the filter and increments before it starts the loop. This is because the user must have previously tested it against the known endpoint filtered instance. This follows the basic idiom in STL that an iterator is determined to be viable by testing its equality against one that is known to not be.
The necessity to move to an acceptable point in the iteration implies the curious relationship whereby different start point iterators evaluate, in their filtered form, to be the same. Consider the sequence of integers 0, 2, 4, 5, 6, 7, 8, 9. Using a filter, is_odd, which selects odd numbers, there are several ways to specify equivalent iterators:
int ints[] = { 0, 2, 4, 5, 6, 7, 8, 9 };
stlsoft::filter(&ints[0], &ints[0] + 8, is_odd()); // Is equivalent to:
stlsoft::filter(&ints[1], &ints[0] + 8, is_odd()); // this
stlsoft::filter(&ints[2], &ints[0] + 8, is_odd()); // and this
stlsoft::filter(&ints[3], &ints[0] + 8, is_odd()); // and this
Each of the iterators in that case actually refers to the element at index 3, whose value is 5, since that's the first one in the series that has an odd value.
The remainder of the implementation shown is entirely normal, given what we learned in Section 36.4.5 about handling the member selection operator. So far, so good.
42.5.2 Bidirectional Iterator Semantics
I expect you're ahead of me here. Given the current member variables, we cannot implement bidirectional iterator semantics because we stand the same risk of stepping outside the iterable range as discussed in Section 42.2, only this time we would step out of the beginning rather than the end. The remedy in this case is to remember the starting point. Hence, we add another member variable of the base iterator type, m_begin, and adjust the implementation of the constructor accordingly, as shown in Listing 42.3.
Listing 42.3. Member Variables Supporting Bidirectional Iteration
template <typename I, typename P, typename T>
class filter_iterator
{
. . .
public: // Construction
filter_iterator(I begin, I end, P pr)
: m_it(begin)
, m_begin(begin)
, m_end(end)
, m_pr(pr)
{
. . .
}
. . .
private: // Member Variables
I m_it;
I m_begin;
I m_end;
P m_pr;
};
Using this member, the implementation of the bidirectional iterator methods is surprisingly simple, as shown in Listing 42.4.
Listing 42.4. Predecrement Operators
. . .
public: // Bidirectional Iterator Methods
class_type& operator --()
{
STLSOFT_MESSAGE_ASSERT( "Attempting to increment an endpoint
iterator", m_it != m_begin);
for(--m_it; m_it != m_begin; --m_it)
{
if(m_pr(*m_it))
{
break;
}
}
return *this;
}
class_type& operator --(int); // Canonical implementation
. . .
Now we can enumerate forwards as well as backwards:
template <typename I>
void fn(I from, I to)
{
++it;
--it;
}
struct is_odd;
int ints[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
fn(stlsoft::filter(&ints[0], &ints[0] + 8, is_odd())); // Well-formed
42.5.3 Random Access Iterator Semantics
This one is very simple. There's no reasonable way to implement random access iterator semantics in a filtering iterator, so we don't do it. The only conceivable way would be extremely expensive since each apparent random access operation would involve an element-by-element iteration to identify which elements match the predicate. Even if this weren't the case, I simply can't conceive of a scenario in which random access filtering is meaningful. I may be wrong, of course, in which case please write to me and disabuse me of my erroneous assumptions.