5

ベクターから重複を削除する方法を探しています (彼を theGreatVector :D と呼びましょう)。オブジェクトをソートする方法がないため、std::sort の後に std::unique を使用することはできません。

theGreatVector にはいくつかのvector<Item*>(smallVectors)が含まれています

== のオーバーロードを取得したvector<Item*>ので、それを使用できます

O（n²）で何かを作成できますが、時間効率が必要です（theGreatVector.size（）は10⁵または10⁶になる可能性があります）

今、私が得たのはそのようなものです（smallOneが含まれていない場合にのみベクトルを埋めます）：

for(i=0;i<size;i++)
{
  vector<Item*>smallOne = FindFacets(i)
  if(smallOne doesnt belong to GreatOne) // this line already in O(n) :/
  {
     theGreatOne.push_back(smallOne);
  }
}

nlog(n) + n または n² よりも低いものでもそれを行う方法があれば、それは素晴らしいことです!

どうもありがとう

アズ

4

2 に答える 2

0

unordered set を見てください: http://www.cplusplus.com/reference/unordered_set/unordered_set/ それはあなたが望むことをしているようです。単一要素の挿入は、平均で O(1) で行われ、最悪の場合は O(n) で行われます。等値演算子のみを指定する必要があります。

于 2013-04-24T09:52:45.753 に答える
0

常にstd::tieすべてのデータ メンバーを に変換し、std::tuple辞書式順序付けを使用して、ビッグ データ構造へのポインターのベクトルを並べ替えることができます。std::unique出力をコピーする前に、そのデータ構造に対して行うことができます。小さな変更を加えて、大きなItemベクトルを直接並べ替えることで、重複を削除することもできます。

#include <tuple>
#include <memory>
#include <vector>

// tuples have builtin lexicographic ordering, 
// I'm assuming all your Item's data members also have operator<
bool operator<(Item const& lhs, Item const& rhs)
{
    return std::tie(lhs.first_data, /*...*/ lhs.last_data) < std::tie(rhs.first_data, /*...*/ rhs.last_Data);
}

int main()
{
   // In the Beginning, there was some data
   std::vector<Item> vec;
   // fill it

   // init helper vector with addresses of vec, complexity O(N)
   std::vector<Item*> pvec; 
   pvec.reserve(vec.size());
   std::transform(std::begin(vec), std::end(vec), std::back_inserter(pvec), std::addressof<Item>);

   // sort to put duplicates in adjecent positions, complexity O(N log N) 
   std::sort(std::begin(pvec), std::end(pvec), [](Item const* lhs, Item const* rhs){
       return *lhs < *rhs; // delegates to operator< for Item
   });       

   // remove duplicates, complexity O(N)
   auto it = std::unique(std::begin(pvec), std::end(pvec), [](Item const* lhs, Item const* rhs){
       return *lhs == *rhs; // assumes Item has operator==, if not use std::tuple::operator==
   });
   pvec.erase(it, std::end(pvec));

   // copy result, complexity O(N)
   std::vector<Item> result;
   result.reserve(pvec.size());
   std::transform(std::begin(pvec), std::end(pvec), std::back_inserter(result), [](Item const* pelem){
       return *pelem;
   });

   // And it was good, and done in O(N log N) complexity
}
于 2013-04-24T09:51:45.020 に答える