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向量中進行保存。