官术网_书友最值得收藏!

  • Mastering the C++17 STL
  • Arthur O'Dwyer
  • 523字
  • 2021-07-08 10:20:25

Searching and inserting in a sorted array with std::lower_bound

Once a range of data has been sorted, it becomes possible to search within that data using binary search, as opposed to the slower linear search. The standard algorithm that implements binary search is called std::lower_bound(a,b,v):

    template<class FwdIt, class T, class C>
FwdIt lower_bound(FwdIt first, FwdIt last, const T& value, C lessthan)
{
using DiffT = typename std::iterator_traits<FwdIt>::difference_type;
FwdIt it;
DiffT count = std::distance(first, last);

while (count > 0) {
DiffT step = count / 2;
it = first;
std::advance(it, step);
if (lessthan(*it, value)) {
++it;
first = it;
count -= step + 1;
} else {
count = step;
}
}
return first;
}

template<class FwdIt, class T>
FwdIt lower_bound(FwdIt first, FwdIt last, const T& value)
{
return std::lower_bound(first, last, value, std::less<>{});
}

This function returns an iterator to the first element in the range that is not less than the given value v. If there is an instance of the value v already in the range, then the returned iterator will point at it (in fact, it will point at the first such value in the range). If there's no instance already in the range, then the returned iterator will point at the place where v should go.

We can use the return value of lower_bound as the input to vector::insert in order to insert v into the proper place in a sorted vector while preserving its sorted order:

    std::vector<int> vec = {3, 7};
for (int value : {1, 5, 9}) {
// Find the appropriate insertion point...
auto it = std::lower_bound(vec.begin(), vec.end(), value);
// ...and insert our value there.
vec.insert(it, value);
}
// The vector has remained sorted.
assert((vec == std::vector{1, 3, 5, 7, 9}));

The similar function std::upper_bound(a,b,v) returns an iterator to the first element in the range that is greater than the given value v. If v is not in the given range, then std::lower_bound and std::upper_bound will have the same return value. But if v is present in the range, then lower_bound will return an iterator pointing to the first instance of v in the range and upper_bound will return an iterator pointing "one past" the last instance of v in the range. In other words, using the two functions together will give you a half-open range [lower, upper) containing nothing but instances of the value v:

    std::vector<int> vec = {2, 3, 3, 3, 4};
auto lower = std::lower_bound(vec.begin(), vec.end(), 3);

// First approach:
// upper_bound's interface is identical to lower_bound's.
auto upper = std::upper_bound(vec.begin(), vec.end(), 3);

// Second approach:
// We don't need to binary-search the whole array the second time.
auto upper2 = std::upper_bound(lower, vec.end(), 3);
assert(upper2 == upper);

// Third approach:
// Linear scan from the lower bound might well be faster
// than binary search if our total range is really big.
auto upper3 = std::find_if(lower, vec.end(), [](int v) {
return v != 3;
});
assert(upper3 == upper);

// No matter which approach we take, this is what we end up with.
assert(*lower >= 3);
assert(*upper > 3);
assert(std::all_of(lower, upper, [](int v) { return v == 3; }));

This handles searching and inserting values in a sorted array. But what about deletion?

主站蜘蛛池模板: 巴彦淖尔市| 湄潭县| 波密县| 同心县| 都江堰市| 十堰市| 乐安县| 通辽市| 巫溪县| 古田县| 轮台县| 顺昌县| 工布江达县| 德保县| 大宁县| 万源市| 抚松县| 保康县| 南投县| 呼和浩特市| 洞口县| 巩留县| 新营市| 临西县| 收藏| 稷山县| 启东市| 虞城县| 民丰县| 永靖县| 沾益县| 马山县| 电白县| 永川市| 长宁区| 积石山| 琼结县| 长寿区| 大石桥市| 行唐县| 措美县|