C++ Logo


Advanced search

Subject: Re: [std-proposals] Finding the index of an element (std::find_first_index)
From: Kosher Yosher (goekhan.oezdogan_at_[hidden])
Date: 2020-10-01 11:56:51

std::find_if + std::distance would incur 2*O(n) on a linked list vs O(n)
with the proposed template. The return type of std::distance also doesn't
cover the entire container range. My main concern is readability though. We
always talk about making intent clear in code and having 2 functions,
similar to the erase / remove idiom, to do 1 logical operation goes against
that. You wrote a blog post about this idiom in July and we see it
happening in C++20; same thing.
Similar reasoning against pushing the inverse std::find_if version as a
"good" solution - it just doesn't express intent.

All you can do with an integer index is use it to increment an existing
> iterator

I think programs would be quite boring if that's all you can do with an
integer. :) This comes up all the time in game programming for example
where the use-case is to use the integer to index into another table.

I've talked to a few people now about the name and it is indeed difficult
for the reasons you mentioned. The return type is also a little tricky.
So we came to the same conclusions and I wrote this mail in hopes that
these are not problems that would prevent this from going in, ridding the
world of more old C-style code. :) It's easier to convince people when you
have a snappy one-liner to do the job.

Looking forward to more replies.

Thanks Arthur!

On Thu, 1 Oct 2020 at 17:25, Arthur O'Dwyer <arthur.j.odwyer_at_[hidden]>

> On Thu, Oct 1, 2020 at 11:43 AM Kosher Yosher via Std-Proposals <
> std-proposals_at_[hidden]> wrote:
>> Hi,
>> Quick thoughts on adding a new function to <algorithm> which returns the
>> index of an element, matched by a predicate, in a container? The goal is to
>> stop writing FindX scanning functions and make it as concise as possible to
>> do this common operation.
> I think from the classic STL's point of view that'd be simply
> auto it = std::find_if(v.begin(), v.end(), pred);
> if (it != v.end()) {
> auto index = std::distance(v.begin(), it);
> // do something with index
> }
> The thing is, in terms of the classic STL, you never actually want to know
> indices because they're simply not as useful as iterators. Anything you
> might want to do with "that element" requires an iterator. Anything you
> might want to do "for each element up to that one" requires an iterator.
> All you can do with an integer index is use it to increment an existing
> iterator, which might be slow if the iterator type isn't random-access.
> However, the STL does provide std::count and std::count_if, which do
> something similar to what you want and return integers. So I guess maybe
> the classic-STL name for what you want is `count_until`. The problem is
> that it's not clear what value `count_until` could return to indicate
> failure. The obvious answer is "length of the entire range."
> auto trim(string_view sv) {
> auto leading_spaces = nonstd::count_until(sv.begin(), sv.end(),
> std::not_fn(isSpace));
> sv.remove_prefix(leading_spaces);
> auto trailing_spaces = nonstd::count_until(sv.rbegin(), sv.rend(),
> std::not_fn(isSpace));
> sv.remove_suffix(trailing_spaces);
> return sv;
> }
> Compare to one way you might write that today (if I haven't made an
> off-by-one error):
> auto trim(string_view sv) {
> auto first_nonspace = std::find_if(sv.begin(), sv.end(),
> std::not_fn(isSpace));
> sv.remove_prefix(first_nonspace - sv.begin());
> auto last_nonspace = std::find_if(sv.rbegin(), sv.rend(),
> std::not_fn(isSpace)).base();
> sv.remove_suffix(sv.end() - last_nonspace);
> return sv;
> }
> template<class InputIterator, class UnaryPredicate>
>> constexpr std::size_t find_first_index(InputIterator first, InputIterator last, UnaryPredicate pred)
> I think you should use std::iter_difference_t
> <https://en.cppreference.com/w/cpp/iterator/iter_t><InputIterator>
> instead of std::size_t.
> OTOH, it's a little weird to talk about the difference_type of an input
> iterator.
> OTOOH, it seems that all standard input iterators have `ptrdiff_t` as
> their difference_type, so that's good.
> my $.02,
> Arthur

STD-PROPOSALS list run by std-proposals-owner@lists.isocpp.org

Standard Proposals Archives on Google Groups