Element access on RandomAccessRanges

[gnzlbg]

RandomAccessRanges support O(1) access to all of its elements, however, there is no syntax sugar for this yet (via the [] and the () operators).

    std::vector<int> v {1, 2, 3, 4};
    auto rng = ranges::range(ranges::begin(v), ranges::end(v));
    CHECK(rng[0] == 1);
    CHECK(rng[1] == 2);
    CHECK(rng[2] == 3);
    CHECK(rng[3] == 4);
    CHECK(rng(0) == 1);
    CHECK(rng(1) == 2);
    CHECK(rng(2) == 3);
    CHECK(rng(3) == 4);

I personally prefer the () operator since it can be easily extended to handle multidimensional ranges but the [] should also be provided for backwards compatibility (and on multidimensional ranges [] could offer one dimensional indexing which is also useful).

[Rapptz]

w.r.t. bikeshedding

operator() is associated with functions (and function objects) too much. It's better to provide operator[] and at like std::vector and friends. Just my two cents.

[gnzlbg]

@Rapptz Most linear algebra libraries use () for element access since [] cannot be overloaded for multiple dimensions (see e.g. Eigen3, Boost.uBLAS, and Stroustrup's Programming - Principles and Practice Using C++). When they also provide [] they use it to denote one-dimensional access for multidimensional entities (e.g. multidimensional C-Array's [][][]... vs []). Still, the more generic ones need to use a get function instead (like Boost.Geometry) due to the overloaded meaning you describe.

The problem appears when a library-user with an already working linear-algebra algorithm (that works with e.g. Eigen3::Matrix/Vector), wants to use it with a one dimensional range using (). Asking this user to abstract ()/[], e.g., using a generic get function is IMO unreasonable since:

• the cost of providing both ()/[] is minimal,
• the user will be right in that () means element access in his context,
• Boost.Range v2 also provides ().

So unless there is a good argument against providing operator()(index_t) I am strongly against not providing it since it is a reality that ranges will be expected to provide both and the [] vs () issue won't be fixed any time soon.

There is just a lot of code using (i) and (i, j, k).

[ericniebler]

What are you asking for, exactly? That the Iterable concept should require operator[] when the iterator type is random-access? That seems over-constraining. Or that range_facade and others could provide operator[] as a convenience?

[ericniebler]

Most linear algebra libraries use () for element access since [] cannot be overloaded for multiple dimensions

Ranges are not multi-dimensional. They are linear sequences. Always.

[gnzlbg]

That the Iterable concept should require operator[] when the iterator type is random-access? That seems over-constraining.

That the Iterable concept should require operator[] and operator() for element access when the iterator type is random access. It is over-constraining, but the alternatives (e.g. *next(begin(range), n)) are too verbose when compared with range(n) and range[n].

Ranges are not multi-dimensional. They are linear sequences. Always.

1) I haven't said that they should be multi-dimensional. I have just said that there is generic code out there (albeit not generic enough) that provides algorithm for working on linear sequences like ranges but assumes that the access operator is sometimes operator[] and sometimes operator() instead of some generic get(rng, n) or using *next(begin(range), n) everywhere.

2) What about trees? The ASL library is a good example of multi-dimensional iterators in practice. Boost.GIL uses them too. I can think of ranges in which the "next" operator could take a parameter indicating in which dimension the range should be advanced... but this is outside of the scope of this discussion.

[ericniebler]

That the Iterable concept should require operator[] and operator() for element access when the iterator type is random access.

Concept requirements from from algorithms. What algorithms need this requirement? Random access iterators require operator[] and the general feeling among those I've spoken to is that it was a mistake. Think: if we want std::pair<int*,int*> to model Range, we can today. If we add this requirement, we can't. Likewise for any user-defined range-like thing that doesn't have operator[].

Also, I don't expect people will be writing many algorithms on ranges that do anything other than take the begin and end and pass it to an iterator-based algorithm.

I could be convinced that some of the models of Range could provide operator[] as a convenience, though.

[pfultz2]

That the Iterable concept should require operator[] and operator() for element access when the iterator type is random access. It is over-constraining

No this should not happen at all. This requires the Iterable concept to be entirely intrusive, since the operators can not be implemented as free functions.

I have just said that there is generic code out there (albeit not generic enough)

Of course, its not generic enough. In general, extension points in generic code is handled through overriding ADL free functions(or through template specialization). This allows implementing the concept in non-intrusive ways. So you can make sets of third-party types implement a concept where you can't change the type directly.

[gnzlbg]

Oven provides at, Boost.Geometry provides get, you can use these non-member non-friend functions to access the elements of their "ranges" and use them to write generic algorithms full of ats and gets everywhere...

I fully understand the consequences of forcing everyone to implement any of them (or both).

Still, choosing a non-member accessor means that:

• tons of already existing algorithms using []/() (e.g. templated on a Sequence) can't use any of your random-access ranges without changing all their calls to at/get which in a lot of contexts is just not possible.
• linear algebra libraries (e.g. Eigen3) using () everywhere can't use your random access ranges either,
• porting a library from ()/[] to use at/get is a lot of work, and the resulting code is very ugly for those that have gone through the expression template pain to get a nice syntax besides performance,
• libraries with their own hand-rolled non-member non-friend accessors are easy to extend but you just turned the problem of dealing with () and [] into dealing with (), [], at, get, ... (insert xkcd reference here).

Whatever decision is made here, it will be a trade-off.

[pfultz2]

It makes no sense to limit the extensibility of the range library because other libraries did not write their code to be extensible. The problem could be alleviated some by having the models of range in the library provide these member functions as convienence.

porting a library from ()/[] to use at/get is a lot of work

I wonder if some tool in clang could help with this.

libraries with their own hand-rolled non-member non-friend accessors are easy to extend but you just turned the problem of dealing with () and [] into dealing with (), [], at, get, ...

I don't understand this point at all.

[gnzlbg]

The problem could be alleviated some by having the models of range in the library provide these member functions as convienence.

@pfultz2 This could be a good compromise, provide these functions when possible but not make it part of the concepts. @ericniebler what do you think? could this be provided by range_facade and iterator_range for RandomAccessRanges?

There is still no simple way to access the nth-element of a RandomAccessRange tho. Following Boost.Range/Oven a non-member non-friend at(range, n) -> reference_t should do for RandomAccessRanges.

libraries with their own hand-rolled non-member non-friend accessors are easy to extend but you just turned the problem of dealing with () and [] into dealing with (), [], at, get, ...

I don't understand this point at all.

@pfultz2 It just turns the problem of having two competing standard ways of accessing the elements in a "range" into having n-standard ways of doing it. I guess it is just something we have to live with.

[ericniebler]

could this be provided by range_facade and iterator_range for RandomAccessRanges?

I suppose so. The question then becomes, do we provide front and back and other container-like accessors? I've tried to keep the interface minimal, but I'm starting to feel like the guy plugging a crack in a dam with his finger.

There is still no simple way to access the nth-element of a RandomAccessRange tho. Following Boost.Range/Oven a non-member non-friend at(range, n) -> reference_t should do for RandomAccessRanges.

That would be the best we could do.

[gnzlbg]

I'll submit a pull request with at, front, and back as extensions to the library.