C/C++ Users Journal March 2004

Strict Ownership in STL Containers

Dealing with dynamically allocated objects

By Oliver Schoenborn

There are many situations in C++ where dynamically allocated objects (DAO) are difficult — if not impossible — to avoid. These situations include:

• Delayed construction. When you want to instantiate a data member of a class Foo after instantiating a Foo, for instance, you commonly make the data member a pointer type and dynamically create the data member.
• Object acquisition. For example, when an instance of Bar must be acquired by an instance of a class Foo and Bar is characterized by its identity rather than by its state.
• Polymorphism. In most cases this involves instantiation of classes whose type is known only at runtime.
• Object creation not mandatory. For instance, when a function or class instance can decide not to create or can fail to create an object.
• Hide implementation of data member. For example, when your class Foo has a data member of type Bar whose class definition you do not want to include in the header for Foo, so that classes that use Foo are not affected by changes in the definition of Bar.
• Storage of objects in STL value-based containers (currently all the STL containers). For example, when you need to store a reference type rather than a value type in an STL container, you typically use a container of pointers to DAOs.
• Sharing resources. When an object of a given type shares a data member with another object of the same type (when the types are different, dynamic allocation is less common).

The main danger with DAOs is that they must be destroyed manually, such as via a call to delete. This contrasts with automatic, static, global, and temporary objects, which are all destroyed automatically by the compiler (I call those "auto variables") as specified clearly in the Standard [1]. Manual destruction means several faults are possible:

• Forget to destroy the DAO.
• Forget to destroy the DAO before erasing or removing it from an STL container of pointers to DAOs.
• Attempt to destroy more than once.
• Attempt to access DAO already destroyed (aka dangling pointer).

The associated failures can be anything from an undefined behavior of your program, program crash, and data corruption, to apparent wrong program logic and even security holes. Moreover, the compiler provides no help in identifying the presence of such faults. Unlike type safety, you're on your own to find or implement tools and techniques that prevent these faults or let you identify them before it is too late.

Ownership

The concept of ownership is actually at the root of these problems, but is easily overlooked [2]. In fact, it is central to clean programming with DAOs in C++.

In this article, I distinguish three types of activities for any variable that appears in your programs: acquisition, use, and release. In C++ terms, this is construction, access, and destruction. The actors for each I call the creator, user, and owner, respectively. The role and responsibilities of the first two are straightforward and I won't elaborate on them here. The responsibility of the third one is ownership.

For simplicity, I define the owner as the code "block"; that is, a function or object in charge of calling the destructor (if any) of an object and freeing (if necessary) the memory in which it was stored.

With these terms, in C++ any object has only one creator but can have several users (via references and pointers). Also, for auto-variables the creator and owner are the same and don't change, whereas for DAOs the owner is often different from the creator and can change during the program run or for different runs.

Ownership can be shared or strict. A DAO is strictly owned if it has only one owner at any given point during its lifetime. Who this is can change, but there is always at most one owner at any given time. The preferred idiom for strict ownership is to create in one place, destroy in one place, and access all over.

Shared ownership refers to several objects owning a common resource. Shared ownership can be useful in the Flyweight pattern [3] and in idioms such as Copy-On-Write [4]. The preferred idiom for shared ownership is to create in one place, and make any user also an owner so that it is not possible to use a resource that has already been discarded.

Both types of ownership have advantages and disadvantages, but ideally you should use each in the appropriate circumstances. In essence, strict ownership is to shared ownership what private is to public, what nonfriend is to friend: stricter, i.e., "use strict by default, and shared only if you have to."

How is strict ownership stricter? First, the lifeline of a strictly owned resource is single, so you control exactly when the resource is returned to the system. This is a good practice just to save on system resources. But it also leads to deterministic resource management, and simplifies debugging when you need to verify when a resource is being released. Second, strict ownership allows you to decouple ownership of, from access to, a DAO. This lets you support the ownership-as-an-implementation detail idiom, which increases encapsulation.

Shared ownership typically requires extra information, in addition to the resource, to be shared by the owners, so that they can coordinate when the shared resource should be destroyed. Otherwise, they could not know if the resource has already been destroyed or needs destruction. This has a cost in performance that may or may not be negligible in your application. This also is the cause of what's known as "circular references" [5]. There is no way for you to prevent it. But such a problem is much less likely with strict ownership.

One advantage of shared ownership is that you don't need to worry about whether the resource is available before using it, if you can make all users also shared owners. This is true, however, only if there are no circular references, and if eliminating circular references does not require that you violate the "user is also an owner" idiom. Consider Listing 1. How will the body of the B constructor and destructor affect who owns what, and how well defined is the program that would make use of such code? Say, for instance, that B is passed a pointer to the A that created it? Should the destructor delete it? Is there any way to prevent B::a from pointing to the A that owns it? These questions are important to ask to have clear ownership semantics if A and B are DAOs.

Tools and Techniques

The biggest problem in using DAOs is that, unlike with auto-variables, all aspects of ownership are left entirely up to you. Worse, the compiler cannot warn you if you are forgetting it (resource leak), overdoing it (double delete), inadvertently changing it from strict to shared, or climbing stairs that have nothing at the top (dangling pointer or reference). And finally, the ownership policy you use for a particular DAO can only be documented in comments that are easy to forget, get wrong, or be out of sync with the code, or by looking at the code itself, which can be tedious and error prone.

For this reason, there are tools and techniques to help you avoid such faults:

• Static code analyzers that are more rigorous than the typical compiler and can point out potential problems or breach of coding standards.
• Debuggers and memory managers that can give you information on how your program uses memory, if there are any leaks, and so on.
• assert() and other unit testing techniques that let you verify your code and validate your assumptions.
• Smart pointers that add "smarts" to DAO pointers by wrapping them with extra functionality, such as lifetime management, thread support, and the like.

The last option is the most interesting to me since it goes right to the root of the problem — adding reusable functionality at the code level to avoid the faults in the first place by providing some degree of automation of various aspects of ownership. Some widely known smart-pointer classes available:

• std::auto_ptr, which provides strict ownership but implicit move on copy semantics; this makes its use error prone and, most importantly, makes it unusable in STL containers.
• boost::shared_ptr [6] and AUTO_REF [7], which provides shared ownership, which makes them okay in STL containers.
• boost::scope_ptr [8], which provides strict ownership, but cannot be moved around your program or used in STL containers.
• Loki::SmartPtr [8], a policy-based smart pointer that supports separate policies for ownership type, lifetime, multithreading, and so on.

I needed to have strictly owned DAOs in STL containers and ended up creating three classes to support this. These classes are in the NoPtr library (available at http://www.cuj.com/code/), which supports strict ownership of DAOs. NoPtr's name derives from the fact that the classes it provides use object semantics rather than pointer semantics. The classes give access to dynamically allocated objects as objects, rather than as pointers to objects. This approach has pros and cons, but does mean that operator() is overloaded instead of operator->. But this is a separate issue from ownership, so it does not matter in the context of this article. (Of course, I might have been able to create them with Loki, but it wouldn't have been as much fun.)

The NoPtr Library

The essence of the NoPtr library is its support of as many characteristics of strict ownership as possible. What operations are important for strict ownership? You would expect at least the following:

1. Take ownership of a DAO at construction and after construction.

2. Destroy DAO owned.

3. Release a DAO from ownership.

4. Transfer DAO to another owner.

5. Prevent implicit copy and assignment.

6. Access to DAO, with assertion for non-nullness.

Support for these features is provided by the DynObj<T> class, whose role is therefore to be a strict owner (items 1-5) and accessor (item 6) of a "DYNamically allocated OBJect." Item 5 has the minor disadvantage that you must do the copy of the DAO yourself, but it prevents accidental shallow copy of the DAO owned. This is a small price to pay in the amount of typing to avoid a nasty source of bugs. (An alternative would be to use a trait template parameter, but this has several disadvantages that go beyond the scope of this article). Listing 2 presents an example use of DynObj. In addition, DynObj supports:

• Const correctness. A DynObj<const T> gives access only to the const methods and operators of T.
• Polymorphism. A DynObj<Base> can be used to represent a Derived.
• Delayed initialization. A DynObj<T> appearing as a data member of a class need not have a complete definition of T; a forward declaration is sufficient.
• Invisibility of transfer of ownership to pure accessors. A pure accessor of a DAO does not care who owns it; it is not affected by a change of owner of the DAO.

The second class, DynTmp<T>, supports the common idiom of strict ownership transfer via unnamed temporaries. DynObj cannot support this because it must prevent copy construction. Listing 3 illustrates a typical use of this.

This has two important advantages. First, it makes clear the transfer of ownership from a local variable to a temporary; second, it makes clear the effect on a DynObj when one is involved; and finally, the DAO is destroyed if the DynTmp is not "consumed" by a DynObj. Note that DynTmp has no public member functions; that is, it can only be used to transfer ownership.

The third class RRef<T>, short for "reseatable reference," is a weak reference for pure usage of a DAO. It is not a necessary class since you could just pass around a pointer or reference, obtained from the DynObj. However, RRef<T> includes debug information so that RRef<T> can verify that the DAO is non-null before you attempt to access it. Listing 4 is an example use of RRef<T>.

You can use DynObj<T> in STL containers, but you must (unfortunately) explicitly tell DynObj about it. This way, it can customize its behavior to satisfy the "copy constructable" and "assignable" requirements of STL container elements [1]. You do this by specifying an extra "context" parameter called InValueContainer. From your point of view, this parameter does not change the class — namely the STL container is still storing DynObj<T> objects — but the extra parameter is necessary for it to work in value-based containers. There are no issues of conversion between DynObj<T> and DynObj<T>::InValueContainer that you need to worry about. The extra parameter is intentionally long to write, so as to discourage using it outside of containers. Indeed, inside a container you only need to specify the extra parameter at declaration time, so it is a practical solution. Listing 5 illustrates this.

Acknowledgments

Thanks to reviewers Sam Saariste, Phil Bass, Terje Slettebo, and Mark Radford. Any mistakes left are mine.

References

[1] ISO/IEC 14882:1998(E), "Programming Languages — C++."

[2] Interesting discussion of ownership at http://www.itworld.com/AppDev/10/ITW1137/.

[3] Gamma, Erich et al. Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley, 1995.

[4] C++PL, and C++FAQ sections 28, 28.7 and 28.8 (http://www.faqs.org/faqs/C++-faq/part1/).

[5] Meyers, Scott. More Effective C++, Item 29, Addison-Wesley, 1996.

[6] http://www.boost.org/libs/smart_ptr/index.htm.

[7] http://www.codeproject.com/cpp/auto_ref.asp.

[8] Alexandrescu, Andrei. Modern C++ Design, Addison-Wesley, 2001.