HomePhabricator

[ADT] llvm::bsearch, binary search for mere mortals

Authored by sammccall on Apr 16 2019, 4:53 PM.

Description

[ADT] llvm::bsearch, binary search for mere mortals

Summary:
Add to STLExtras a binary search function with a simple mental model:
You provide a range and a predicate which is true above a certain point.
bsearch() tells you that point.
Overloads are provided for integers, iterators, and containers.

This is more suitable than std:: alternatives in many cases:

  • std::binary_search only indicates presence/absence
  • upper_bound/lower_bound give you the opportunity to pick the wrong one
  • all of the options have confusing names and definitions when your predicate doesn't have simple "less than" semantics
  • all of the options require iterators
  • we plumb around a useless value parameter that should be a lambda capture

The API is inspired by Go's standard library, but we add an extra parameter as
well as some overloads and templates to show how clever C++ is.

Reviewers: ilya-biryukov, gribozavr

Subscribers: dexonsmith, kristina, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D60779

llvm-svn: 358540

Details

Committed
sammccallApr 16 2019, 4:53 PM
Differential Revision
D60779: [ADT] llvm::bsearch, binary search for mere mortals
Parents
rGd5bc5ca3e4f6: [x86] adjust LEA tests for better coverage; NFC
Branches
Unknown
Tags
Unknown