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

Question

我正在寻找一种方法来从向量中删除重复项（我们称之为theGreatVector :D）。 我不能使用std::sort，然后使用std::unique，因为没有办法对我的对象进行排序。

theGreatVector包含一些vector (smallVectors)

我得到了vector 的==重载，所以可以使用它

我能够创建一个O(n²)的解决方案，但我需要更高的时间效率（theGreatVector.size()可能是10⁵或10⁶）

现在我得到了类似这样的东西（只有在smallOne不存在于myVec中时才填充它）：

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

- Azhrilla

---

如果您有相等的值，很可能您也可以定义一些排序，并执行排序操作。 - juanchopanza

你的对象无法排序是什么意思？你总可以将每个数据成员都用 std::tie 放入一个 std::tuple 中，并对其使用词典序排序。 - TemplateRex

你的==在vector<Item*>上是做什么用的？它是比较size和指针值，还是对指针进行解引用并比较其基础值？为什么你认为<不能以类似的方式工作，Item有什么奇怪的地方吗？通过“重复”，你是指重复的vector<Item*>，还是在vector<Item*>中的一个Item*中重复出现的Item*，或者是在vector<Item*>中的一个Item*中重复出现的Item（我假设是第一种情况）？GreatOne的顺序很重要吗？你有多频繁地添加、读取和修改它？按什么模式进行操作（大量添加，然后只有大量读取吗？) - Yakk - Adam Nevraumont

是的，它帮了我很多。虽然我没有使用您的解决方案，但它给了我解决问题的思路。最终，我使用了词典排序来创建对象之间的顺序，但我没有使用元组，而是保持了向量。实际上，我在向量<Item*>之间创建了一个排序。 - Azhrilla

很高兴知道你找到了适合你的东西！ - TemplateRex

Answer 1

你可以将每个数据成员都使用 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
}

- TemplateRex

---

你需要比较 Item*，而不是 Item。 - juanchopanza

@juanchopanza 谢谢，已修复。 - TemplateRex

非常感谢您的回答，但是对我来说有点难以理解^^您建议删除smallvector并改用元组，是吗？ - Azhrilla

@Azhrilla，我的建议是您使用“元组”来进行比较，这样您就可以对向量进行排序。如果您的“Item”非常昂贵，则“pvec”只是一个辅助数据结构，用于交换。 - TemplateRex

Answer 2

看一下无序集合： http://www.cplusplus.com/reference/unordered_set/unordered_set/ 它似乎可以做到你想要的。单个元素的插入平均时间复杂度为O(1)，最坏情况为O(n)，只需要提供等号操作符。

- Ilya Kobelevskiy