从不可排序的向量中删除重复项

Question

我正在寻找一种从矢量中删除重复项的方法(让我们称之为theGreatVector:D).我不能使用std :: sort后跟std :: unique,因为无法对对象进行排序.

vector<Item*>theGreatVector 包含一些(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²的东西,那就太好了!

非常感谢

AZH

Answer 1

您始终可以将std::tie每个数据成员放入 a 中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
}