c++ 这样使用std：：upper_bound和std：：lower_bound是否正确？

我有一个pair对象的排序向量，我将使用std::upper_bound和std::lower_bound来查找所有满足(data>=a) && (data<b)的元素，下面是我的代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

struct comp_lower
{
  comp_lower() {}
  bool operator()(const pair<double, unsigned> &data, const double &bound) const
  {
    return data.first<bound;
  }
};

struct comp_upper
{
  comp_upper() {}
  bool operator()(const double &bound, const pair<double, unsigned> &data) const
  {
    return bound <= data.first;
  }
};

int main(void)
{
  std::vector< std::pair<double, unsigned> > sortData;

  // sort the data manually based on the first entry
  sortData.push_back( make_pair(-5, 1) );
  sortData.push_back( make_pair(-4.5, 10) );
  sortData.push_back( make_pair(-4 , 19) );
  sortData.push_back( make_pair(-4 , 2) );
  sortData.push_back( make_pair(-3.5 , 28) );
  sortData.push_back( make_pair(-3.5 , 11) );
  sortData.push_back( make_pair(-3 , 37) );
  sortData.push_back( make_pair(-3 , 20) );
  sortData.push_back( make_pair(-3 , 3) );
  sortData.push_back( make_pair(-2.5 , 12) );
  sortData.push_back( make_pair(-2.5 , 29) );
  sortData.push_back( make_pair(-2 , 38) );
  sortData.push_back( make_pair(-2 , 21) );
  sortData.push_back( make_pair(-2 , 4) );
  sortData.push_back( make_pair(-1.5 , 30) );
  sortData.push_back( make_pair(-1.5 , 13) );
  sortData.push_back( make_pair(-1 , 39) );
  sortData.push_back( make_pair(-1 , 22) );
  sortData.push_back( make_pair(-1 , 5) );
  sortData.push_back( make_pair(-0.5 , 31) );
  sortData.push_back( make_pair(-0.5 , 14) );
  sortData.push_back( make_pair(0 , 6) );
  sortData.push_back( make_pair(0 , 23) );
  sortData.push_back( make_pair(0 , 40) );
  sortData.push_back( make_pair(0.5 , 32) );
  sortData.push_back( make_pair(0.5 , 15) );
  sortData.push_back( make_pair(1 , 41) );
  sortData.push_back( make_pair(1 , 24) );
  sortData.push_back( make_pair(1 , 7) );
  sortData.push_back( make_pair(1.5 , 33) );
  sortData.push_back( make_pair(1.5 , 16) );
  sortData.push_back( make_pair(2 , 42) );
  sortData.push_back( make_pair(2 , 25) );
  sortData.push_back( make_pair(2 , 8) );
  sortData.push_back( make_pair(2.5 , 17) );
  sortData.push_back( make_pair(2.5 , 34) );
  sortData.push_back( make_pair(3 , 43) );
  sortData.push_back( make_pair(3 , 26) );
  sortData.push_back( make_pair(3 , 9) );
  sortData.push_back( make_pair(3.5 , 35) );
  sortData.push_back( make_pair(3.5 , 18) );
  sortData.push_back( make_pair(4 , 44) );
  sortData.push_back( make_pair(4 , 27) );
  sortData.push_back( make_pair(4.5 , 36) );
  sortData.push_back( make_pair(5 , 45) );

  double a = -4.1;
  double b = -3.0;

  vector< pair<double, unsigned> >::iterator lower = std::lower_bound(sortData.begin(), sortData.end(), a, comp_lower());
  vector< pair<double, unsigned> >::iterator upper = std::upper_bound(sortData.begin(), sortData.end(), b, comp_upper());

  cout << (lower->first) << "," << (lower->second) << "  [" << a << "]" <<   endl;
  cout << (upper->first) << "," << (upper->second) <<  "  [" << b << "]" << endl << endl;

  return 0;
}

这里我搜索所有第一个条目大于或等于-4.1且小于-3的元素。它应该返回（-4，19）和（-3.5，11），但它返回（0，0）和（-3，37）。我想我用错了upper_bound和lower_bound，但我没能弄清楚。

为什么它不返回（-4，19）作为第一个结果：comp_lower中的参数类型错误。bound参数应为double，而不是无符号。
为什么不返回（-3.5，11）作为第二个结果：您的代码显示为double b = -3.0，而您的问题描述显示为-3.9。
但是，这并不完全正确，lower_bound和upper_bound都返回满足特定规则的序列的 first 元素，因此它们都不直接适合于寻找所需的上限，但是，如果你只取前面的元素，你会得到正确的结果：

vector< pair<double, unsigned> >::iterator upper = 
    std::upper_bound(sortData.begin(), sortData.end(), b, comp_upper()) - 1;

当然，你必须检查upper_bound是否返回了序列的第一个元素，这样迭代器就不会在递减时超出边界。

c++ 这样使用std：：upper_bound和std：：lower_bound是否正确？

1条答案

相关问题

热门标签

最新问答