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

您始终可以将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 回答
0

看看无序集： http ://www.cplusplus.com/reference/unordered_set/unordered_set/ 它似乎做你想做的事。单个元素的插入平均在 O(1) 中完成，在最坏的情况下为 O(n)，只需要提供相等运算符。

于 2013-04-24T09:52:45.753 回答