[Dune-devel] Random-Access Iterators

[Oliver Sander]

Hi,
I would really expect property b):

> (b) you could also want to write
>     gridView.begin() + gridView.indexSet().index( entity )
>     to obtain an iterator to "entity"

I think people will assume this implicitly, and get confused if it doesn't hold.
On the other hand it cannot hold with mixed-element grids.  This for me is another
point against random-access iterators.


> 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.

Everything in a UG level view is stored in linked lists.  There is no way to implement
random access here.

Cheers,
Oliver


> 
> 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
>>
> 


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 473 bytes
Desc: OpenPGP digital signature
URL: <https://lists.dune-project.org/pipermail/dune-devel/attachments/20141001/db3c5f0c/attachment.sig>