c++ - 将前缀和名称与名称列表匹配的算法

Question

我有一个 std::vector<std::string>目录中的所有文件:

// fileList
folder/file1
folder/file2
file3
file4.ext

和一个std::set<std::string>文件名和所有使用的文件夹前缀相同:

// set1
file2
file4.ext

// set2
folder

我需要生成 set1 中所有文件的完整(相对)路径，但如果不遍历 set2 就无法做到这一点 set1.size()次，乘以 fileList.size()

更新:一些说明:

上述示例的预期输出:

folder/file2
file4.ext

建议的(低效的？)解决方案，可能过于冗长且实现愚蠢:

// pseudo-code!
vector<string> allpossibleFullPaths( set1.size()*set2.size() );
vector<string> output;
foreach( prefix_in_set2 )
    foreach( filename_in_set1 )
        allpossibleFullpaths.push_back( set2[i] + "/" set1[i] )

foreach( filename_in_fileList )
    files.push_back( find( fileList[i] in allpossibleFullPaths ) );

(快速伪代码) 这看起来效率很低，有没有更好的方法来进行这些匹配？

谢谢!

PS:更好的方法是跟踪 double ，这样我就可以警告用户。

Answer 1

你不清楚的地方是:

• 给定如上所述的 set1 和 set2，如果 fileList 有“file4.ext”和“folder\file4.ext”会怎么样。你想要两个吗？还是 set1 中的文件列表保证是唯一的？

假设你想要两者，伪代码:

 foreach(pathname in fileList)
    separate pathname into path & filename.
    if path is not empty, but not in set2, skip to next pathname.
    if filename is in set1, output pathname.

由于集合查找应该是 O(1)，总复杂度是 O(2 * fileList.Length)

如果set1中的文件名是唯一的，可以统计输出路径名的个数，当达到set1.Length时提前退出。

遍历最长的集合似乎违反直觉，但它的查找也是最慢的，因此必须尽量减少对 fileList 的操作。

更新:这是完整的工作 C++ 代码(包括和使用省略)

void ListFiles()
{
    vector<string> fileList;
    fileList.push_back("folder/file1");
    fileList.push_back("folder/file2");
    fileList.push_back("file3");
    fileList.push_back("file4.ext");

    set<string> set1;
    set1.insert("file2");
    set1.insert("file4.ext");

    set<string> set2;
    set2.insert("folder");

    for(vector<string>::iterator iter = fileList.begin();
        iter != fileList.end();
        ++iter)
    {
        string pathname = *iter;
        string filename;
        string path;
        size_t pos = pathname.find('/');
        if (pos == string::npos || pos == 0)
            filename = pathname;
        else
        {
            path = pathname.substr(0, pos);
            if (set2.find(path) == set2.end())
                continue;
            filename = pathname.substr(pos+1);
        }
        if (set1.find(filename) != set1.end())
            cout << pathname << endl;
    }

}