我正在寻找一种在 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 的经验,所以不知道我上面写的代码是否足够高效。任何建议或意见都非常受欢迎。谢谢。