0

有没有一种有效的方法来比较两个执行 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;
    }
4

2 回答 2

2

如果你有小向量，你可以写一些可以解决问题的东西，但如果向量没有排序，就无法避免n*n比较。假设您在两个向量中都有 1,000,000 个元素，即 1,000,000,000,000 次比较操作。

如果您只需要相等/不相等，则可以复制两者，对副本进行排序，比较它们并销毁副本...

于 2012-06-18T14:51:32.947 回答
1

你可以复印。以明显的方式复制为向量然后排序，或者如果向量可能包含很多欺骗：

std::set<T,pred> s1(v1.begin(), v1.end());
std::set<T,pred> s2(v2.begin(), v2.end());
std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(tmp), pred());

相反，使用它可能会更快unordered_set，而且内存也更少，因为您只需要其中一个集合的“副本”。但是，您必须编写一个哈希函数，这可能并不容易，具体取决于您的谓词做什么。您还必须编写交集代码，但这很简单。

v1其他可能的选择：填充完成后立即排序；使用Xaset而不是 a vector; 提供标准作为 aset而不是 a vector。它们是否适用取决于X和/或调用者是否可以看到pred. 和上面一样，如果你可以写一个哈希，那么你可以set用unordered_set.

于 2012-06-18T14:59:18.127 回答