C++ Logo

STD-PROPOSALS

Advanced search

Subject: Re: [std-proposals] Finding the index of an element (std::find_first_index)
From: Arthur O'Dwyer (arthur.j.odwyer_at_[hidden])
Date: 2020-10-04 22:08:14


On Sun, Oct 4, 2020 at 2:44 PM Jason McKesson via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> So right there, that's the question: is the name `count_until` "alien"
> to the standard library?
>
> I argued that it is alien, and my reason for this is that the suffix
> "until" does not work like similar algorithm suffixes.
>
> The behavior of `count_if` relative to `count` is solely about h .
> `count` is just a special-case of `count_if` and could be implemented
> in terms of it. `count_until` is not and cannot be implemented in
> terms of either `count` or `count_if`. `count_until` treats its
> predicate in a completely different way from `count_if`.
>
> Similarly `is_sorted` is just a special case of `is_sorted_until`, and
> the former can be implemented in terms of the latter. Again, this is
> not the case of `count_until` relative to `count`.
>
> The name "count_until" *suggests* that the "until" suffix is being
> used like `is_sorted_until`. But it's not. With `is_sorted_until`, you
> have a variation of the `is_sorted` algorithm, one which subsumes the
> shorter named one. That isn't the case here. `count_until` is as
> different an algorithm from `count` as `lower_bound` is from `find`.
>

Hmm. I mostly disagree with your parsing of the "_until suffix." I think
your way of looking at it works, but when I look at the algorithms
is_sorted_until and is_heap_until, I parse them as "is_XXX_until", not
"XXX_until". For me, they're already quite odd misfits in the STL, because
they're algorithms beginning with "is_" which do not actually return a
boolean answer. So adding a third misfit algorithm ending in "_until"
doesn't really bother me, personally.

However, it is true that you could implement `is_sorted(a, b)` in terms of
`is_sorted_until(a, b) == b`.
We might also imagine that `std::mismatch` could be called
`std::equal_until`, and `std::find_if` could be called `std::none_of_until`.
In that world, `std::count_until` would be absolutely the wrong name for
this algorithm, because you can't implement `std::count` in terms of this
algorithm, at all.

Note in passing that
http://open-std.org/JTC1/SC22/WG21/docs/papers/2019/p1927r0.pdf proposes to
add `is_partitioned_until` to the list.

It seems obvious to me that the correct name is "find_index". That's
> what you asked for, after all: do exactly what `find` does, just
> return an index instead of an iterator. You can implement `find` in
> terms of `find_index` (though you *really* shouldn't), so it fits into
> the suffix nomenclature of algorithm naming.
>

Presumably you'd have two versions: `find_index(first, last, value)` and
`find_index_if(first, last, pred)`. Or would the latter be `find_if_index`?

> [...] if an index-based
> `find` is a legitimate thing to have, why not other index-based
> algorithms too?
>

Agreed.
Btw, I've been mostly convinced that this algorithm is not needed (not even
in theory) by the slightly handwavey example given earlier in this thread,
of composing it out of the `enumerate` view which has a decent chance of
getting into C++23. Here's the example worked out:
https://godbolt.org/z/YE4f7T

template<class R, class Pred>
size_t find_index(R&& r, Pred pred)
{
  auto e = ranges::views::enumerate(r);
  auto getSecond = [](auto&& x) -> decltype(auto) { return (x.second); };
  return (*std::ranges::find_if(e, pred, getSecond)).first;
}

This is not elegant code *at all*, but at least it shows that it's possible
to get integer indices out of Ranges algorithms, if you really need
integers, and without doing two passes.

–Arthur



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

Standard Proposals Archives on Google Groups