如何找到向量中第一个比整数X小的元素？ (c++)

Question

如果我有以下向量 {10 10 10 20 20 20 30 30} 我想要一个函数返回 = X 的整数的位置或直接返回 X 之后的较小元素，例如如果我正在搜索 11 我希望函数返回 2 因为第二个元素（10）是第一个较小的元素向量中的元素超过 11。
我尝试使用 lower_bound 但这不起作用。

int myints[] = {10,20,30,30,20,10,10,20};
vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20
vector<int>::iterator low,up;

sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

low=lower_bound (v.begin(), v.end(), 11); //
up= upper_bound (v.begin(), v.end(), 11); //

cout << "lower_bound at position " << int(low- v.begin()) << endl;
cout << "upper_bound at position " << int(up - v.begin()) << endl;

return 0;

此代码输出：

lower_bound at position 3
upper_bound at position 3

Answer 1

cppreference 告诉我

std::lower_bound

返回一个迭代器，指向[first,last)范围内的第一个元素，且不小于value

和

std::upper_bound

返回一个迭代器，指向范围 [first, last) 中大于 value

的第一个元素

在这种情况下，给定一个包含

10 10 10 20 20 20 30 30

的向量，我希望两个函数都指向第一个

20

，它位于向量中的位置 3，并且确实是您两次得到的结果。如果您要求

20

，

std::lower_bound

将返回一个指向向量中第一个

20

（位置 3）的迭代器...第一个数字不小于 20，并且与您得到的结果相同要求

11

。但在这种情况下，

std::upper_bound

将返回一个指向第一个

30

（位置 6）的迭代器，这是第一个大于 20 的值。

只需将迭代器向后移动一位即可获得小于目标数字的最后一个值，

std::prev

是实现此目的的一种方法。

Answer 2

好吧，

upper_bound

返回第一个大于测试项目的项目，因此之前的项目（如果存在）将是您想要的项目？

Answer 3

你可以这样做...如果向量为空，最好返回一个迭代器...

auto find_next_smaller(vector<int> vec, const int x) { 
    std::sort(vec.begin(), vec.end());
    auto it = std::lower_bound(vec.begin(), vec.end(), x); 
    if (it == vec.end()) { 
      it = (vec.rbegin()+1).base();
    }
    else if (it != vec.begin() && *it > x) { 
        --it; 
    }

    return it; 
} 

Answer 4

如果必须找到小于或等于某个 x 的元素，则可以使用多重集来实现。

#include <iostream> 
#include <set> 
#include <iterator> 

using namespace std; 

int main() 
{
    multiset <int, greater <int> > iammultiset;
    iammultiset.insert(10);
    iammultiset.insert(10);
    iammultiset.insert(14);
    iammultiset.insert(20);
    iammultiset.insert(20);
    iammultiset.insert(30);
    iammultiset.insert(40);
    iammultiset.insert(50);
    //{10,10,14,20,20,30,40,50}
    
    cout<<*iammultiset.lower_bound(17) << endl;
    //The Output here will be 14.
    
    cout<<*iammultiset.lower_bound(20) << endl;
    //The Output here will be 20.
}

Answer 5

#include <bits/stdc++.h>
using namespace std;
template <typename F, typename T>

F first_less_than(F f, F l, T val)
{
    auto it = lower_bound(f, l, val);
    return it == f ? l : --it;
}

int main()
{
    vector<int> s{10, 20, 25, 40};
    auto j = first_less_than(s.begin(), s.end(), 35);

    cout << *j;

    //output : 25
    return 0;
}

Answer 6

我使用了更大的比较器和反向迭代器

#include<bits/stdc++.h>
using namespace std;
int32_t main()
{
int myints[] = {10,20,30,30,20,10,10,20};
vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20
vector<int>::reverse_iterator low;
vector<int>::iterator up;

sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

low=lower_bound (v.rbegin(), v.rend(), 11, greater<int>()); //
up= upper_bound (v.begin(), v.end(), 11); //
cout <<"lower_bound number "<<*low<<endl;
cout << "lower_bound at position " << int(v.rend()-low)-1 << endl; //subtracted 1 bcz we used rend() iterator(as in end() iterator we subtract 1 to get position)
cout << "upper_bound at position " << int(up - v.begin()) << endl;

return 0;
}

输出：

lower_bound number 10
lower_bound at position 2
upper_bound at position 3