1

我有 3 个文件。F1，F2，F3。F1 是具有 200K 条目的主文件。F2 和 F3 可以包含超集或条目的子集（300K 或 100K）。我的目标是得出 F1 中不在 F2 和 F3 中的条目列表。到目前为止，这就是我实现它的方式。

  1. 在 C++ STL 映射中加载 F1 条目。
  2. 开始阅读 F2。如果条目匹配，则减少计数（而不是从映射中删除）。计数 = F1 开始的大小。如果计数为 0，那么我知道 F1 中的所有条目都已在 F2 中找到，因此无需在 F2 中进一步遍历或遍历 F3。
  3. 我没有从我的地图中“删除”条目的原因是我读到 C++ STL 地图是一棵二叉树。看看我的条目，我的树绝对不可能是平衡的二叉树。这是一棵极深的树。因此，任何擦除操作都变得昂贵。查找操作也可能很昂贵，但擦除操作必须在每次删除时重新创建树。
  4. 所以现在的问题是我如何到达 F2 中存在的条目列表。我是否维护一个带有布尔标志“found = true or false”的结构？暗示在完成 F2 和 F3 之后，我会遍历整个 STL 映射 - 然后查找找到 = false 的值，然后开始将增量写入文件？

有什么聪明、有效的方法来做到这一点？

4

3 回答 3

1

由于您在评论中说您的输入已经排序，所以完全避免使用容器：

#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-23T15:44:21.033 回答
0

为什么不同时读取 F2 和 F3 并将它们放入无序集合中。

阅读F1，吐出这组里没有的那些项目。

于 2013-02-23T05:35:39.840 回答
0

我不知道你从哪里得出这个结论：

我的树绝对不可能成为平衡的二叉树。

但这是错误的。您对 std::map 的工作方式有奇怪的想法，并尝试根据这些想法过早地对其进行优化。因此，只需从地图中删除项目，从该地图中的 F2 和 F3 删除元素后剩下的就是您需要的。如果标准映射不够快，请尝试哈希映射，即 unordered_map。

PS，这应该设置和 unordered_set

于 2013-02-23T05:08:20.550 回答