10

Graph および Node クラスによって実装された有向非巡回グラフがあります。各ノードには、子へのポインターのリストと、親へのポインターのリストがあります。一部のアルゴリズムは親リストへの高速アクセスを要求し、グラフは小さく、ノードあたりの接続数が少ないため、最近親を追加しました。メモリの問題はありません。

子リストは std::shared_ptr を使用して、ノードが少なくとも親を持つ限りメモリ内に保持されるようにします。しかし、ノードに親を所有させたくないので、親へのポインターにweak_ptrを使用しました。

しかし、アルゴリズムに問題がありました。アルゴリズムは、weak_ptr から新しい shared_ptr を作成する必要があるため、operator== を直接使用することはできず、std::find() などの標準関数を使用するには、my_weak_ptr.lock() を呼び出して比較するラムダ関数を作成する必要があります。一部の shared_ptr に。

shared_ptr に切り替えると、ノードの削除を担当するコードの小さなバグがメモリ リークにつながる可能性があります。または、既に削除されたノードへのポインターがある場合、コードは存在しないはずのノードにアクセスできるため、バグを見つけるのが非常に難しくなる可能性があります。ただし、shared_ptr での作業は、逆参照/削除などを行わないという点で、weak_ptr と同じくらい安全です。想定されていない場合は (生の C++ ポインターよりも優れています)、weak_ptr とは異なり、shared_ptr は逆参照できるため、std::find() を直接使用できます。

ここに「より良い」設計がありますか、それとも、weak_ptr::lock() の余分な操作を行うか、見つけにくいバグのリスクを冒すかどうかに応じて、この特定の状況の問題ですか?

4

2 に答える 2

12

あなたが自分で言ったようshared_ptrに、両方向で使用すると、メモリリークが発生し、見つけにくく、壊れにくい円が作成されます-shared_ptrが提供するすべての利点が(ほぼ)失われます。そうweak_ptrなるでしょう。

あなたのアルゴリズムはロックする必要があると言いますが、weak_ptr私は違います。アルゴリズムはshared_ptr、ノードから親を取得する必要があります。weak_ptr親ノードをロックし、親ノードまたは NULL に正しく設定された結果を返すのは、ノードのタスクです。

ノードが親をshared_ptrまたはとして保存するかどうかは、実装の詳細weak_ptrです。クライアントにのみを提供することで、その詳細をカプセル化しshared_ptrます。

class Node
{
  /* ... */
  std::weak_ptr<Node> parent;
public:
  std::shared_ptr<Node> getParent()
  {
    return parent.lock();
  }
};

編集: もちろん、概念的には、複数の親がいる場合も同じことが当てはまります。

Edit2: コメントでは、親リストを反復処理するアルゴリズムについて言及しているため、アルゴリズムごとにラムダを記述する必要があります。これらのアルゴリズムを頻繁に使用する場合は、ターゲットを自動的にロックしてweak_ptr返すイテレータ アダプタを作成することを検討してshared_ptrください。

template <class WPIterator>
struct LockTheWeakIterator
{
  //static_assert that WPiterator's value_type is some weak_ptr
  //typedef all those iterator typedefs
  typedef typename WPIterator::value_type::element_type element_type;

  shared_ptr<element_type> operator*()
  { return iter->lock(); }

  //provide all the other operators - boost.operators might help with that...

  WPIterator iter;
};

template <class IT>
LockTheWeakIterator<It> lockTheWeak(It iter);


//somewhere...
auto theParentIter = std::find_if(lockTheWeak(parents.begin()), 
  lockTheWeak(parents.end()), 
  whatIAmLookingFor);
于 2013-01-28T13:41:16.603 に答える
3

ほとんどの有向非巡回グラフは、親への弱いポインターをまったく必要としないはずですが、単純なポインターで機能します。どちらの場合も、ノードが削除されたら、各クライアントの親リストから自分自身を削除するのは各ノードの責任です。特別な状況で親ポインターから共有ポインターを取得する必要がある場合は、現在 lock() を使用するのと同様の方法で std::shared_from_this を使用できます。このようにして、作業を保存して、必要な場所だけで共有ポインターを作成して処理することができます。

于 2013-01-28T14:02:04.413 に答える