lower_boundC++ STL

发布网友

我来回答

共1个回答

热心网友

在C++的STL库中，`lower_bound`函数用于在有序序列中找到可以插入新值的位置，使得序列保持有序。其函数原型有两版本。

第一个版本的函数原型是：`template class ForwardIterator, class Type > ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const Type &value );`。该函数使用底层的 `<`（小于）操作符，返回一个`iterator`，指向在`[first,last)`标记的有序序列中可以插入`value`，而不会破坏容器顺序的第一个位置，这个位置标记了一个大于等于`value`的值。

例如，有一个序列`ia[]={12,15,17,19,20,22,23,26,29,29,35,40,51}`。如果调用`lower_bound(ia.begin(), ia.end(), 21)`，将返回一个指向`22`的`iterator`。同样，`lower_bound(ia.begin(), ia.end(), 22)`也将返回一个指向`22`的`iterator`。

第二个版本的函数原型是：`template class ForwardIterator, class Type, class Compare > ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const Type &value, Compare comp );`。此版本根据`comp`进行排序和比较，同样返回一个`iterator`，指向在`[first,last)`标记的有序序列中可以插入`value`，而不会破坏容器顺序的第一个位置。

调用`lower_bound`之前，必须确保序列为有序序列，否则可能会调用错误。第一个版本排序依据底层的 `<`（小于）操作符，而第二个版本根据`comp`进行排序。