0

我正在寻找一种在 C++ 中搜索大数组的方法。我用谷歌搜索,有人建议在排序后的数组上使用 stl 算法。我有一个大数组(nxm)并且我有许多条件,因此对于每次搜索,我都会找到满足条件的所有数据的索引并返回索引。我复制并修改了我在网上找到的代码如下

struct MyComparator
{
  bool operator()(const pair<NumType, unsigned int> &d1, const pair<NumType, unsigned int> &d2) const
  {
    return d1.first<d2.first;
  }
};

struct LessThan
{
  NumType x;
  LessThan(NumType y) {x=y;}
  bool operator()(const pair<NumType, unsigned int> &d) const {return d.first<x;}
};

struct GreaterEqual
{
  NumType x;
  GreaterEqual(NumType y) {x=y;}
  bool operator()(const pair<NumType, unsigned int> &d) const {return d.first>=x;}
};

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

  int N=1000, M=2000; // just example, could be as big as 50000
  int P = 2000;       // 2000 conditions, each for one search 

  for (int row=0; row<N; row++)
  {
    for (int col=0; col<M; col++)
    {
      // where x (not shown here) is the data in the array and ind is the correspond index 
      sortData.push_back( make_pair( x, ind) );
    }
  }  
  sort(sortData.begin(), sortData.end(), MyComparator());  // sort the data array

  for (unsigned int k=0; k<P; k++)  // loop the search
  {
     // cond is a predefined array contains P numbers
     double lower_bound = cond(k) - 0.5;
     double upper_bound = cond(k) + 0.5;

     // since the array is sorted, to find all elements satisfying the condition, we search for iterator for the first meet number

     // since the array is sorted, to find all elements satisfying the condition, we search for reverse iterator for the first meet number in the reverse vector
     std::vector< pair<double, unsigned int> >::iterator itb = find_if(sortData.begin(), sortData.end(), GreaterEqual(lower_bound));

    std::vector< pair<double, unsigned int> >::reverse_iterator ite = find_if(sortData.rbegin(), sortData.rend(), LessThan(upper_bound));

    // here, I would like to iterate the data found but I didn't get it compiled, I think it is because itb is iterator and ite is reverse_iterator? so how to make it work?
    std::vector<int> index;
    while (itb!=ite)
    {
      index.push_back(*itb.second);
      itb++;
    } 

    coords.push_back(index);
  }
}

在代码中,我使用一个迭代器和一个 reverse_iterator 来查找满足条件 data>=cond[k]-0.5 && data 的第一个和最后一个元素

购买方式,我使用 while 迭代所有找到的元素并将第二个数据成对存储到另一个向量。有没有办法用一行而不是使用循环来做到这一点?

这段代码比我原来的 for 循环代码要快,但是当 N、M、P 很大时它仍然很慢。由于我几乎没有 STL 的经验,所以不知道我上面写的代码是否足够高效。任何建议或意见都非常受欢迎。谢谢。

4

0 回答 0