C++地图:需要智能算法

Question

我有3份文件。F1，F2，F3。F1是包含200 K条目的主文件。F2和F3既可以包含超集，也可以包含条目的子集(300 K或100 K)。我的目标是在F1中找到一个不在F2和F3中的条目列表。到目前为止，我就是这样执行的。

1. 在F1 STL映射中加载C++条目。
2. 开始阅读F2。如果条目匹配，则减少计数(而不是从地图中擦除)。Count = F1的大小。如果计数为0，那么我知道F1中的所有条目都已在F2中找到，因此无需在F2中进一步遍历或遍历F3。
3. 我之所以没有“删除”地图中的条目，是因为我读到了C++ STL映射是一棵二叉树。看看我的条目，我的树绝对不可能是一棵平衡的二叉树。这是一棵非常深的树。所以任何擦除操作都是很昂贵的。查找操作可能也很昂贵，但是擦除操作必须在每次删除时重新创建树。
4. 因此，现在的问题是如何得出F2中存在的条目列表。我是否维护一个带有布尔标志"found = true或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';

    }
}

Answer 2

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

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

但这是错误的。对于std::map是如何工作的，您有一些奇怪的想法，并试图根据这些想法过早地优化它。因此，只需从地图中删除项目，在该映射中删除F2和F3中的元素后所剩下的就是您所需要的。如果标准映射不够快，请尝试散列映射，也就是unordered_map。

应该设置PS和unordered_set

Answer 3

为什么不同时阅读F2和F3，并将它们放在一个无序的集合中。

阅读F1并列出在这个集合中找不到的项目。