[swift-evolution] [Discussion] Binary search, lower bound, upper bound, equal range

Daniel Vollmer lists at maven.de
Mon Feb 15 16:45:12 CST 2016


> On 15 Feb 2016, at 21:35, Jeff Hajewski via swift-evolution <swift-evolution at swift.org> wrote:
> 
> Hello,
> 
> Description
> Implement analogs to C++’s binary_search, lower_bound, upper_bound, and equal_range algorithms.
> 
> Initial Proposal
> I propose adding four methods for generic Array and adding four methods for Arrays that conform to Comparable:

Over the weekend, I looked at what I would require for porting a simple kd-tree from C++ to Swift, and other than stable sort I was also lacking equal_range. But I think that defining the interface for these methods on Array would be a mistake: One thing the STL got very right is that the caller gets to pick the iterators (ranges) for the algorithm. For the kd-tree, I would want to stable_sort and apply equal_range to recursively smaller segments (slices?) of an Array, and not always the complete one.

	Daniel.


More information about the swift-evolution mailing list