0

我有一个对对象的排序向量。我将使用 std::upper_bound 和 std::lower_bound 来查找所有元素，例如 (data>=a) && (data 

#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

1 回答 1

0

为什么它不返回 (-4, 19) 作为第一个结果：您在 comp_lower 中的参数类型错误。bound参数应该是，而double不是无符号的。

为什么它不返回 (-3.5, 11) 作为第二个结果：您的代码显示double b = -3.0，即使您的问题描述为 -3.9。

不过，这并不完全正确。两者都lower_bound返回upper_bound满足特定规则的序列的第一个元素，因此两者都不直接适用于查找所需上限的任务。但是，如果您只取前面的元素，您将得到正确的结果：

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

而且，当然，您必须检查 upper_bound 是否返回了序列的第一个元素，这样迭代器就不会因递减而越界。

于 2013-07-27T22:43:35.640 回答