Re: [boost] [iterator] counting_iterator and reverse iterator problem (was: [graph][iterators] csr graph and reverse iterator problem)

Subject: Re: [boost] [iterator] counting_iterator and reverse iterator problem (was: [graph][iterators] csr graph and reverse iterator problem)
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-09-09 11:29:14

On Fri, 9 Sep 2011, Takatoshi Kondo wrote:

>
> On Thu, 8 Sep 2011 14:31:10 -0400 (EDT)
> Jeremiah Willcock <jewillco_at_[hidden]> wrote:
>
>> On Thu, 8 Sep 2011, Takatoshi Kondo wrote:
>>
>>> Hi,
>>>
>>> On Thu, 8 Sep 2011 07:48:01 +0900
>>> Michel Morin <mimomorin_at_[hidden]> wrote:
>>>
>>>> Relevant ticket (#2640):
>>>>   https://svn.boost.org/trac/boost/ticket/2640
>>>>   Legal forward iterators cannot store their referents
>>>>   (was: counting_iterator::reference lifetime tied to iterator)
>>>
>>> Thanks, I've understood what is the problem.
>>> I think that when we write a generic algrithm using reverse_iterator
>>> or make own iterator using counting_iterator, we should refer to this
>>> problem in comment.
>>>
>>> Anyway my problem has solved. Thanks again :)
>>
>> One further note -- there is nothing in the BGL requirements that states
>> that vertex_iterators need to be bidirectional, so you cannot rely on that
>> being true for arbitrary graph types (see
>> http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/VertexListGraph.html).
>
> Thanks for the advice. I read the document. My understanding is that
> concept check's purpose is to constrain the custom containers.
> e.g.
> http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/using_adjacency_list.html#sec:custom-storage
>
> If the custom container doesn't satisfy the concept, compile error would occur.
> I believe when I choose the container that has random access iterator for VertexList,
> I can rely on the function vertices(g) returns a pair of random access iterator.
> Am I wrong?

Yes, you are right, but whether the iterator is random access is an 
implementation detail.

> But in the case of compressed_sparse_row_graph, we can't pass
> the template parameter as a container selector.The iterator's
> capability depend on implementation. But it's detail of implementation.
>
> Hmm...
> Should we only rely on MultiPassInputIterator capability?

I think that would be better.  Is there some reason you need a 
reverse_iterator on top?

-- Jeremiah Willcock