On Sun, Oct 4, 2020 at 2:44 PM Jason McKesson via Std-Proposals <std-proposals@lists.isocpp.org> 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:

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