2 つのベクトルを並べ替えたりコピーしたりする必要がないように、STL 型の操作を行う効率的な方法はありますか? 問題は、並べ替えにより getIntersection メソッドでロックを作成する必要があることです。理想的には、データ構造を読み取ってその中のデータを検索し、変更しないため、これを回避したいと考えています。sort メソッドはデータ構造を変更するため、メソッドの他の呼び出しを同期する必要があります。おそらくコピーを作成する必要がありますが、それは大きなコピーである可能性がありますが、ロックするよりも高速である可能性がありますが、わかりません. したがって、私の質問は、ソートされたベクトルを検索する方が、ロックまたはコピーの価格を取得するよりも効率的かどうかになります。次の例を検討してください。
class X
{
public:
struct TestX
{
long id;
.......... // other items
};
void getIntersectionByID ( vector<TextX>& result, const vector<TestX>& ids)
{
return getItemsByIntersection<long,TestX>( result, _v1, ids, &TestX::id);
return false;
}
private:
vector<TestX> _v1; // assume this is populated with data
};
// generic pred to do weak ordering on a structure by a generic field
// this is a generalized less than function which can be used for ordering
// and other equality operations
template<typename T, typename K>
struct byField
{
public:
byField(T K::* idMember) : idMember_(idMember) {}
bool operator() (const K& obj1, const K& obj2)
{
return ( obj1.*idMember_ < obj2.*idMember_ );
}
private:
T K::* idMember_;
};
template <typename T, typename K>
bool getItemsByIntersection ( std::vector<K>& retds, std::vector<K>& ds, const std::vector<T>& values, T K::* field )
{
//create the vector of structs to use for comparison
typename std::vector<K> searchCriteria(values.size());
typename std::vector<K>::iterator itS = searchCriteria.begin();
// assign the item to the vector
for (typename std::vector<T>::const_iterator it = values.begin(), itEnd = values.end(); it != itEnd; ++it,++itS)
{
(*itS).*field = *it;
}
// reserve half the size of the total ds just to be safe
typename std::vector<K> tmp;
tmp.reserve(ds.size()/2);
sort( ds.begin(), ds.end(), byField<T,K>(field) );
sort( searchCriteria.begin(), searchCriteria.end(), byField<T,K>(field) );
setGrep ( ds.begin(), ds.end(), searchCriteria.begin(), searchCriteria.end(), std::back_inserter(tmp), byField<T,K>(field) );
// don't change state until the very end, any existing contents in retds are destroyed
retds.swap(tmp);
if ( !retds.empty() )
{
return true;
}
return false;
}
/ this is a set grep meaning any items that are in set one
// will be pulled out if they match anything in set 2 based on operator pred
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
_OutputIterator
setGrep(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result, _Compare __comp)
{
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first1, *__first2))
++__first1;
else if (__comp(*__first2, *__first1))
++__first2;
else
{
*__result = *__first1;
++__first1;
++__result;
}
return __result;
}