c++ - 从不可排序的 vector 中删除重复项

Question

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

theGreatVector 包含一些 vector<Item*> (小 vector )

我为 vector<Item*> 重载了 ==所以我可以使用它

我能够在 O(n²) 内创建一些东西，但我需要时间效率(theGreatVector.size() 可以是 10⁵ 或 10⁶)

现在我得到的是类似的东西(只有当 smallOne 不在其中时，我才填充我的 vector ):

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² 的情况下做到这一点，那就太好了!

非常感谢

啊啊

Answer 1

您始终可以将每个数据成员 std::tie 放入一个 std::tuple 中，并对其使用字典顺序对指向您的大数据结构的指针 vector 进行排序.然后，您可以在复制输出之前对该数据结构执行 std::unique 操作。通过一个小的修改，您还可以通过直接对大的 Item vector 进行排序来删除重复项。

#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
}