std::upper_bound with iterator hint?
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
- Issue type
- Feature
- Clarity
- Needs clarification
- Activity status
- Stale
- Tech stack
- cpp
- Domain
- performance
Research direction
Start by reviewing the linked Boost.Math PR and searching Boost.Algorithm for binary-search APIs that accept iterator hints. Determine whether an existing facility meets the increasing-argument use case; done means reaching a documented decision about support or a defined API change.
Written by the indexing model from the issue text.
Description
In this PR, I use std::upper_bound to calculate the empirical cumulative distribution function. However, the principle use of this function is in a quadrature, where each call to the function occurs with increasing argument. Hence, if I could cache an iterator hint, then the call complexity would be an amortized log(log(N)) (or is it amortized constant time? I forget. In either case, it's better than log(N).)
Does boost.algorithm have iterator hints for binary searches?
- Dominant language
- C++
- Stars
- 131
- Forks
- 117
- PR merge metrics
- No merged PRs in 30d
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from boostorg/algorithm
-
Difficulty 5/5 Over a week Newbie friendliness 30/100
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
-
Difficulty 5/5 Over a week Newbie friendliness 25/100
-
Automated formatting Open
Difficulty 4/5 3-5 days Newbie friendliness 25/100
All issues in boostorg/algorithm
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
objectionary/eo-graphs#74 ·
-
Difficulty 1/5 Under an hour Newbie friendliness 95/100
-
enhancement
Difficulty 1/5 Under an hour Newbie friendliness 88/100
QuantStack/git2cpp#187 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 86/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100