STL排序向量找到第一个元素小于或等于给定值

Question

我有一个向量pairs。假设它是这样的：

vector<pair<int,int>> vec = { {1,12}, {1,5}, {1,6}, {1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} }; 

pairs按第一个元素排序。

给定一个pair，我需要找到向量的最后一个pair的索引，该向量的第一个元素小于或等于给定对的第一个元素。如果去年pair，另一对骗其左边的第一个元素的值相同，我首先需要的所有那些对：

<4,10> => 4 (vec[4] is <3,9>, the elements with the largest first value less than or equal to 4 are those with first element as 3, and there are 4 pairs with a 3 in the first element, at indices 4-7, so return the first of those pairs) 

<0,10> => -1, since no element exists to its right. 

<1,6> => 0 (vec[0] is <1,12>. There is no pair whose first element is less than 1, and there are 4 pairs, including <1,6> whose first element is 1. So we need the first of these 4 pairs.) 

<23,81> => 12 (vec[12] is <20,8>) 

条件：我只需要使用标准的算法，如upper_bound，binary_search和lower_bound。我想这一点，但它没有严重：

vector<pair<int,int>> vec = { {1,12}, {1,5}, {1,6},{1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} }; 

auto i = std::lower_bound(vec.begin(), vec.end(), make_pair<int,int>(4,10), 
    [](const pair<int,int>& f1, const pair<int,int>& f2) { return f1.first < f2.first; }); 

cout << i-vec.begin(); 

Answer 1

，你也许想结合低和上限？

#include <algorithm> 
#include <vector> 
#include <utility> 
#include <iostream> 

using namespace std; 

int main() 
{ 
    vector<pair <int,int> > vec = { {1,12}, {1,5}, {1,6}, {1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} }; 

    auto u_it = std::upper_bound(vec.begin(), vec.end(), make_pair<int,int>(4, 10), 
     [](const pair<int,int>& f1, const pair<int,int>& f2) { return f1.first < f2.first; }); 

    if(u_it == vec.begin()) 
     cout << "-1\n"; 

    auto l_it = std::lower_bound(vec.begin(), u_it, *prev(u_it), 
     [](const pair<int,int>& f1, const pair<int,int>& f2) { return f1.first < f2.first; }); 

    cout << l_it - vec.begin() << "\n"; 
    return 0; 

} 

输出：

Georgioss-MacBook-Pro:~ gsamaras$ g++ -Wall -std=c++0x main.cpp 
Georgioss-MacBook-Pro:~ gsamaras$ ./a.out 
4 

PS - 答案WhozCraig的评论后更新：

要使用it = std::upper_bound(beg,end)找到第一个被严格更大的元素，如果回答不开始，然后使用std::lower_bound(beg,it)来查找其值从(it-1)中拉出的元素的最低匹配序数。

现在答案满足所有的测试用例您提供了（我不是在这里展示它）。希望有所帮助！ :)

---

附录：

参考了std::lower_bound，std::upper_bound和std::prev。请注意0​​调用如何使用std::make_pair而不是初始化列表，以便它可以让编译器进入并解决deduce the type。

Answer 2

std::lower_bound返回第一项目大于或等于定值

---

需要

• +1到输入std::lower_bound
• -1至std::lower_bound

结果找到的值（或者你可以使用std::upper_bound）

，并再次使用std::lower_bound找到一双合适

---

例如

#include <vector> 
#include <iostream> 
#include <algorithm> 
using namespace std; 

int my_find(const vector<pair<int,int>>& vec, int value){ 
    auto comparer = [](const pair<int,int>& f1, int value) { return f1.first < value; }; 

    auto i = std::lower_bound(vec.begin(), vec.end(), value+1, comparer); 
    if(i==vec.begin()){return -1;} 

    i = std::lower_bound(vec.begin(), vec.end(), (i-1)->first, comparer); 
    return i-vec.begin(); 
} 

int main(){ 

    vector<pair<int,int>> vec = { {1,12}, {1,5}, {1,6},{1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} }; 

    cout << my_find(vec,-1) << '\n'; 
    cout << my_find(vec,3) << '\n'; 
    cout << my_find(vec,10) << '\n'; 
    cout << my_find(vec,100) << '\n'; 
} 

---

BTW，你不需要提供pair到lower_bound

，如果你只使用lower_bound，你既然你想第一对只需要一个比较器