C++ 映射 : Smart algorithm needed

Question

我有 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 中存在的条目列表。我是否维护一个带有 bool 标志“found = true or false”的结构？暗示在完成 F2 和 F3 后，我将遍历整个 STL 映射 - 然后查找已找到 = false 的值，然后开始将增量写入文件？

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

Answer 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';

    }
}