[C++] 위크포인터와 순환 참조

해당 글을 참고하여 작성된 글입니다.

몇몇 이미지가 업로드 되지 않네요.. 추후에 수정하도록 하겠습니다.

---

.NET과 Java의 가비지콜렉터는 순환 참조 문제를 감지하고 해소시켜줄 수 있다. 그러나 c++에서 이 문제를 다루기는 그리 쉽지만은 않다.

순환참조란

다음 상황을 가정해보자

// C# version
class Person {
  public Person(string name) {
    this.Name = name;
    Console.WriteLine(this.Name + " instance created.");
  }

  ~Person() {
    Console.WriteLine(this.Name + " instance to be disposed.");
  }

  public string Name { get; private set; }

  private Person spouse;

  public Person Spouse {
    get { return spouse; }
    set { this.spouse = value; spouse.spouse = this; }
  }
}

class CircularReference {
  static void GetCoupleMarried() {
    Person husband = new Person("John"), wife = new Person("Pocahontas");
    husband.Spouse = wife;
    Console.WriteLine(husband.Name + "'s wife is " + husband.Spouse.Name + ".");
    Console.WriteLine(wife.Name + "'s husband is " + wife.Spouse.Name + ".");
  }

  static void Main(string[] args) {
    GetCoupleMarried();
    GC.Collect();
  }
}

아래는 자바에서의 순환참조 상황이다.

// Java version
public class Person {
  public Person(String name) {
    this.name = name;
    System.out.println(this.name + " instance created.");
  }
	
  protected void finalize() throws Throwable {
    System.out.println(this.name + " instance to be disposed.");
  }

  // no auto-implemented properties in Java	
  private String name;
	
  public String getName() {
    return name;
  }
	
  private Person spouse;
	
  public Spouse getSpouse() {
    return spouse;
  }

  public void setSpouse(Person spouse) {
    this.spouse = spouse;
    spouse.spouse = this;
  }
}

public class CircularReference {
  static void getCoupleMarried() {
    Person husband = new Person("John"), wife = new Person("Pocahontas");
    husband.setSpouse(wife);
    System.out.println(husband.getName() + "'s wife is " + husband.getSpouse().getName() + ".");
    System.out.println(wife.getName() + "'s husband is " + wife.getSpouse().getName() + ".");
  }
	
  public static void main(String[] args) {
    getCoupleMarried();
    System.gc();
  }
}

메인함수는 남자와 여자의 인스턴스를 생성하고, 그 둘을 결혼시킴으로써 해당 인스턴스의 배우자로 서로를 지목하도록 만든다. 실행 결과는 다음과 같다.

John  instance created.
Pocahontas  instance created.
John's  wife is Pocahontas.
Pocahontas's  husband is John.
Pocahontas  instance to be disposed.
John  instance to be disposed.

CLR과 JVM의 가비지콜렉터는 두 인스턴스가 해제될 때 순환참조를 감지하고 이를 처리해준다. 그러나 c++에서는 이를 자동으로 처리할 수 없다.
아래는 위 코드를 cpp로 그대로 포팅한 것이다.

// person.h – Buggy version
#ifndef PERSON_H_
#define PERSON_H_

#include <memory>
#include <string>

using namespace std;

class person {
  friend void get_couple_married(shared_ptr<person>, shared_ptr<person>);
public:
  person() = delete;
  person(const string);
  ~person();

  string get_name() const;
  shared_ptr<person> get_spouse() const;
private:
  string name_;
  typedef shared_ptr<person> spouse_ptr;
  spouse_ptr spouse_;

  void set_spouse(const shared_ptr<person>);
};

#endif /* PERSON_H_ */
/* ---------------------------------- */
// person.cpp
#include "person.h"
#include <iostream>
#include <stdexcept>

using namespace std;

person::person(const string name) : name_{name} {
  cout << name_ << " instance created." << endl;
}

person::~person() {
  cout << name_ << " instance to be disposed." << endl;
}

string person::get_name() const { return name_; }

shared_ptr<person> person::get_spouse() const { return spouse_; } 

void person::set_spouse(const shared_ptr<person> sp) {
  this->spouse_ = sp;
}

void get_couple_married(shared_ptr<person> husband, shared_ptr<person> wife) {
  // checks arguments aren’t null
  if ((husband==nullptr)||(wife==nullptr))
    throw invalid_argument("get_couple_married(husband, wife): can't get nullptr as couple member");

  // checks arguments aren’t the same instance
  if (husband.get()==wife.get())
    throw invalid_argument("get_couple_married(husband, wife): husband and wife can't be the same person");

  // Here’s where the issue is produced. Both husband and wife get each other’s shared_ptr
  // targeting them
  husband->set_spouse(wife);
  wife->set_spouse(husband);
}
/* ---------------------------------- */
// main.cpp
#include <iostream>
#include "person.h"

using namespace std;

void get_couple_married() {
  shared_ptr<person> husband = make_shared<person>("John"), wife = make_shared<person>("Pocahontas");
  get_couple_married(husband, wife);
  cout << husband->get_name() << "'s wife is " << husband->get_spouse()->get_name() << "." << endl;
  cout << wife->get_name() << "'s husband is " << wife->get_spouse()->get_name() << "." << endl;
}

int main() {
  get_couple_married();
  return 0;
}

위 코드를 실행시켜보면 예상 c#과 java에서의 결과와 다른 결과가 나온다.

아내와 남편의 인스턴스가 서로를 강하게 참조하고 있기 때문에 소멸자가 불리지 않기 때문이다.

실행과정을 나타내면 아래와 같다.

• husband와 wife에 대한 shared_ptr 생성(레퍼런스 카운터(h, w) : 1, 1)
• 둘을 결혼시킴(2, 2)
• get_couple_married 스코프를 벗어나면서 맨 처음 만들었던 스마트포인터 소멸 (1, 1)
• 레퍼런스 카운트가 0이 된 객체가 없는 상태에서 프로그램 종료

이를 해결하기 위해서는 둘 중 하나의 인스턴스가 나머지 하나를 약하게 참조하도록 변환해야한다. 아래 코드는 이에 대한 구현이다.

// person.h – Correct version (see Figure 2)
#ifndef PERSON_H_
#define PERSON_H_

#include <memory>
#include <string>

using namespace std;

class person {
  friend void get_couple_married(shared_ptr<person>, shared_ptr<person>);
public:
  person() = delete;
  person(const string);
  ~person();

  string get_name() const;
  shared_ptr<person> get_spouse() const;
private:
  // nested class that models a smart pointer that could be strong or weak
  class spouse_ptr {
  private:
    shared_ptr<person> strong_;
    weak_ptr<person> weak_;
    spouse_ptr& set(const shared_ptr<person>);
  public:
    spouse_ptr();
    spouse_ptr(const shared_ptr<person>);

    spouse_ptr& operator=(const shared_ptr<person>);

    shared_ptr<person> get() const;
  };
  string name_;
  spouse_ptr spouse_;

  void set_spouse(const shared_ptr<person>);
};

#endif /* PERSON_H_ */
/* ---------------------------------- */
// person.cpp
#include "person.h"
#include <iostream>
#include <stdexcept>

using namespace std;

person::person(const string name) : name_{name} {
  cout << name_ << " instance created." << endl;
}

person::~person() {
  cout << name_ << " instance to be disposed." << endl;
}

string person::get_name() const { return name_; }

shared_ptr<person> person::get_spouse() const { return this->spouse_.get(); } 

void person::set_spouse(const shared_ptr<person> sp) {
  this->spouse_ = sp;
}

person::spouse_ptr::spouse_ptr() : strong_{nullptr}, weak_{} {}
person::spouse_ptr::spouse_ptr(const shared_ptr<person> sp) : strong_{nullptr}, weak_{} {
  set(sp);
}

person::spouse_ptr& person::spouse_ptr::operator=(const shared_ptr<person> sp) {
  return set(sp);
}

shared_ptr<person> person::spouse_ptr::get() const {
  if (strong_!=nullptr)
    return strong_;
  else
    return weak_.lock();
}

person::spouse_ptr& person::spouse_ptr::set(const shared_ptr<person> sp) {
  // the strong or weak reference is used depending on 
  if (sp->get_spouse()==nullptr) {
    strong_ = sp;
    weak_.reset();
  } else {
    strong_ = nullptr;
    weak_ = sp;
  }

  return *this;
}

void get_couple_married(shared_ptr<person> husband, shared_ptr<person> wife) {
  // checks arguments aren’t null
  if ((husband==nullptr)||(wife==nullptr))
    throw invalid_argument("get_couple_married(husband, wife): can't get nullptr as couple member");

  // checks arguments aren’t the same instance
  if (husband.get()==wife.get())
    throw invalid_argument("get_couple_married(husband, wife): husband and wife can't be the same person");

  // the husband strongly points to his wife, while she weakly points back to him
  // (see function person::spouse_ptr::set)
  husband->set_spouse(wife);
  wife->set_spouse(husband);
}
/* ---------------------------------- */
// main.cpp
#include <iostream>
#include "person.h"

using namespace std;

void get_couple_married() {
  shared_ptr<person> husband = make_shared<person>("John"), wife = make_shared<person>("Pocahontas");
  get_couple_married(husband, wife);
  cout << husband->get_name() << "'s wife is " << husband->get_spouse()->get_name() << "." << endl;
  cout << wife->get_name() << "'s husband is " << wife->get_spouse()->get_name() << "." << endl;
}

int main() {
  get_couple_married();
  return 0;
}

위 코드의 경우 다음과 같은 순서로 동작한다.

• husband와 wife의 shared_ptr 생성 (레퍼런스카운트(h, w) : 1, 1)
• 결혼하면서 h는 w를 강하게 참조, w는 h를 약하게 참조 (레퍼런스 카운트 : 1, 2)
• get_couple_married 스코프를 벗어나면서 맨 처음 만들었던 shared_ptr 소멸 (레퍼런스 카운트 : 0, 1)
• 레퍼런스 카운트가 0이 된 남편의 소멸자 호출
  • 소멸자 내부 로직 수행(cout)
  • 아내를 참조하고 있는 shared_ptr 소멸 (0, 0)
• 레퍼런스 카운트가 0이 된 아내의 소멸자 호출

소멸자 호출 순서는 java와 c#과 다르긴 하지만, 순환참조 문제는 해결되었다. 그러나 다른 형태의 순환참조 문제가 발생하였을 경우(ex. 클래스 타입이 변할 경우, 순환참조에 참여하는 객체가 3개 이상일 경우 등등) 이 코드를 재사용할 수 없다는 문제점이 존재한다.

순환참조 문제 감지 복잡도

위 배우자 예시 코드는 순환참조 문제를 일부러 발생시킨 코드이기 때문에 deterministic하고 실제 발생하는 순환참조의 문제보다 해결하기 훨씬 쉽다. 실제로는 서로 다른 타입(heterogeneous)의 인스턴스들이 서로를 참조하고 있기도 하고, 비결정적인 상황이 많이 발생하기에 해결하기 복잡한 경우가 많다. 가장 쉬운 예시로, 다음과 같은 상황을 생각해볼 수 있다(circular references between homogeneous types).

모든 사람마다 베스트프렌드를 참조하고 있는 상황이다. 이때는 베프를 선택할 때마다 순환참조가 발생하는지 확인해야하고, 발생하는 경우 weak_ptr로 이를 끊어줘야한다. 또한 순환참조 현상이 깨지는 경우, 기존의 약한참조(weak_ptr)를 강한참조(shared_ptr)로 바꿔주고 새로운 순환참조가 있는지 다시 확인해야한다.

따라서 이 경우 친구관계를 맺을 때의 시간복잡도는 O(n)으로 나타낼 수 있다.(n은 연결되어있는 노드의 개수)

// circular_ptr.h
#ifndef CIRCULAR_PTR_H_
#define CIRCULAR_PTR_H_

#include <memory>

using namespace std;

template <typename T>
class circular_ptr;

// this header only offers the prototype of this template function.
// Implementors of a concrete types T should provide specific versions, and make this
// function friend to T (see class person below this code).
template <typename T>
circular_ptr<T> *get_circular_ptr(const shared_ptr<T>&);

template <typename T>
class circular_ptr {
public:
  circular_ptr() : strong_{nullptr}, weak_{} {}

  // copy constructor
  circular_ptr(shared_ptr<T> &t) : strong_{nullptr}, weak_{} {
    set(t);
  }

  // copy assignment operator
  circular_ptr& operator=(shared_ptr<T> &t) {
    return set(t);
  }

  shared_ptr<T> get() const {
    if (strong_!=nullptr)
      return strong_;
    else
      return weak_.lock();
  }

  // whether circular_ptr uses a weak link to refer to a T instance.
  bool is_weak() {
    return !(weak_.expired());
  }

  // releases its link, whichever it is (strong or weak).
  bool reset() {
    // looks for a weak link that directly or not points to the this circular_ptr
    circular_ptr *weak_one = find_weak_link_reaching_this();

    // if found, means that there was a circular reference. That circular reference is
    // being broken in this reset. Consequently, the weak ptr must become strong.
    if (weak_one) {
        weak_one->strong_ = weak_one->weak_.lock();
        weak_one->weak_.reset();
      }

    strong_.reset();
    weak_.reset();

    return (weak_one);
  }

  bool operator==(const circular_ptr &other) const {
    return get()==other.get();
  }

  bool operator!=(const circular_ptr &other) const {
    return !(*this==other);
  }
protected:
  // this function is O(n) in non-deterministic cases. A deterministic circularity
  // scenario may override this function to get constant order of complexity.
  virtual bool is_this_reachable_from(const shared_ptr<T> &start) const {
    shared_ptr<T> current = start, currents_next;

    // it basically performs a walkthrough from start argument to see whether it reaches
    // this instance or null. If the former, returns true. False otherwise.
    if (current!=nullptr) {
        do {
            currents_next = get_circular_ptr(current)->get();
            if ((currents_next!=nullptr)&&(this==get_circular_ptr(currents_next))) {
                return true;
              }

            current = currents_next;
          }
        while ((current!=nullptr)&&(current!=start));
      }

    return false;
  }

  // same comment: if circularity is deterministic, this function could be overridden and
  // thus optimized
  virtual circular_ptr *find_weak_link_reaching_this() {
    circular_ptr *current = this, *weak_one = nullptr;
    // provided that there's no strong circular reference, either the chain ends in nullptr
    // or we reach a member that is weak
    while (current!=nullptr) {
        if (current->is_weak()) {
            weak_one = current;
            // now, it must be confirmed that *this is reachable from weak_one.
            do {
                if ((current = get_circular_ptr(current->get()))==this)
                  return weak_one;
              }
            while (current!=weak_one);
            // provided that weak_one is reachable from current, as weak_one is weak
            // because participates in a loop.
            break;
          }

        if (shared_ptr<T> t = current->get()) current = get_circular_ptr(t);
        else break;
      }

    return nullptr;
  }
private:
  shared_ptr<T> strong_;
  weak_ptr<T> weak_;

  circular_ptr& set(shared_ptr<T> &t) {
    if (t==nullptr) {
        reset();
      }
    else {
        bool cycle_already_detected = false;

        if (get()!=nullptr) {
            cycle_already_detected = reset();
          }

        // checking for cycle_already_detected helps avoid an extra round
        if ((cycle_already_detected)||( is_this_reachable_from(t)))
          weak_ = t;
        else
          strong_ = t;
      }

    return *this;
  }
};

#endif /* CIRCULAR_PTR_H_ */

// person.h
#ifndef PERSON_H_
#define PERSON_H_

#include <string>
#include <memory>
#include "circular_ptr.h"

using namespace std;

class person {
  friend circular_ptr<person> *get_circular_ptr(const shared_ptr<person>&);
public:
  person()=delete;
  person(const string);
  ~person();

  string get_name() const;
  void set_best_friend(shared_ptr<person>);
  shared_ptr<person> get_best_friend() const;
  void set_no_best_friend();
private:
  class best_friend_ptr : public circular_ptr<person> {
  public:
    best_friend_ptr();
    best_friend_ptr(shared_ptr<person>&);
    best_friend_ptr& operator=(shared_ptr<person>&);
  };

  string name_;
  best_friend_ptr best_friend_;
};

#endif /* PERSON_H_ */
/* ---------------------------------- */
// person.cpp
#include "person.h"
#include <iostream>
#include <stdexcept>

using namespace std;

person::person(const string name) : name_ {name}, best_friend_ {} {
  if (name_=="") throw invalid_argument("A person must have a non-empty name");
  cout << name_ << " instance created." << endl;
}

person::~person() {
  cout << name_ << " instance to be disposed." << endl;
}

string person::get_name() const {
  return name_;
}

void person::set_best_friend(shared_ptr<person> best_friend) {
  if (this==best_friend.get())
    throw invalid_argument("Best friend can't be self person");
  best_friend_ = best_friend;
}

shared_ptr<person> person::get_best_friend() const {
  return best_friend_.get();
}

void person::set_no_best_friend() {
  best_friend_.reset();
}

person::best_friend_ptr::best_friend_ptr() : circular_ptr::circular_ptr() {}
person::best_friend_ptr::best_friend_ptr(shared_ptr<person> &p) : circular_ptr::circular_ptr(p) {}

person::best_friend_ptr& person::best_friend_ptr::operator=(shared_ptr<person> &t) {
  return static_cast<person::best_friend_ptr&>(circular_ptr::operator=(t));
}

circular_ptr<person> *get_circular_ptr(const shared_ptr<person> &p) {
  return &(p->best_friend_);
}
/* ---------------------------------- */
// main.cpp
#include <iostream>
#include <string>
#include <memory>
#include <vector>
#include "person.h"

using namespace std;

void print_friendship(vector<shared_ptr<person>> vp) {
for (auto p : vp) {
      auto q = p->get_best_friend();
      cout << p->get_name() << "'s best friend is " << (q ? q->get_name() : "nobody") << endl;
    }
    cout << "\n";
}

void make_friends() {
  shared_ptr<person> john = make_shared<person>("John"),
                     charles = make_shared<person>("Charles"),
                     emma = make_shared<person>("Emma"),
                     cindy = make_shared<person>("Cindy"),
                     arthur = make_shared<person>("Arthur"),
                     laurie = make_shared<person>("Laurie");

  vector<shared_ptr<person>> vp = {john, charles, emma, cindy, arthur, laurie};

  john->set_best_friend(charles);  // strong
  charles->set_best_friend(emma);  // strong
  emma->set_best_friend(cindy);    // strong
  cindy->set_best_friend(arthur);  // strong
  arthur->set_best_friend(laurie); // strong
  laurie->set_best_friend(john);   // weak!
  print_friendship(vp);

  cindy->set_best_friend(charles); // weak, but also laurie’s ptr to john
                                   // becomes strong
  print_friendship(vp);

  john->set_best_friend(cindy);    // strong
  emma->set_best_friend(arthur);   // weak, but also cindy’s ptr to charles
                                   // becomes strong
  print_friendship(vp);

  charles->set_no_best_friend();   // emma’s ptr to arthur becomes strong
  print_friendship(vp);            // See Figure below this
}

int main() {
  make_friends();

  return 0;
}

위 코드의 실행 결과는 다음과 같다. (왜 저렇게되는지 궁금하면 코드 위에 있는 이미지들을 보자) 참조관계도 정상적으로 출력되고, 메모리 누수 없이 잘 해제되고 있는 모습이다.

순환참조 문제 회피

대부분의 문제상황은 프로그래밍 당시의 사고수준으로는 해결하기 힘들다. 비결정적인 순환참조 문제가 선형시간의 시간복잡도를 가질 수 밖에 없다면, 순환참조를 회피하는 방향으로 코드를 재구조하는 것도 방법 중 하나이다. 다음 코드는 베프 정보를 person 클래스의 인스턴스가 다른 인스턴스를 참조하는 방식으로 유지하던 것을 별도의 해쉬테이블을 만들어 관리하는 것으로 바꾼 코드이다.

#ifndef PERSON_H_
#define PERSON_H_

#include <string>
#include <memory>
#include <map>

using namespace std;

class person;

// this class models a table of friendship (name, best friend)
class friendship {
public:
  void set_best_friend(shared_ptr<person>, const shared_ptr<person>);
  shared_ptr<person> get_best_friend(const shared_ptr<person>) const;
  void set_no_best_friend(shared_ptr<person>);
private:
  // hashtable
  map<string, shared_ptr<person>> container_;
};

class person {
public:
  person()=delete;
  person(const string);
  ~person();

  string get_name() const;
private:
  string name_;
};

#endif /* PERSON_H_ */
/* ---------------------------------- */
// person.cpp
#include "person.h"
#include <iostream>
#include <stdexcept>

using namespace std;

void friendship::set_best_friend(shared_ptr<person> p, const shared_ptr<person> best_friend) {
  if (p.get()==best_friend.get())
    throw invalid_argument("Best friend can't be self person");

  auto name = p->get_name();
  container_.erase(name);
  if (best_friend)
    container_[name] = best_friend;
}

shared_ptr<person> friendship::get_best_friend(const shared_ptr<person> p) const {
  auto i = container_.find(p->get_name());
  if (i==end(container_))
    return nullptr;
  else
    return i->second;
}

void friendship::set_no_best_friend(shared_ptr<person> p) {
  set_best_friend(p, nullptr);
}

person::person(const string name) : name_ {name} {
  if (name_=="") throw invalid_argument("A person must have a non-empty name");
  cout << name_ << " instance created." << endl;
}

person::~person() {
  cout << name_ << " instance to be disposed." << endl;
}

string person::get_name() const {
  return name_;
}
/* ---------------------------------- */
// main.cpp
#include <iostream>
#include <string>
#include <memory>
#include <vector>
#include "person.h"

using namespace std;

void print_friendship(const vector<shared_ptr<person>> &vp, const friendship& f) {
for (auto p : vp) {
      auto q = f.get_best_friend(p);
      cout << p->get_name() << "'s best friend is " << (q ? q->get_name() : "nobody") << endl;
    }
    cout << "\n";
}

void make_friends() {
  shared_ptr<person> john = make_shared<person>("John"),
                     charles = make_shared<person>("Charles"),
                     emma = make_shared<person>("Emma"),
                     cindy = make_shared<person>("Cindy"),
                     arthur = make_shared<person>("Arthur"),
                     laurie = make_shared<person>("Laurie");

  friendship f;
  vector<shared_ptr<person>> vp = {john, charles, emma, cindy, arthur, laurie};

  // now friendship is kept outside person instances, to eliminate all chance of circular
  // references
  f.set_best_friend(john, charles);
  f.set_best_friend(charles, emma);
  f.set_best_friend(emma, cindy);
  f.set_best_friend(cindy, arthur);
  f.set_best_friend(arthur, laurie);
  f.set_best_friend(laurie, john);
  print_friendship(vp, f);

  f.set_best_friend(cindy, charles);
  print_friendship(vp, f);

  f.set_best_friend(john, cindy);
  f.set_best_friend(emma, arthur);
  print_friendship(vp, f);

  f.set_no_best_friend(charles);
  print_friendship(vp, f);
}

int main() {
  make_friends();

  return 0;
}

이렇게 만들면, 메모리 누수를 방지하면서도 시간복잡도를 O(log(n))으로 줄일 수 있다.(std::map의 시간복잡도)

첨언

cpp에서의 스마트포인터의 도입은 동적 메모리 관리를 위한 큰 도약임은 분명하다. shared_ptr은 레퍼런스 카운트를 구현하였고, weak_ptr은 이에 따르는 원형참조 문제를 보완해준다.
다만, 재귀함수처럼 언어가 그것을 지원해준다고 해서 반드시 사용해야하는 것은 아니다.

저의 의견이 아닌 원글 작성자의 의견입니다.