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

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

主站蜘蛛池模板: 繁峙县| 宜良县| 正阳县| 巩留县| 应城市| 苏尼特左旗| 喀喇沁旗| 晋城| 大同县| 秦安县| 宜春市| 武威市| 泰州市| 延川县| 新巴尔虎右旗| 合阳县| 漳州市| 金塔县| 南通市| 高雄县| 任丘市| 京山县| 仁寿县| 建水县| 高尔夫| 专栏| 长乐市| 韶山市| 南部县| 洛南县| 石嘴山市| 莫力| 维西| 清镇市| 青浦区| 汨罗市| 柳江县| 白玉县| 沂源县| 泰宁县| 襄垣县|