Make DocumentMarkerListEditor::RemoveMarkers() more efficient
The current implementation of this method does a binary search to get the first
marker to be removed, then linearly walks the markers, erasing all that fall in
the specified range. This can potentially take time quadratic in the number of
markers to be removed, and always takes at least log N time.
This new implementation finds both the start point and end point of the range to
be erased in log N time, then does a single erase operation that takes time
linear in the number of markers to be removed. So the asymptotic lower bound
stays the same and the asymptotic upper bound is improved from quadratic to
linear.
I've also added a few more test cases to DocumentMarkerListEditor test to verify
the new implementation works correctly.
BUG=707867
Review-Url: https://codereview.chromium.org/2922623002
Cr-Commit-Position: refs/heads/master@{#476551}
2 files changed
