c++ - 两个 vector 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::set 这样的有序容器，并将 CompareId 用于 StrictWeakOrdering 模板参数。如果您需要应用大量集合操作，我认为这会更好。这有它自己的开销(作为一棵树)但是如果你真的发现这是一个效率问题，你可以实现一个快速内存分配器来超快地插入和删除元素(注意:只有在你分析并确定这是一个瓶颈)。

警告:进入有点复杂的领域。

您可以考虑另一种解决方案，如果适用，它的速度会非常快，而且您永远不必担心数据排序问题。基本上，使任何一组共享相同 ID 的 MyType 对象存储一个共享计数器(例如:指向 unsigned int 的指针)。

这将需要创建 ID 到计数器的映射，并且需要在每次基于其 ID 创建 MyType 对象时从映射中获取计数器。由于您拥有具有重复 ID 的 MyType 对象，因此不必像创建 MyType 对象那样频繁地插入 map (大多数可能只获取现有计数器)。

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

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

现在让我们回到存储 MyType* 的 A 和 B vector 的位置。要获取 A 中不在 B 中的元素，我们首先调用 traversal_counter()。假设这是我们第一次调用它，那么它的遍历值为 1。

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

现在遍历 A 中的每个 MyType* 对象。计数器值与当前遍历值(1)不匹配的是 A 中不包含在 B 中的元素。

当遍历计数器溢出时会发生什么？在这种情况下，我们遍历存储在 ID 映射中的所有计数器，并将它们与遍历计数器本身一起设置回零。如果它是 32 位 unsigned int，这只需要在大约 40 亿次遍历中发生一次。

这是您可以应用于给定问题的最快解决方案。它可以对未排序的数据执行任何线性复杂度的集合操作(​​并且总是，不仅仅是在像哈希表这样的最佳情况下)，但它确实引入了一些复杂性，所以只有在你真的需要它时才考虑它。