C++ Map：需要智能算法

我有3個文件。 F1，F2，F3。 F1是具有200K條目的主文件。 F2和F3可以包含一個超集或一個子集（300K或100K）。我的目標是獲得F1中不在F2和F3中的條目列表。這是我迄今爲止實施的方式。C++ Map：需要智能算法

在C++ STL映射中加載F1條目。
開始閱讀F2。如果條目匹配，減少計數（不從地圖上擦除）。 Count =開始的F1大小。如果計數爲0，那麼我知道F1中的所有條目都已經在F2中找到了，所以不需要在F2中進一步遍歷或者遍歷F3。
我不是從我的地圖中「擦除」條目的原因是我讀了C++ STL地圖是一棵二叉樹。看着我的參賽作品，我的樹絕對不會是一個平衡的二叉樹。這是一棵非常深的樹。所以任何擦除操作都變得昂貴。查找操作也可能很昂貴，但擦除操作必須在每次刪除時重新創建樹。
所以現在的問題是如何到達F2中存在的條目列表。我是否維護一個帶有布爾型標誌「found = true或false」的結構？暗示在完成F2和F3之後，我回溯整個STL映射 - 然後查找已找到= false的值，然後開始將delta寫入文件中？

任何明智，有效的方法來做到這一點？

2013-02-23 Apad

你知道條目中的文件的順序什麼？例如，它們是按照一些自然的（和文件之間的一致性）順序排序的嗎？如果是這樣，你可以以各種方式利用它...如果不是，使用'std :: unordered_map'而不是'std :: map'（即散列表而不是樹）是一個明顯的更改。 – addaon 2013-02-23 05:02:58

你的問題不清楚。起初你說你的目標是找到F1中不是F2或F3的條目，那麼你說你需要找到F2中存在的條目。你需要什麼，作爲輸出/結果？ – Tawnos 2013-02-23 05:03:40

對不起。我打算問，到達F1中不在F2和F3的參賽作品。 F1，F2和F3中的所有條目都進行了排序，並且這些條目實質上是具有文件名的目錄路徑。因此，條目類似於a/a1/b，a/a1/b/c，a/a1/b/c/d，a/a2，a/a2/b，a/a2/b/b1，a/a2/b/b1/c等。無序地圖是否有意義？任何其他方式來達到這個？ – Apad 2013-02-23 05:13:18

我不知道從哪裏得到這樣的結論：

是絕對沒有辦法我的樹將是一個平衡二叉樹樹。

但它是錯誤的。你對std :: map如何工作有着奇怪的想法，並根據這個想法儘量優化它。因此，只需從地圖中刪除項目，刪除該地圖中的F2和F3元素後剩下的內容就是您需要的。如果標準地圖速度不夠快，請嘗試散列地圖aka unordered_map。

PS，這應設置並unordered_set

來源

2013-02-23 05:08:20 Slava

爲什麼在這兩個F2和F3不識字，把他們在一個無序的。

閱讀F1並吐出這些設置中找不到的物品。

來源

2013-02-23 05:35:39

既然你在評論你的投入已經測序說，只是避免容器完全：

#include <iostream> 
#include <fstream> 
#include <string> 
using namespace std; 
int main() 
{ 
    ifstream f1("f1.data"), f2("f2.data"), f3("f3.data"); 
    string f1entry, f2entry, f3entry; 

    while (getline(f1,f1entry)) { 
     while (f2 && f2entry < f1entry) getline(f2,f2entry); 
     while (f3 && f3entry < f1entry) getline(f3,f3entry); 
     if (f1entry != f2entry 
      && f1entry != f3entry) 
      cout << f1entry << '\n'; 

    } 
}

來源

2013-02-23 15:44:21 jthill

C++ Map：需要智能算法

回答

相關問題