[Ranges] result for range::find() (and similar)

Sean Parent sean_parent at mac.com
Tue Jan 8 02:05:45 CET 2013


Some comments from the writeup -
https://github.com/dietmarkuehl/kuhllib/wiki/STL-2.0

---
Ranges - agree with the value of them, especially for dealing with
containers. But having them at the exclusion of positions leads to things
like you note:
>>>
auto it    = kuhl::find<kuhl::result_iterator>(c, v);  // the default
auto start = kuhl::find<kuhl::result_start_range>(c, v);
auto tail  = kuhl::find<kuhl::result_tail_range>(c, v);
auto copy  = kuhl::find<kuhl::result_tail_copy<>>(c, v);
<<<
I find that is overkill to have so many variants of the same algorithm
(and using a template parameter here implies it isn't a simple enumeration
- I prefer a naming convention).

copy taking pair of ranges is a different algorithm with a different result
(a pair of positions). In ASL we have copy_bounded() for this <
http://stlab.adobe.com/group__copy.html#ga3698dd264aafd035f821ed531121f118>.
Constructing an unbounded range to satisfy this is unnecessary complexity.
---
Multiple properties

In ASL we added projection function arguments to solve the same thing - so
given a vector of struct employee { string first, string last };. You can
write:

sort(v, less(), &employeee::last);
auto p = lower_bound(v, "Smith", less(), &employee::last);

I think lower_bound is another interesting case with ranges - if
lower_bound is frequently used as:

auto p = lower_bound(v, value);
if (p == end(v) || *p != value) insert(v, p, value);

I'm not sure what range one would pass to insert to denote an insertion
point.

----

Iterator vs. const iterator

I've never figured out why people consider this a problem.

----
reading vs. writing

This could also be viewed as a sub problem of the proxy object problem. I'm
not convinced that iterators or ranges is the correct place to fix it. I'm
not even strongly convinced of the need for strong separation between
access and traversal, I just don't know of many useful models.

----

Limited output sequence

We should have a set of bounded algorithms -

These have different results - see copy_bounded().

----

Heterogeneous iterator

Again, I think this is putting too much on iterators. Algorithms that act
with a sentinel termination or with a count are different beasts. See
copy_n() and copy_sentinel()

http://stlab.adobe.com/copy_8hpp.html

For ranges - I certainly thing you should be able to construct a range with:

a pair of iterators
an iterator and a count
an iterator and a sentinel value

In which case, copy(r, out) can dispatch to the correct algorithm.

----

Although I think the use or property maps is interesting, I'm not convinced
the complexity is warranted. Not all problems are worth solving.

----

A few items you didn't mention:

* Taking function objects instead of items convertible to function objects.
For example - given struct element { ... bool is_selected; };. I should be
able to write:

auto p = find_if(v, &element::is_selected);

No bind necessary. It would be really great if we could simply amend that
language so that pointer to member functions and data members are callable
directly. i.e.:

(&element::is_selected)(e);

Instead of:

e.*(&element::is_selected);

* Fixing the functional operator objects (std::less etc.) so they are
concrete classes that deduce their arguments. In ASL this is what allows me
to write sort(v, greater()).

* Lack of direct access to node pointers to implement node based algorithms
efficiently.

* Many interesting algorithms that could be added.

* Other issues that are more challenging to fix such as:

** Incorrect returned for std::max() when both elements are equal (should
return second argument).
** Incorrect ordering for partition (false should sort before true).
** min and max should return a non-const reference when passed non-const
arguments:
       min(a, b) = 1.0;

Sean



On Mon, Jan 7, 2013 at 4:06 PM, Dietmar Kuehl <dietmar.kuehl at gmail.com>wrote:

>
> On 7 Jan 2013, at 22:55, Sean Parent <sean_parent at mac.com> wrote:
> On Mon, Jan 7, 2013 at 2:20 PM, Dietmar Kuehl <dietmar.kuehl at gmail.com>
>  wrote:
>
>> On 7 Jan 2013, at 20:25, Andrei Alexandrescu <andrei at erdani.com> wrote:
>> > As has been stated there are advantages and disadvantages to be had from
>> > dealing away with iterators. The way I see thing is, this decision
>> > influences direction dramatically:
>>
>> Of course. In particular:
>>
>> > * Iterator-based ranges are a helper for iterators
>>
>> If ranges and iterators coexist, they need to be able to interact. Even
>> without bringing
>> up my vision for accessing data ranges/sequences, yet (i.e., property
>> maps), you'll get
>> a combinatorial explosion on how to call algorithms, e.g.:
>>
>>     mismatch(range0, range1)
>>     mismatch(range0, begin1, end1);
>>     mismatch(begin0, end0, range1);
>>     mismatch(begin0, end0, begin1, end1); // yes, STL doesn't use end1;
>> it is wrong!
>>
>
> It's a different algorithm - don't make me pay for your algorithm to do
> additional tests if I can ensure it isn't necessary. Feel free to propose a
> new form of mismatch that take two ranges. There are many such algorithms.
>
>
> I think it is just one algorithm but there is a bit of missing context:
> When I'm thinking about
> STL-like algorithm I'm thinking of mixed type begin and end indicators (or
> single-pass and
> multi-pass sequences; for bidrectional and random-access requirements the
> ends need to
> be homogenous). That is, if you know which range is bigger, make the end
> unreachable,
> i.e., the comparison between the end and the iterator a constexpr
> operator==() always
>  returning false. An incomplete write-up of ideas how to improve the STL
> is at
> <https://github.com/dietmarkuehl/kuhllib/wiki/STL-2.0>.
>
> By I don't know why interop implies you need all forms - I can always
> construct a range from a pair of iterators and I can always extract an
> iterator from a range.
>
>
> I have trouble deciding which ranges would be passed by pairs of iterators
> and which
> would be passed by ranges. Allowing all combinations side steps the
> question.
>
> Does anyone on this list actually have stats on how often iterators cause
> problems by overrunning a range that would have been caught by
> pessimization? I've seen many cases of people overrunning a range because
> they failed to supply a strict-weak-ordering to sort, or when they
> unknowingly invalidated their iterators, or failed to check for
> first==last. I cannot see recall seeing a single instance where someone
> overran a range where simply having a range based interface would have
> helped (not that a range class alone doesn't help with checking first==last
> unless you impose a test on every "drop_front/back" operation).
>
> Positions are a natural concept - I see many benefits in a great range
> library but only complication if it's done while trying to eliminate
> iterators.
>
>
> I'm exploring an area where I see problems with not having iterators. If
> these problems
> can be resolved in a reasonable way I'm happy to go along and see if a
> range-only
> library is easier to use. If not, I'm going back and pursue the direction
> in which I was
> experimenting before (see the link above).
>
> _______________________________________________
> Ranges mailing list
> Ranges at isocpp.open-std.org
> http://www.open-std.org/mailman/listinfo/ranges
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.open-std.org/pipermail/ranges/attachments/20130107/8de0acc8/attachment-0001.html 


More information about the Ranges mailing list