如果一个字符串的值是另一个字符串的一部分，从QStringList中删除该字符串

Question

我想从QStringList中删除一个字符串（以下代码中的folders），如果它包含在同一列表中的另一个字符串中。 例如：" /tmp/a /tmp/b /tmp/a/aa /tmp/c /tmp/a/aa/aaa /tmp/d" 我想删除第1个和第3个字符串，因为它们包含在第5个字符串中。我知道如何在bash中使用grep来做到这一点，但是如何在Qt中实现呢？请注意保留原有的HTML标签。

void MainWindow::on_toolButtonSourceFolders_clicked()
{
    QString startDir = lineEditStartFolder->text();
    QFileDialog* folderDialog = new QFileDialog(this);
    folderDialog->setDirectory(lineEditStartFolder->text());
    folderDialog->setFileMode(QFileDialog::Directory);
    folderDialog->setOption(QFileDialog::DontUseNativeDialog, true);
    folderDialog->setOption(QFileDialog::ShowDirsOnly, true);
    folderDialog->setOption(QFileDialog::DontResolveSymlinks, true);
    QListView *folderList = folderDialog->findChild<QListView*>("listView");
    if (folderList) {
        folderList->setSelectionMode(QAbstractItemView::MultiSelection);
    }
    QTreeView *folderTree = folderDialog->findChild<QTreeView*>();
    if (folderTree) {
        folderTree->setSelectionMode(QAbstractItemView::MultiSelection);
    }

    folderDialog->exec();
    QStringList folders = folderDialog->selectedFiles();
    if (!folders.isEmpty())
            listWidget->addItems(folders);
}

完整的代码可在https://github.com/FluxFlux/qdir2mod获取。

- FluxFlux

---

第三个文件夹如何被“包含”在另一个文件夹中？您的任务描述不准确，但即使如此：真正的用例是什么？ - László Papp

@最终比赛：感谢提示。我已经修复了“第三个”文件夹。最终的应用程序将用于将文件夹合并成基于squashfs的文件。我已经在github上添加了完整代码的URL。 - FluxFlux

这个算法必须表现良好吗？在最坏情况下，你有多少个文件夹？最慢的算法是O(n^2)，否则如果它还没有排序，排序可能会加速它。你也可以构建一个Trie并保留叶节点。 - László Papp

@最终比赛：我将有一个预计的最大文件夹数量<=20。 - FluxFlux

@最终比赛：现在去客户那边工作了 ;) - FluxFlux

Answer 1

如评论中所示，由于目录的最大数量为20个，因此我不会费心去优化算法，所以我只会选择最简单的方法：

QStringList folders = folderDialog->selectedFiles();
QStringList outputFolders = folders;
foreach (const QString &folder, folders) {
    foreach (const QString &f, folders) {
        if (f.contains(folder))
            outputFolders.removeOne(folder);
    }
}

你也可以避免使用临时副本，但这会使代码变得更加复杂，对于仅有20个“文件夹”来说不值得。

此外，请注意，“文件夹”是GUI术语。你所指的是文件和目录，这更具普适性。最好使用正确的术语，而不是仅限于GUI术语。

- László Papp

---

“removeOne”和“contains”可能是O(n)的，所以你的代码将会是O(n^3)，即使只有20个项目也很糟糕。而且，由于你没有处理“f==folder”的情况，列表将始终为空。 - alexisdm

@alexisdm：感谢您宝贵的评论。您是正确的！ - FluxFlux

@最终比赛：非常感谢您的答案！稍作修改后，我已经解决了我的问题。 :D - FluxFlux

Answer 2

稍作修改后，我解决了这个问题：

QStringList folders = folderDialog->selectedFiles();
QStringList outputFolders = folders;
foreach (const QString &folder, folders) {
    foreach (const QString &f, folders) {
        const QString &cfolder = (folder + "/");
        if (f.contains(cfolder))
            outputFolders.removeOne(folder);
    }
}
if (!outputFolders.isEmpty())
        listWidget->addItems(outputFolders);

- FluxFlux

---

你不应该在目录中使用 contains，而应该使用 startsWith（例如，字符串 /tmp/tmp/a/b 包含 /tmp/a，这不是你想要的）。 - alexisdm

@alexisdm：再次感谢您宝贵的评论。 :D - FluxFlux