[Dune-devel] Random-Access Iterators
Jö Fahlke
jorrit at jorrit.de
Wed Oct 1 15:10:27 CEST 2014
Am Wed, 1. Oct 2014, 10:28:33 +0200 schrieb Markus Blatt:
> Date: Wed, 1 Oct 2014 10:28:33 +0200
> From: Markus Blatt <markus at dr-blatt.de>
> To: dune-devel at dune-project.org
> Subject: Re: [Dune-devel] Random-Access Iterators
> X-No-Auth: unauthenticated sender
> X-No-Relay: not in my network
> User-Agent: Mutt/1.5.21 (2010-09-15)
> X-Spam-Flag: No
> X-Envelope-From: <markus at dr-blatt.de>
>
> Hi Jö,
>
> On Tue, Sep 30, 2014 at 11:17:28PM +0200, Jö Fahlke wrote:
> > Hi!
> >
> > The random-access entity iterators are now ready for general review.
> > https://cgit.dune-project.org/repositories/dune-grid/log/?h=feature/random-access-entity-iterators
> >
>
> from a quick glance there seems to be something fishy with the
> comparison operators. For operator<(o) you seem to test whether
> distanceTo(o) is less than zero. Ergo a<b <=> b-a<0. Shouldn't this be
> the other way around?
Um, I have the sense of distanceTo() reversed compared with the iterator
facades. I'll change that for consistency.
> This brings me directly to the next point. Is there a special reason
> not to use the iterator facades? These are already tested and might
> help prevent the above mistakes. In addition it would reduce
> replication of boilerplate code and increase maintainability.
Three, actually:
- EntityIterator derives from EntityPointer, and as long as that is still
around I don't want to change that. But to use the iterator facades I also
need to derive from them. But then there are two base classes providing
e.g. operator*().
- Also because of EntityPointer: it holds the iterator implementation as
member. However, the iterator facades access the implementation methods as
asImp().increment();
not as
asImp().realIterator.increment();
Now I could implement all the implementation methods on EntityIterator to
forward to the realIterator member. But then I would have to provide
different versions of EntityIterator, one for each category of iterator I
want to implement. Pretty much what I do now with EntityIteratorBase, just
with some IteratorFacades mixed in to complicate the ancestry even further.
I feel that would be too complicated to understand half a year later, and
thus make this difficult to maintain.
- Whenever I implemented an iterator with the iterator facades I was unable to
hide the implementation methods from the user, i.e. by making them private.
It *should* be possible by making the iterator facade a friend of the
implementation, but I never managed to get that to work properly[1], so this
time I did not even try. *Why* do I want to hide the implementation methods
from the user? Well, normally I would not care so much, but the
EntityIterator is a facade class, and we have a history of beeing very
conservative when it comes to expose implementation details on those.
[1] Possibly due to a compiler bug with friend declarations. I don't remeber
the details, maybe it is fixed now. Still the iterator facade
documentation
<http://www.dune-project.org/doc/doxygen/html/group__IteratorFacades.html#_details>
does make all implementation methods public...
> > @Carsten: are you willing to include this in 2.4, provided noone finds any
> > serious issues?
> >
>
> Will this put a lot of work onto grid maintainers?
None whatsoever. Unless the maintainer wants to make his iterators
random-access, of course.
> > [...]
> >
> > There is one function that has been omitted from random access iterators for
> > the time being, namely operator[]. There are three possibilities for the
> > return type of operator[]: Either return the entity by value -- but that needs
> > copyable entities, which are not ready yet. Or return a reference to the
> > entity -- not possible, since we have nothing that stores that entity. Or
> > return a proxy object -- but I'm too lazy to implement that, since we will
> > have copyable entities soon. Note that instead of the (currently) invalid
> > expression "it[n]" you can write "*(it+n)": The + creates a temporary
> > iterator that holds the entity.
> >
>
> They are supposed to return the reference_type as defined in the
> iterator_traits. This might also be a proxy object. IMHO it is
> problematic to say something is a random access iterator but at the
> same time omit implementing the full functionality. This means that
> many of the STL algorithms are not usable with it and prevents people
> from getting some parallel speedup just by using parallel versions of
> it. (I know that we still tend to write raw loops mostly but that
> might be worse improving anyhow)
Strictly, the return type must be "convertible to reference". value_type is
"const Entity", reference is thus "const Entity&". I propose to make the
type of it[n] "const Entity". For this case my gcc claims:
======================================================================
-*- mode: compilation; default-directory: "/tmp/" -*-
Compilation started at Wed Oct 1 14:40:43
set -x && cat test.cc && g++ -std=c++11 -Wall test.cc -o test && ./test
+ cat test.cc
#include <iostream>
#include <ostream>
#include <type_traits>
struct Entity {};
int main() {
std::cout << std::is_convertible<const Entity, const Entity &>::value << std::endl;
}
+ g++ -std=c++11 -Wall test.cc -o test
+ ./test
1
Compilation finished at Wed Oct 1 14:40:44
======================================================================
I also don't like a half-assed random access operator, even though I don't
need operator[] myself currently. But:
- I don't want to implement a proxy class for something as complicated as the
Entity, with all of the issues that a proxy class brings, when in two weeks
Entities will be copyable and I can just use those to implement this.
- The driving reason to implement random-access iterators is that I want to do
std::advance(it, n) and maybe std::distance(it1, it2), and I want to do it
efficiently, if the grid supports that. That works perfectly with the
current proposal.
> > I also omitted implementing bidirectional iterators, since I could not come up
> > with a use case for iterating backwards through the grid. If a grid declares
> > an iterator implementation as bidirectional, the resulting EntityIterator will
> > nevertheless just be a forward iterator. It should be easy to add
> > bidirectional iterators, should the need arise.
>
> Here is one: Implementing a matrix free backwards gauss seidel method.
Alright, I'll add them...
--
Jorrit (Jö) Fahlke, Institute for Computational und Applied Mathematics,
University of Münster, Orleans-Ring 10, D-48149 Münster
Tel: +49 251 83 35146 Fax: +49 251 83 32729
In the beginning the Universe was created. This has made a lot of
people very angry and been widely regarded as a bad move.
-- Douglas Adams
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 828 bytes
Desc: Digital signature
URL: <https://lists.dune-project.org/pipermail/dune-devel/attachments/20141001/3eea11b7/attachment.sig>
More information about the Dune-devel
mailing list