C++两个向量之间的区别<MyType*> A和B

Question

我有两个vector<MyType*>对象，称为A和B。 MyType类有一个字段ID，我想要获得MyType*，它们在A中，但不在B中。我正在研究图像分析应用程序，并希望找到一个快速/优化的解决方案。

此致 波吕克斯

Answer 1

无序的方式通常有二次复杂性，除非数据预先排序（由你的ID字段），在这种情况下，会是线性的和通过B.

struct CompareId 
{ 
    bool operator()(const MyType* a, const MyType* b) const 
    { 
     return a>ID < b->ID; 
    } 
}; 
... 
sort(A.begin(), A.end(), CompareId()); 
sort(B.begin(), B.end(), CompareId()); 

vector<MyType*> C; 
set_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C)); 

另一种解决方案是将不需要重复的搜索使用比如std有序容器::与用于严格弱模板参数CompareId设置。我认为如果你需要应用大量的集合操作，情况会更好。这有它自己的开销（作为一棵树），但如果你真的发现这是一个效率问题，你可以实现一个快速的内存分配器来插入和删除元素超快（注意：只有这样做，如果你配置文件，并确定这是一个瓶颈）。

警告：进入一些复杂的领域。

还有另一种解决方案，你可以考虑哪些可能是非常快的，如果适用，你不必担心排序数据。基本上，使任何共享相同ID的MyType对象组共享一个共享计数器（例如：指向unsigned int的指针）。

这将需要为计数器创建一个ID映射，并且每次根据其ID创建MyType对象时，都需要从映射中获取计数器。由于您的MyType对象具有重复的ID，因此您不必像创建MyType对象那样经常插入到地图中（大多数情况下可能只是获取现有的计数器）。

除此之外，还有一个全局的“遍历”计数器，只要它被提取就会增加。

static unsigned int counter = 0; 
unsigned int traversal_counter() 
{ 
    // make this atomic for multithreaded applications and 
    // needs to be modified to set all existing ID-associated 
    // counters to 0 on overflow (see below) 
    return ++counter; 
} 

现在让我们回到您有A和B向量存储MyType *的位置。为了获取A中不在B中的元素，我们首先调用traversal_counter（）。假设这是我们第一次调用它，那会得到一个遍历值1.

现在迭代B中的每个MyType *对象，并为每个对象设置从0到遍历值1的共享计数器。

现在通过每个迭代的MyType *对象A中有不当前遍历值相匹配的计数器值一（1）是不包含在B.

会发生什么A中的元素当你溢出遍历计数器？在这种情况下，我们遍历存储在ID映射中的所有计数器，并将其与遍历计数器本身一起设置为零。如果它是32位无符号整数，则只需要在约40亿次遍历中发生一次。

这是关于您可以应用于给定问题的最快解决方案。它可以对未排序的数据进行线性复杂度的任何设置操作（并且总是，不只是在像散列表这样的最佳情况下），但它确实会带来一些复杂性，所以只有在真正需要时才考虑它。

Answer 2

排序根据ID，然后使用std::set_difference两种载体（std::sort）。您需要定义一个自定义比较传递到这两种算法，例如

struct comp 
{ 
    bool operator()(MyType * lhs, MyType * rhs) const 
    { 
     return lhs->id < rhs->id; 
    } 
}; 

Answer 3

首先看问题。你想要“一切都在A而不是B”。这意味着你将不得不访问“A中的所有内容”。您还需要访问B中的所有内容，以了解什么是和不在B中。因此，这表明应该有一个解决方案，或者自由地消除n和m之间的差异，即O(2n)。

让我们考虑std::set_difference方法。每种类型是O(n log n)，并且set_difference是O(n)。所以sort-sort-set_difference方法是O(n + 2n log n)。我们称之为O(4n)。

另一种方法是首先将B的元素放置在集合（或地图）中。遍历B的迭代创建集合是O(n)加上插入O(log n)的每个元素，然后遍历A O（n），查找A（log n）的每个元素，给出总数：O(2n log n)。我们称之为O(3n)，稍微好一点。

最后，使用unordered_set（或unordered_map），并假设我们得到O(1)插入的一般情况和O(1)查找，我们有一个方法是O(2n)。 A-HA！

这里真正的胜利是unordered_set（或地图）是可能最自然的选择代表在首位，即你的数据，正确的设计得到优化的实现。这并不总是会发生，但是它确实很好！

Answer 4

如果B预先存在于A中，那么在填充A时，可以在C向量中进行保存。