2

I have a code with nested traversals involving STL containers. In particular I have a top container ( a list) which contains sublists and those sublists contain further sublists. For e.g. In a DICOM structure, a patient can have multiple Studies and each Study can have multiple Series. I have to perform some operation on Series objects and the only way to reach them is to drill down deep in a loop as shown below.

The pseudocode looks like this.

STLContainer top;
STLContainer::iterator top_iter;

for ( top_iter= top.begin(); top_iter != top.end(); ++top_iter) {
 STLContainer mid = *top_iter;
 STLContainer::iterator mid_iter;

 for ( mid_iter = mid.begin(); mid_iter!= mid.end(); ++mid_iter) {
  STLContainer bottom = *mid_iter;
  STLContainer::iterator bottom_iter;

  for(bottom_iter = bottom.begin(); bottom_iter != bottom.end(); ++bottom_iter){
     ExecuteSomething(*bottom_iter); // Finally do something with the stored object
  }
 }

}

Now If I have to execute a series on operations repeatedly on these 'bottom' objects, I have to do this traversal again and again. If i wish to use STL Algorithms, I would need to write atleast 3 lines of "for_each" for each level of nesting.

Does anyone know of a technique to shorten this code which can work a bit like this?

// Drills down to the deepest nested container
for_each(top.begin(), top.end(), DrillDownAndExecuteOnBottom());

which can work in just one single line? Something like this? Thanks!

4

3 に答える 3

3

コンテナがすべて同じ要素タイプではないと仮定します。

struct DrillDownAndExecuteOnBottom
{
  template<typename T>
    void operator()(T& t) const
    { for_each(t.begin(), t.end(), *this); }

  void operator()(Bottom& b) const
  { ExecuteSomething(b); }
};

これにより、オブジェクトに到達するまで深さ優先探索が実行されBottomます。

于 2012-06-06T17:18:09.310 に答える
1

トラバーサルを1回記述し、ラムダを使用してカプセル化できます。

void for_each_bottom( Top &top, const std::function<void(Bottom &)> &fn ) {  
    for (auto t = top.begin(); t != top.end(); ++t)  
        for (auto m = t->begin(); m != t->end(); ++m)  
            for (auto b = m->begin(); b != b->end(); ++b)  
                 fn( *b );

}  

void demo( Top &top ) {
    for_each_bottom( top, []( Bottom &bottom ) {
        ExecuteSomething( bottom );
    } );
}

(必要に応じて、トラバーサルにJonathan Wakelyの再帰/テンプレートアプローチを使用します。これらのネストされたループは単純ですが、あまり一般的ではありません。また、必要に応じて、std ::function<>の代わりにテンプレートタイプを使用してください。必要な場合を除きます。)

于 2012-06-06T17:20:13.603 に答える
0

トリックを実行する必要がある再帰関数のセミ擬似コードを次に示します。

void iterate(Container c)
{
    for (Iterator iter = c.begin(); iter != c.end(); iter++)
    {
        if (*iter is a Container)  // I forget how to do type-checking in C++
            iterate(*iter);
        else
            ExecuteSomething(*iter);
    }
}

編集:

このようなものはより柔軟かもしれません(C++が関数ポインターをCとは異なる方法で処理するかどうかを覚えていません/それらを利用するためのより良い方法がありますが、何でも)

void recursiveIterateAndExecute(Container c, void func(Container))
{
    for (Iterator iter = c.begin(); iter != c.end(); iter++)
    {
        if (*iter is a Container)  // I forget how to do type-checking in C++
            recursiveIterateAndExecute(*iter, func);
        else
            func(*iter);
    }
}

これらをSTLアルゴリズムにさらに一致するように修正する方法はおそらくありますが、C ++で多くの作業を行っていないため、実際にはコメントできません。

于 2012-06-06T16:21:31.633 に答える