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);
}
}
コードでは、1 つの iterator と 1 つの reverse_iterator を使用して、条件 data>=cond[k]-0.5 && data を満たす最初と最後の要素を見つけます。
念のため、while を使用して見つかったすべての要素を反復処理し、2 番目のデータをペアで別のベクトルに格納します。ループを使用する代わりに、1行でそれを行う方法はありますか?
このコードは、元の for ループ コードよりも高速ですが、N、M、P が大きい場合は依然として低速です。私は STL の経験がほとんどないので、上記のコードが十分に効率的かどうかはわかりません。提案やコメントは大歓迎です。ありがとう。