C++ Logo


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?

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.


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

Standard Proposals Archives on Google Groups