数据结构-C++映射:需要智能算法

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中存在的条目列表。我是否维护一个带有布尔标志"find=true或false"的结构？暗示在完成F2和F3之后，我重新遍历整个STL映射，然后查找已找到=false的值，然后开始将delta写入文件

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

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中删除元素后剩下的就是您所需要的。如果标准映射不够快，请尝试哈希映射（也称为无序映射）。

PS，并且应该设置和取消设置

Answer 3

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

读取F1，并吐出在该集合中找不到的项目。