New Age C++

Weak Pointers and Circular References in C++ 11

In both .NET and Java, the garbage collector is smart enough to detect and release circular references. Dealing with circular references in C++ isn't as simple.

• By Diego Dagum
• 10/19/2012

In the first installment of this series on pointers, I covered the two most common smart pointers. One of them, shared_ptr, implements reference counting on its heap objects. A reference counter reaching 0 triggers an object deletion, avoiding memory leaks.

Today I'll cover weak_ptr, a complement intended to deal with circular references.

Circular References
Consider the code in Listing 1. The Main method instantiates a husband and his wife, then "marries" them by making each refer to the other as spouse. Running the program would show this output:

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.

In both .NET and Java, the garbage collector is smart enough to detect and release circular references. Dealing with circular references in C++, however, isn't as simple. Listing 2 contains a buggy C++ port of Listing 1.

Run the code in Listing 2 and you'll get the following:

John  instance created.
Pocahontas  instance created.
John's  wife is Pocahontas. 
Pocahontas's husband is John.

The husband and wife instances aren't destroyed, as each one points to the other (see Figure 1).

[Click on image for larger view.]

Figure 1. Spouses mutually keep reference counters above 0.

C++11 introduced a "weak_ptr" to help untie cycles. But unlike managed languages, the developer is responsible for applying it. This can be tedious and error-prone. "Weak_ptr" is called "weak" because it points to a shared instance without incrementing the instance reference counter. Conversely, a "shared_ptr" is "strong" because it increments such counter.

In Listing 2, one of the partners strongly references the other, but the latter must weakly correspond to the former. When both get out of scope, the wife's reference counter will be 1 while the husband's is 0. Listing 3 shows a possible implementation. I created a nested type (spouse_ptr) whose function set deals with the decision of applying a strong or a weak reference. A person's spouse field type is then spouse_ptr (see Figure 2).

[Click on image for larger view.]

Figure 2. A smarter pointer that chooses either strong or weak links.

Run Listing 3 and see what happens. This time both instances are destroyed. However, compared with its managed counterpart, I had to develop a pointer that correctly handles circular references. Furthermore, this approach isn't reusable for other circular-type contexts.

Complexity of Circular Reference Detection
The spouse example is a predictable (deterministic) and relatively easy scenario in which to introduce circular references. In the real world, they may happen in complex environments with heterogeneous participants and unpredictable (non-deterministic) occurrences. To illustrate, I'll create a general, extensible C++ solution for circular references between homogeneous types, then apply this solution to a scenario of a person and his or her best friend.

A person's best friend property is a pointer to another person. Since circular chains of friends may spontaneously happen, as in Figure 3, it's unknown beforehand when and how many persons will be involved.

[Click on image for larger view.]

Figure 3. A group of people, each with his or her best friend.

Every time a person sets their best friend, I have to detect whether a circular reference is established, in order to close it with a weak_ptr. Should an existing circular reference get broken as a consequence of a friendship change, I'll have to flip its weak link into a strong one (see Figure 4).

[Click on image for larger view.]

Figure 4. As Cindy's best friend is now Charles, Laurie's weak link to John becomes strong.

Listing 4 contains a template type, circular_ptr, which is a general case of spouse_ptr (see Listing 3), even for unpredictable scenarios.

Circular_ptr implements a function (is_this_reachable_from) to detect circular references just before they occur. It also implements a function (find_weak_link_reaching_this) to find the weak link in a cycle being broken. Both implementations are virtual (that is, overridable) because their order of complexity is O(n), linear to the number of elements in the cycle. Linear order is not necessarily bad, and it's certainly below a quadratic order. In deterministic circular scenarios, the order is constant (in the spouse example, it's 1).

[Click on image for larger view.]

Figure 5. People and their best friends, a non-deterministic circular reference example.

I extended circular_ptr as best_friend_ptr, a person's nested class. The function main() in Listing 5 deals with six people, making and breaking friendship cycles between them. In the beginning (Figure 3) they all compose a circular chain of friends.

Then the chain is broken, as seen in Figure 4, though a smaller circle prevails. In Figure 5, the ring expands again to contain all people. Finally, in Figure 6, the ring is broken again and no cycle stays alive. Run Listing 5 and confirm that at the end all instances are properly released. Listing 5 shows the best friend scenario.

[Click on image for larger view.]

Figure 6. Lonely Charles breaks the circle, so Emma's link becomes strong.

Avoiding Circular References
Einstein said that the significant problems we face cannot be solved at the same level of thinking we were at when we created them. If non-deterministic circular references have linear complexity, I'll redesign my solution so circular friend chains aren't circular references. Instead of keeping a person's best friend as a person property, I'll move it to a type supported by a map. See the friendship class in Listing 6 for details.

Which approach is more elegant is debatable, but Listing 6 is simpler than Listing 5 because no circle-detection logic is needed. Besides, its complexity is logarithmic O(log(n)).

The Strength of Weakness
C++11 smart pointers are a leap in the right direction for dynamic memory management. Shared_ptrs implement reference counting. Weak_ptrs complement them before circular references. Nonetheless, circular references are like recursion: just because the language enables them, it doesn't mean they must be used.