1

我有一个文件列表（存储为 c 样式字符串），我将对其执行搜索，我将删除那些与我的参数不匹配的文件。用于此目的的最佳容器是什么？我现在正在考虑设置。请注意，文件列表永远不会比初始化时大。我只会从容器中删除。

4

6 回答 6

3

我绝对不会使用集合——你不需要对它进行排序，所以使用集合没有意义。Set 通常实现为自平衡树，在您的情况下不需要自平衡算法。

如果您打算执行一次此操作，我将使用带有 remove_if 的 std::vector（来自 <algorithm>），然后是擦除。如果您以前没有使用过 remove_if，它的作用是遍历所有相关项并将所有相关项向下移动，覆盖该过程中不相关的项。您必须在其后进行擦除以减小矢量的大小。像这样：

std::vector<const char*> files;
files.erase(remove_if(files.begin(), files.end(), RemovePredicate()), files.end());

如果你想利用它的 O(1) 删除时间属性，编写代码来用 std::list 做同样的事情会有点困难。看到你只是在做这个一次性的操作，可能会花很少的时间你甚至不会注意到它，我建议你这样做，因为这是最简单的方法。

老实说，我认为您不会看到 std::list 和 std::vector 方法之间的速度差异太大。矢量方法只复制每个值一次，因此它实际上非常快，但占用的空间要少得多。在我看来，只有当您在整个应用程序的生命周期中进行大量添加和删除操作时，才真正合理地使用 std::list 并使用三倍的空间。

于 2009-01-29T01:00:56.113 回答
2

std::set 中的元素必须是唯一的，因此除非文件名是全局唯一的，否则这将不适合您的需求。

我可能会推荐一个 std::list。

于 2009-01-29T00:24:33.750 回答
1

来自SGI：

  • Avector是一个Sequence，支持随机访问元素，在末尾固定时间插入和移除元素，在开始或中间线性时间插入和移除元素。

  • Alist是一个双向链表。也就是说，它是一个既支持向前遍历又支持向后遍历的序列，以及（摊销的）常数时间在开头或结尾或中间插入和移除元素。

  • Anslist是一个单向链表：其中每个元素都链接到下一个元素，但不链接到前一个元素。也就是说，它是一个支持前向但不支持后向遍历和（摊销）恒定时间插入和删除元素的序列。

  • Set是一个存储 Key 类型对象的有序关联容器。Set是一个简单关联容器，这意味着它的值类型以及它的键类型都是 Key。它也是一个独特的关联容器，这意味着没有两个元素是相同的。

  • Multiset是一个存储 Key 类型对象的有序关联容器。Multiset是一个简单关联容器，这意味着它的值类型以及它的键类型都是 Key。它也是一个多关联容器，这意味着两个或多个元素可能是相同的。

  • Hash_set是一个散列关联容器，用于存储 Key 类型的对象。Hash_set是一个简单关联容器，这意味着它的值类型以及它的键类型都是 Key。它也是一个唯一关联容器，这意味着没有两个元素使用二进制谓词 EqualKey 比较相等。

  • Hash_multiset是一个散列关联容器，用于存储 Key 类型的对象。Hash_multiset是一个简单的关联容器，这意味着它的值类型以及它的键类型都是 Key。它也是一个多关联容器，这意味着两个或多个元素可以使用二进制谓词 EqualKey 比较相等。

（有些容器被省略了。）

hash_set如果您只需要一个快速且不包含多个相同键的容器， 我会选择。hash_multiset如果您这样做，set或者multiset您希望对字符串进行排序，或者list您slist希望字符串保持其插入顺序。

在您建立您的列表/集合后，使用remove_if根据您的条件过滤掉您的项目。

于 2009-01-29T00:29:10.093 回答
0

我将从扔掉向量开始，因为它是一个顺序容器。设置，我相信接近于顺序或散列。我会避免这种情况。双向链表，stl 列表就是其中之一，有两个指针和节点。基本上，要删除一个项目，它会破坏链然后用指针重新连接两个部分。

于 2009-01-29T00:20:54.163 回答
0

假设您的搜索条件不依赖于文件名（即您搜索内容、文件大小等），因此您不能使用集合，我会选择list. 构建整个列表需要 O(N)，每次删除需要 O(1)。

如果你想让它更快，并且不坚持使用现成的 STL 容器，我会：

  1. 用一个vector
  2. 使用假删除删除，即。将项目标记为已删除
  3. 当已删除/所有项目的比率超过某个阈值时，我会过滤这些项目remove_if

这应该会给你最好的空间/时间/缓存性能。（尽管您应该确定它的轮廓）

于 2009-01-29T00:46:17.967 回答
0

您可以使用两个列表/向量/任何东西：

using namespace std;

vector<const char *> files;

files.push_back("foo.bat");
files.push_back("bar.txt");

vector<const char *> good_files;  // Maybe reserve elements given files.size()?

for(vector<const char *>::const_iterator i = files.begin(); i != files.end(); ++i) {
    if(file_is_good(*i)) {
        new_files.push_back(*i);
    }
}
于 2009-01-29T00:51:01.873 回答