[Dune-devel] Random-Access Iterators

[Martin Nolte]

Hi all,

this is a very interesting discussion, especially as people start mixing 
different meanings of "Random Access Iterator":

(a) for structured grids, you could say random access means writing
     something like
	 (it + x_axis_increment( k ))
     or something like that.
(b) you could also want to write
     gridView.begin() + gridView.indexSet().index( entity )
     to obtain an iterator to "entity"
(c) for the STL, a random access iterator just provides array-like access to 
elements in a range [begin,end) or the distance (it - begin).

Please add to the list if I omitted a point of view. A second interesting 
question is their usefulness, which evidently depends on their meaning in the 
first place.

 From my point of view, (a) is not really an option. If we want a special 
concept for structured grids, this will include much more that just walking in 
the direction of an axis and should be discussed separately.

As for (b): I do not understand the semantics. ALUGrid guarantees this, too 
without being able to provide random access iterator in the sense of the STL. 
On the other hand, I might want to index a structured grid in a different 
order from the iterator (e.g., to improve a matrix layout). We could, however, 
add a suitable "capability", if desired.

The STL semantics, however, are just a potential performance gain the user can 
exploit if the container provides it. The question here is: Do we want our 
interface to enforce the slower iterator type or are we willing to forward the 
"faster" iterator, if provided? Moreover, this has nothing to do with a 
structured / unstructured discussion. The macro grids in Alberta and ALU are 
stored in array-like structures and, thus, allow for random access in the 
sense of (c). Implementations storing all levels in an array-like structure 
(e.g., UG?) could even provide random access iterators for all level views.

On the other side of the discussion, I have to agree that random access 
iterators are hardly ever needed. For thread parallelism, you can usually 
afford to iterate once over the grid and remember ever n-th iterator (i.e., 
the begin iterator of the n-th subrange). Other uses for random access 
iterators are divide-and-conquer algorighms (e.g., binary_search), which do 
not seem to have much use on unstructured or even structured multi-d grids. 
One further thing that I can imaging is an integral (i.e., orderable) entity 
seed, if you only look in one grid view: Use s = (it - begin) as entity seed 
and reobtain the entity by *(begin + s).

As the work has already been done, it boils down to the question: Do we want 
to protect the user from himself? For me, the answer is no, but I know that 
some developers disagree on this.

Finally, I suggest to postpone this discussion as a 3.0 (or later) feature, 
because once we no longer return references to entities, we can implement the 
full interface without additional tricks. As noone seems to have real need for 
them right now and opinions seem to diverge, it might otherwise just become a 
useless show stopper for 2.4.

Best,

Martin




On 10/01/2014 02:30 PM, Christian Engwer wrote:
> Hi Andreas,
>
>> One question:
>> is it supposed to be guaranteed by the proposal that if an element K has
>> index k then
>> it[k] would give me that element? There might be some use case for
>> easily going from index to element although
>> I haven't really come up with an example. But I guess that wouldn't
>> really be guaranteed anyway because that would
>> mean that one always iterates over the grid in the order of incrementing
>> index.
>
> I think this would be a reasonable requirement. We don't require this
> for arbitrary meshes, but for meshes with random access I think it
> would be very useful to have this property. It would also imply that
> we iterate in the order of indices and it would result in better
> locality of our algorithms.
>
> Christian
>
> _______________________________________________
> Dune-devel mailing list
> Dune-devel at dune-project.org
> http://lists.dune-project.org/mailman/listinfo/dune-devel
>

-- 
Dr. Martin Nolte <nolte at mathematik.uni-freiburg.de>

Universität Freiburg                                   phone: +49-761-203-5630
Abteilung für angewandte Mathematik                    fax:   +49-761-203-5632
Hermann-Herder-Straße 10
79104 Freiburg, Germany