C++에서 그래프 표현 (정점 이웃)을위한 스마트 포인터 11

Question

그래프 표현에 C++ 11 스마트 포인터를 올바르게 사용하는 방법이 궁금합니다.

모든 정점 벡터가 포함 된 그래프 구조가 있다고 가정합니다. 또한 정점의 구조/클래스가 있습니다. 이 정점에는 모든 이웃 벡터 (인접성 목록)가 포함됩니다.

제 질문은 :이 그래프를 나타 내기 위해 어떤 종류의 포인터/스마트 포인터를 사용해야합니까?

이진 트리의 경우 부모 노드에 대해 원시 포인터를 사용해야합니다. 노드가 그 부모를 소유하지 않기 때문입니다. 노드가 자식의 소유권을 가지고 있기 때문에 이진 트리의 자식은 std :: unique_ptr로 나타낼 수 있습니다.

그러나 그래프에서 여러 노드가 공통 이웃을 가질 수 있습니다. 그래서,이 표준을 사용해야합니까 :: shared_ptr? 어쨌든 원시 포인터를 사용해야합니까?

Answer 1

노드 (또는 에지) 소유 전략을 먼저 디자인해야합니다.

예를 들어 사이트의 이진 트리 예제에서 상위 노드는 상위 노드가 아니라 하위 노드를 소유합니다. 이 설계는 루트 노드를 제외하고 트리의 모든 노드가 정확히 하나의 다른 노드에 의해 소유됨을 보장합니다.이 노드는 특별한 경우를 만들 수 있습니다. 이 예에서 각 노드는 정확히 하나의 소유자 (부모)를 가지므로 unique_ptr을 사용하여이 관계를 모델링 할 수 있습니다. 또한이 예제에서 자식에서 부모로의 링크는 소유하지 않은 링크이므로 소유하는 스마트 포인터로 모델링 할 수 없습니다.

이진 트리 예제에서 소유 그래프는 비순환적이고 지시되며 모든 노드는 에서 (포인터 소유)로 한 번만 지정됩니다.

보다 복잡한 예제에서 그래프는 비순환적이고 방향성이 있지만 노드는 번 이상을 가리킬 수 있습니다. 이러한 그래프는 pointee-to 링크가 pointee의 소유권을 공유하기 때문에 shared_ptr을 사용하여 pointed-to 링크를 모델링 할 수 있습니다.

그러나주의해야합니다. 그래프가 순환되면 즉시 shared_ptr을 더 이상 독점적으로 사용할 수 없습니다. 소유권주기를 설정할 때마다 :

A owns B which owns C which owns A 

메모리 누수를 설정합니다. 이러한 사이클은 shared_ptr 또는 unique_ptr으로 만들 수 있습니다. 그러나 실제적으로 사이클은 shared_ptr을 사용하면 더 자주 발생하는 경향이 있습니다. 소유권 다이어그램이 본질적으로 unique_ptr보다 복잡하기 때문일 수 있습니다.

shared_ptr에는 순환 소유권 패턴을 깨기위한 도우미 클래스가 포함되어 있습니다 : weak_ptr. 즉시주기를 설정하고, 그래서 모두 다음

A points to B and B points to A 

: 당신이 모델 노드 A와 B와 그래프는 방향성이 경우

A owns B which owns C which has a (non-owning) weak_ptr to A 

, 그리고이는 뭔가를 설정하는 데 사용할 수 있습니다 이러한 포인터 중 소유 포인터를 소유 할 수 없습니다. 이러한 상황에서는 무엇을 소유하고 있는지 설계해야합니다. 아마도 완전히 별도의 코드 조각이 모든 노드를 소유 할 수 있으며 모든 가장자리는 소유하지 않은 포인터로 표현 될 수 있습니다.아마도 그래프는 비주기 지향 에지 집합 (소유 포인터 표시)과 다른 모든 에지 (비 소유 포인터)로 분할 될 수 있습니다. 실제로 이것은 바이너리 트리 소유 자식 포인터와 비 소유 부모 포인터로 수행 한 작업과 정확히 같습니다.

디자인이 완료되면 디자인은 shared_ptr 및/또는 unique_ptr이 디자인을 구현하는 데 적합한 도구인지 여부를 알려줍니다. 무언가가 항상 고유하게 소유되면, unique_ptr가 가능한 옵션입니다. 어떤 항목을 다른 여러 항목에서 소유해야하는 경우 shared_ptr이 올바른 도구 일 수 있습니다 (확실히 unique_ptr이 아님). shared_ptr 소유권 그래프에 사이클이 포함되어있는 경우 해당 링크 중 일부를 weak_ptr으로 바꿔서 문제를 해결할 수 있습니다. 소유 그래프에서주기를 감지하고 중단시키지 않으면주기에 따라 메모리 누수가 발생합니다.