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：需要智能算法

回答

相关问题