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

  • 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?

主站蜘蛛池模板: 万安县| 内乡县| 石泉县| 左权县| 庆安县| 桦南县| 武宣县| 江西省| 蕉岭县| 武乡县| 简阳市| 周口市| 巩留县| 南汇区| 安陆市| 南汇区| 资中县| 楚雄市| 茶陵县| 科尔| 育儿| 安泽县| 台江县| 申扎县| 赤水市| 图们市| 洪湖市| 明光市| 龙胜| 双流县| 天祝| 枞阳县| 泸西县| 滨州市| 延庆县| 千阳县| 宝清县| 保靖县| 拉萨市| 岫岩| 永宁县|