1

パス名のリストがあり、そのうちのいくつかは「サブツリーを含める」フラグでマークされています。サブツリーを含むすべてのパスを反復する必要がありますが、一意のパスごとに 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 ***

ベクトル+セットを使用することにしました：

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

しかし、これはメモリ効率の悪い決定です。なぜなら、各パスは 1) ベクトルで、2) セットで 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}

2 番目のディレクトリ トラバーサル全体をスキップします。したがって、最後に重複を排除する必要はありません。別の例として、

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

A2 番目の列挙中にサブツリーをスキップしたい。

したがって、すべての既知のパス名のうち 2 つを使用します。1 std::set<std::string>つは非再帰的に列挙されたディレクトリ用で、もう 1 つは列挙したディレクトリ用です。再帰的な列挙中に、2 番目のセットに既に存在するサブツリーをスキップします。入力の最後に、簡単に 2 つのセットをマージできます。

于 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

最初の行が処理されると、ツリーには 2 つのノードが含まれます。2 行目が処理されると、ツリーには 3 つのノードが含まれます。3 行目が処理されると、ツリーには 4 つのノードが含まれます。4 行目が処理されると、ツリーには 5 つのノードが含まれます。5 行目が処理されると、ツリーには 6 つのノードが含まれます。

C:\Models\1\B に遭遇した場合、'directory_names' (または 'name_to_id_map') に新しいエントリは追加されませんが、ツリーには 8 つのノードが含まれます。

1) directory_names はフル パスではなく部分文字列のみを保存し、2) 同じパスの一部を共有する 2 つのディレクトリに対して複数の文字列が作成されることはないため、この実装は非常にメモリ効率が良いと思います。基本的に、新しいディレクトリが処理されるたびに、名前とパスに関する一意の情報のみが保存されます (「name_to_id_map」のオーバーヘッドは除きます。これは、適切なランタイムとメモリのバランスを実現するために重要と思われます)。

注：「およびサブツリー（INPUT）を持つ2つの選択されたパス」の意味がよくわかりませんでした。

于 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 に答える