Re: [boost] [iterators] Proof-of-concept for a sentinel iterator adapter

Subject: Re: [boost] [iterators] Proof-of-concept for a sentinel iterator adapter
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-05-13 17:44:45

AMDG

Simonson, Lucanus J wrote:
> Steven Watanabe wrote:
>   
>> template<class T, class Sentinel>
>> class sentinel_iterator {
>> public:
>>     sentinel_iterator(T* ptr, Sentinel s = Sentinel());
>>     sentinel_iterator& operator++() {
>>         ++data.first();
>>         if(data.second()(*data.first())) data.first() = 0;
>>     }
>>     //...
>> private:
>>     boost::compressed_pair<T*, Sentinel> data;
>> };
>>     
>  
> Hmm, if Sentinel can't be optimized away at compile time then we don't want to copy it around when we pass the iterator by value.  Similarly, we don't want to cast it by value every time it is checked as in my earlier code.  Instead we want to enable the static const optimization Beman had in mind.  To do this I changed the casting operator of the struct I provide as the sentinel parameter to cast to a const reference instead of T by value.  The sentinel_iterator itself stays the same as it was in my previous posting.
>   

Ok. In that case just change my code to create the Sentinel on demand.
As long as the Sentinel is an empty class (for example if its operator() 
compares
to a global constant...) then the storage will be optimized away by 
compressed_pair,
using EBO.

> static const int sc_val = -1; 
> struct s_val {
>         operator const int& () const { return sc_val; }
> };
>
> In this way the user can provide a static const reference as the template parameter for the sentinel value if they feel the need for such optimization.  If it is an iterator over objects that are expensive to copy or default construct you would not want to cast by value or default construct the sentinel value in the iterator.
>   

The use of implicit conversions is not quite bulletproof, as it can
fail in cases like this:

template<class T>
class C;

template<class T1, class T2>
bool operator==(const C<T1>&, const C<T2>&);

or like this

class C {
    template<class T>
    C(const T&);
};

You can try to get around this problem by defining your own
comparison operators, but...

// try to define a generic static sentinel
template<class T>
struct static_value {
    operator const T&() const { return(value); }
    static const T value;
};
template<class T>
const T static_value<T>::value = T();
template<class T>
bool operator==(const static_value<T>&, const T&);

// now create a class
class C:
// Let's define a generic comparison operator...
template<class T>
bool operator==(const T&, const C&);

// and this breaks because of the ambiguity
sentinel_iterator<T, static_value<T> > it;

Of course this can be fixed by adding a more specialized
overload just for C, but seems easier to not use operator== at all.

Trying to bypass the problem by explicitly casting in sentinel_iterator
is less than ideal, because it requires that the test to use equality for
the value_type, rather than some other arbitrary operation.

In Christ,
Steven Watanabe