In article <37ECCB17.BCD8782A@ihug.co.nz>, Ross Smith <ross.s@ihug.co.nz> wrote:

> "James Kuyper Jr." wrote:
> >
> > The standard does say that if a container is empty, then begin() and
> > end() compare equal. However, something I haven't found is the reverse
> > statement: that if begin()==end(), the container must be empty. I was
> > wondering about this, because I was thinking about defining a
> > CircularList<> container, similar to std::list<>, but with the property
> > that begin() ie always equivalent to end(). An empty CircularList can be
> > recognized either by checking size(), or testing whether begin()==
> > CircularList::iterator(). All algorithms working on such a container
> > would have to perform that check.
> >
> > Such a container could meet all of the sequence requirements given in
> > section 23.1.1, including the same optional requirements that
> > std::list<> is required to meet, but I wouldn't expect any standard
> > library function that takes iterator range arguments to work properly
> > when given a range of [circlist.begin(), circlist.end()). Annoying.
>
> My solution to that was to have begin() return a special "magic value"
> iterator that dereferences to the same element as end() but doesn't
> compare equal to it.

I haven't had any problem with this.

Here is a *very* simple intrusive circular doubly-linked list that
illustrates the important points (I compiled and ran it too). The property
I like about it is that there are no "if" statements in its
implementation.


struct Link {
    Link* next;
    Link* prev;
};

template<class T>
class List {
    Link list;
public:
    List() {
        list.next = &list;
        list.prev = &list;
    }

    class iterator {
        Link* cur;
        iterator( Link* l ) : cur( l ) { }
        friend class List<T>;
    public:
        T* operator -> () { return static_cast<T*> (cur); }

        iterator& operator ++ () {
            cur = cur->next;
            return *this;
        }

        friend bool operator == ( iterator const& x, iterator const& y ) {
            return x.cur == y.cur;
        }

        friend bool operator != ( iterator const& x, iterator const& y ) {
            return x.cur != y.cur;
        }
    };

    iterator begin() const { return list.next; }
    iterator end() const   { return const_cast<Link*> (&list); }

    void insert( T* t, iterator next ) {
        Link* l = t;
        l->prev = next.cur->prev;
        next.cur->prev = l;
        l->prev->next = l;
        l->next = next.cur;
    }

    void erase( iterator pos ) {
        pos.cur->prev->next = pos.cur->next;
        pos.cur->next->prev = pos.cur->prev;
    }
};

// demo/test

struct Foo : Link {
    char val;
    Foo( char c ) : val( c ) { }
};

void check_list( List<Foo> const& list, char const* expected ) {
    for ( List<Foo>::iterator cur( list.begin() ); cur != list.end(); ++cur )
        assert( cur->val == *expected++ );
    assert( *expected == '\0' );
}

int main() {
    List<Foo> list;
    check_list( list, "" );
    assert( list.begin() == list.end() );
    list.insert( new Foo( '1' ), list.begin() );
    check_list( list, "1" );
    assert( list.begin() != list.end() );
    list.insert( new Foo( '2' ), list.begin() );
    check_list( list, "21" );
    list.insert( new Foo( '3' ), list.end() );
    check_list( list, "213" );
    list.erase( list.begin() );
    check_list( list, "13" );
    List<Foo>::iterator i( list.begin() );
    ++i;
    list.erase( i );
    check_list( list, "1" );
    list.erase( list.begin() );
    check_list( list, "" );
}


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Ross Smith wrote:
>
> "James Kuyper Jr." wrote:
> >
> > I was wondering about this, because I was thinking about defining a
> > CircularList<> container, similar to std::list<>, but with the property
> > that begin() ie always equivalent to end().
> >
> > Such a container could meet all of the sequence requirements given in
> > section 23.1.1, including the same optional requirements that
> > std::list<> is required to meet, but I wouldn't expect any standard
> > library function that takes iterator range arguments to work properly
> > when given a range of [circlist.begin(), circlist.end()). Annoying.
>
> My solution to that was to have begin() return a special "magic value"
> iterator that dereferences to the same element as end() but doesn't
> compare equal to it.

If anything, the end() iterator should be "magic", because one normally
doesn't expect to be able to dereference end().

--

Ciao,                       Paul D. DeRocco
Paul                        mailto:pderocco@ix.netcom.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Aldo Aleardi wrote:
>
> If an empty range [i,i), where i is a valid dereferenceable iterator,
> is a valid range, can I assume that passing it to functions in the
> standard library is always a no-op or in some cases this will result
> in undefined behavior?

An empty range is valid. Notice that min_element and max_element, which are
logically meaningless if given two identical iterators representing an
empty range, return that iterator in this case, which can't necessarily be
dereferenced.

--

Ciao,                       Paul D. DeRocco
Paul                        mailto:pderocco@ix.netcom.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Colin Rafferty wrote:
>
> Aldo Aleardi writes:
>
> > 6
> > An iterator j is called reachable from an iterator i if and only if
> > there is a finite sequence of applications of the  expression
> >  ++i that makes i == j.
>
> > 7
> > ....A range [i, i) is an empty range; ....
>
> > ....Range [i, j) is valid if and only if j is reachable from i.
>
> > I cannot understand from the above statements if an empty range
> > is a valid range.
>
> It is a valid range.  As described in (6), there is a finite sequence
> of applications of the expressoin ++i that makes i == i.
>
> Specifically, it takes zero applications of ++i.
>
> Another way to convince yourself that [i, i) is valid is because an
> empty vector's begin() and end() are the same iterator, and you should
> certainly be able to assume that it is legal to use them.

The standard does say that if a container is empty, then begin() and
end() compare equal. However, something I haven't found is the reverse
statement: that if begin()==end(), the container must be empty. I was
wondering about this, because I was thinking about defining a
CircularList<> container, similar to std::list<>, but with the property
that begin() ie always equivalent to end(). An empty CircularList can be
recognized either by checking size(), or testing whether begin()==
CircularList::iterator(). All algorithms working on such a container
would have to perform that check.

Such a container could meet all of the sequence requirements given in
section 23.1.1, including the same optional requirements that
std::list<> is required to meet, but I wouldn't expect any standard
library function that takes iterator range arguments to work properly
when given a range of [circlist.begin(), circlist.end()). Annoying.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Aldo Aleardi writes:

> 6
> An iterator j is called reachable from an iterator i if and only if
> there is a finite sequence of applications of the  expression
>  ++i that makes i == j.

> 7
> ....A range [i, i) is an empty range; ....

> ....Range [i, j) is valid if and only if j is reachable from i.

> I cannot understand from the above statements if an empty range
> is a valid range.

It is a valid range.  As described in (6), there is a finite sequence
of applications of the expressoin ++i that makes i == i.

Specifically, it takes zero applications of ++i.

Another way to convince yourself that [i, i) is valid is because an
empty vector's begin() and end() are the same iterator, and you should
certainly be able to assume that it is legal to use them.

> If an empty range [i,i), where i is a valid dereferenceable iterator,
> is a valid range, can I assume that passing it to functions in the
> standard library is always a no-op or in some cases this will result
> in undefined behavior?

You can assume neither.

You cannot assume that it is a no-op, becaues the standard doesn't say
that this optimization is required.

You cannot assume that it will result in undefined behavior, because
it is a valid range.

--
Colin
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

from ISO/IEC 14882:1998(E)
24.1 Iterator requirements                   24 Iterators library

....
6
An iterator j is called reachable from an iterator i if and only if
there is a finite sequence of applications of the  expression
 ++i that makes i == j. If j is reachable from i, they refer to the
same container.

7
 Most of the library's algorithmic templates that operate on data
structures have interfaces that use ranges.
A range is a pair of iterators that designate the beginning and end of
the computation. A range [i, i) is an empty range; in general, a range
[i, j) refers to the elements in the data structure starting with the
one pointed to by i and up to but not including the one pointed to by
j. Range [i, j) is valid if and only if j is reachable from i. The
result of the application of functions in the library to invalid
ranges is undefined.
....

I cannot understand from the above statements if an empty range
is a valid range.

If an empty range [i,i), where i is a valid dereferenceable iterator,
is a valid range, can I assume that passing it to functions in the
standard library is always a no-op or in some cases this will result
in undefined behavior?

TIA, Aldo.


--
Is everybody in? Is everybody in?
The ceremony is about to begin.

                        (Jim Morrison)
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]