C++ Logo


Advanced search

Subject: Re: [std-proposals] Finding the index of an element (std::find_first_index)
From: Gokhan (goekhan.oezdogan_at_[hidden])
Date: 2020-10-01 19:19:57


Yes, but that is not the point. Theoretical examples like that are cherries the standard picks on purpose in an attempt to make the library code as generic as possible without sacrificing performance. The example, regardless of how silly it might be in practice, is valid in that regard, a program can be written to prove it, and hence is a point in favour of the template. The same theoretical reasoning applies as an argument against Matthews point about the std::distance range covering the allocation limit in practice. The standard is written against an imaginary machine that *can* allocate the full max(size_t) range.


std::distance also returns a signed integer type – containers are indexed by size_type (unsigned). Another point in favour of the suggested template.


But, while all of that holds, it’s besides the more important practical argument that it is simply more concise to have 1 vs 2 function calls. If one of the goals of the standard committee is to convince people to stop writing C in C++, and express their intent clearly, then this is what you have to do: provide the absolute shortest form in the standard that Just Works(TM). The suggested template function is that.


The ranges solution Dvir suggests in [P2164]

is pretty good too, and I was expecting something like that to come out of the ranges proposals. It’s still a little off from the more concise, proposed version though, especially given that we have all the other count_X and find_X functions doing very similar work. I don’t see how adding this template would make anything worse, once the return type and naming is fixed.


From: Jason McKesson via Std-Proposals
Sent: 01 October 2020 22:49
To: std-proposals@lists.isocpp.org
Cc: Jason McKesson
Subject: Re: [std-proposals] Finding the index of an element (std::find_first_index)


On Thu, Oct 1, 2020 at 12:57 PM Kosher Yosher via Std-Proposals

<std-proposals@lists.isocpp.org> 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



Std-Proposals mailing list




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

Standard Proposals Archives on Google Groups