C++ Logo

STD-PROPOSALS

Advanced search

Subject: Re: [std-proposals] Finding the index of an element (std::find_first_index)
From: Jason McKesson (jmckesson_at_[hidden])
Date: 2020-10-01 16:48:57


On Thu, Oct 1, 2020 at 12:57 PM Kosher Yosher via Std-Proposals
<std-proposals_at_[hidden]> wrote:
>
> 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.

But in those situations, the initial range is undoubtedly an array
(performance game programming doesn't do linked-lists), so `distance`
is 100% OK.

The difficulty is understanding why you would simultaneously need an
integer index on a range that itself isn't random-access. I for one
don't know why I would have a linked list element's index correlate to
some other random-access container's index. I can understand keeping
arrays of containers properly aligned, but not for more complex data
structures.


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

Standard Proposals Archives on Google Groups