1

我有一个路径名列表，其中一些标有“包含子树”标志。我需要迭代所有路径，包括子树，但每个唯一路径只需要一次。

所以，如果我有这样一个目录树：

C:\Models\
C:\Models\A
C:\Models\A\1
C:\Models\B
C:\Models\B\1

和 2 个带有子树（输入）的选择路径：

{"C:\Models\", true}
{"C:\Models\A", true}

迭代时我需要避免以下路径重复：

C:\Models\
C:\Models\A
C:\Models\A\1
C:\Models\B
C:\Models\B\1
C:\Models\A   *** Duplicate ***
C:\Models\A\1 *** Duplicate ***

我决定使用vector + set：

std::vector<std::string> vecPaths;       // For iterating
std::set<std::string>    setUniquePaths; // For duplicates check

但这是记忆无效的决定，因为每条路径将出现 2 次 1) 在向量中和 2) 在集合中。

如何在不复制这些字符串的情况下提供字符串唯一性？

任务定义注意事项：

  • INPUT 是对的序列 {string path, bool includeSubtre}
  • OUTPUT 是一个路径向量，一个快照，用于未来的迭代。
4

5 回答 5

2

如果您只是要迭代std::vector<std::string>而不添加或删除元素（在单次迭代期间），那么为什么不使用一组指针/迭代器来复制重复项：

std::vector<std::string> subtreePaths = //the ones you want to iterate for
...
std::set<std::vector<std::string>::const_iterator> setUniquePaths;
for(auto iterS=subtreePaths.begin(); iterS!=subtreePaths.end(); ++iterS)
    for(auto iterP=vecPaths.begin(); iterP!=vecPaths.end(); ++iterP)
        if(matches(*iterP, *iterS) && setUniquePaths.insert(iterP).second)
            std::cout << *iterP << std::endl;    //or whatever

（当然auto是 C++11，请随意将其替换为符合 C++98/03 的相应迭代器类型）。

但也许我误解了你真正想要达到的目标。

编辑：如果您还没有vecPaths向量中的所有现有路径，并且您实际上想以某种方式迭代您的真实文件系统，vecPaths用所有找到（和重复清理）的路径构建向量，那么我的上述方法当然是垃圾，因为它假设仅对所有路径的已知向量进行基于字符串的迭代。

但如果是这种情况，您可以完全删除向量并使用单个std::set<std::string>来收集您遇到的所有路径（现在自动唯一）。不需要额外的载体。

于 2012-09-06T08:56:55.207 回答
2

到目前为止的评论主要集中在内存中的数据结构上，但重要的是要记住目录遍历非常受 IO 限制。给定输入

{"C:\Models\", true}
{"C:\Models\A", true}

您想跳过整个第二个目录遍历。因此，您不想在最后消除重复项。作为另一个例子，给定

{"C:\Models\A", true}
{"C:\Models\", true}

您想A在第二次枚举期间跳过子树。

因此，使用所有已知路径名中的两个 std::set<std::string>，一个用于非递归枚举目录，一个用于您确实枚举的目录。在递归枚举期间，跳过第二组中已经存在的任何子树。在输入结束时，您可以简单地合并这两个集合。

于 2012-09-06T09:09:23.583 回答
1

如果有很多条目，我会建立一个包含所有唯一目录名称（不是路径）的向量，并使用树（例如http://tree.phi-sci.com/）通过将 ID 序列放入向量中。要确定是否已经看到现有目录，请使用哈希映射为当前路径中的每个目录名称构建 ID 序列。如果路径完全匹配，请跳过它。如果没有，则将相关节点添加到树中以反映新路径。注意：这可能会导致树中的多个节点引用同一个 ID。

这是代码：

std::vector< std::string > directories; // THIS IS THE INPUT!
std::vector< std::string > directory_names;
std::unordered_map< std::string, size_t > name_to_id_map;
tree< size_t > directory_paths;
for (auto idir = directories.begin(); idir != directories.end(); ++idir) {
    // Convert directories to a sequence of IDs (if new names are found, add
    // them to 'directory_names' and 'name_to_id_map'.  This is pretty mechanical code.
    std::vector< size_t > id_sequence = convert( *idir );

    // Walk the tree looking for this ID sequence.
    tree<size_t>::sibling_iterator current_tree_node;
    bool found = true;
    for (auto iid = id_sequence.begin(); iid != id_sequence.end(); ++iid) {
       if ( found ) {
          if ( !directory_paths.is_valid( current_tree_node ) ) {
             // Find a match among the roots of the tree.  Note: There might be a more elegant way to do this.
             tree<size_t>::sibling_iterator iroot( directory_paths.head );
             tree<size_t>::sibling_iterator iroot_end( directory_paths.feet );
             ++iroot_end;

             // Note: If the tree is sorted, we can use equal_range!
             current_tree_node = std::find( iroot, iroot_end, *iid );
             found = ( current_tree_node != iroot_end );
          }
          else {
             // Find a match among the siblings of 'current_tree_node'.
             tree<size_t>::sibling_iterator ichild = directory_paths.begin_child( current_tree_node );
             tree<size_t>::sibling_iterator ichild_end = directory_paths.end_child( current_tree_node );

             // Note: If the tree is sorted, we can use equal_range!
             current_tree_node = std::find( ichild, ichild_end, *iid );
             found = ( current_tree_node != ichild_end );
          }
       }

       if ( !found ) {
          // Add this node to the tree as a child of current_tree_node.
          if ( directory_paths.is_valid( current_tree_node ) ) {
             current_tree_node = directory_paths.insert_after( current_tree_node, *iid );
          }
          else if ( !directory_paths.empty() ) {
             current_tree_node = directory_paths.insert_after( directory_paths.feet, *iid );
          }
          else {
             current_tree_node = directory_paths.set_head( *iid );
          }
       }
    }

    if ( !found ) {
       // This directory path (i.e. *idir) has not been seen before.
       ...
    }
 }

例如，以下输入将创建 5 个唯一名称（C:、Models、A、1、B）。

C:\Models\
C:\Models\A
C:\Models\A\1
C:\Models\B
C:\Models\B\1

处理完第一行后，树将有两个节点。处理完第二行后，树将具有三个节点。处理完第 3 行后，树将有四个节点。处理完第 4 行后，树将有五个节点。处理完第 5 行后，树将有六个节点。

如果我碰巧遇到：C:\Models\1\B，则不会向“directory_names”（或“name_to_id_map”）添加新条目，但树现在将有八个节点。

我相信这个实现非常节省内存，因为 1) directory_names 只存储子字符串，而不是完整路径，以及 2) 永远不会为共享同一路径的一部分的两个目录创建多个字符串。本质上，在处理每个新目录时，只存储有关名称和路径的唯一信息（不包括 'name_to_id_map' 的开销，这对于实现适当的运行时与内存平衡似乎很重要）。

注意：我不太明白您所说的“和 2 个带有子树（INPUT）的选择路径”是什么意思。

于 2012-09-06T16:28:51.380 回答
0

您可以使用boost::variant一个目录来存储节点。每个节点要么是一个文件，要么是一个目录：

typedef boost::variant<
      std::string
    , std::map<std::string, boost::recursive_variant_>
    > Tree;

map确保目录中没有重复的名称。

您可能需要添加函数来填充和遍历此递归数据结构。

于 2012-09-06T08:49:14.437 回答
-1

使用 shared_ptr。但是字符串可以实现为 COW，因此无需担心副本。

于 2012-09-06T08:30:48.140 回答