C/C++ Users Journal May 2004
In the article "Strict Ownership in STL Containers: The NoPtr Library" (CUJ, March 2004), I discussed the concept of ownership of dynamically allocated objects in C++. In particular, I stressed how important it is for you to establish a clear ownership policy for each dynamically allocated object (DAO) you create.
In the process, I distinguished two types of ownership — strict and shared — and suggested that strict ownership leads to clearer resource lifetime, which greatly reduces the likelihood of cyclical dependencies. This led to the conclusion that it is better to use strict ownership unless the design really requires sharing resources (see Copy-On-Write [1] and the Flyweight pattern [2]). I then presented the NoPtr library [3] classes that support strict ownership, before wrapping up with an example of how the main class — called DynObj<T> for a DAO of type T — could be used even inside an STL container. Design-wise, this was a major challenge since strict ownership is at odds with STL's requirements for copy constructibility and assignability.
In this article, I discuss how DynObj<T> was designed to allow strict ownership of a DAO within value-based containers like the STL containers.
A bare-bones DynObj<T> would provide strict ownership of a DAO of type T and nothing more (such as support for conversions, polymorphism, and so on, all included in the actual NoPtr library). The header would be something like Listing 1. However, the problem is that in Listing 1, DynObj<T> does not satisfy the copy-constructibility and assignability (CCA) requirements that any element type of an STL container must satisfy [4]. If you consider making this DynObj<T> CCA-compliant, and you want it to have reference semantics (in fact, that's often the whole point of using a container of DAOs), then you are forced to use shallow copying of the _dao data member. But shallow copying implies shared ownership, which violates the class invariant of DynObj<T>.
If DynObj<T> is to be stored in a container, something must be changed. For instance, you might want changes that:
There is a way around this problem if you make two assumptions about DAOs stored in STL containers:
Assumption #1 is concerned with temporaries. Any temporaries created are needed only for the operation, so once the operation is over, a good implementation gets rid of them. Assumption #2 is concerned with the nature of containers — they just contain, they don't affect the state of what they contain. Any reasonably sensible implementation of STL containers could be expected to satisfy both assumptions without problem.
How does this help? The class invariant for DynObj<T> is that, at most, one DynObj<T> has a given DAO of type T at any given time (strict ownership). An invariant just gives a guarantee that is true by the end of construction, before entry to member functions and after returning from them. These two assumptions allow the DynObj<T> class invariant to be upheld before and after insertion into a container, or swapping two DynObj in the container(s), while relaxing it during certain operations.
With these assumptions, it is sufficient to add to DynObj the following capabilities:
How can copy-construction and assignment be allowed only when the DynObj is being inserted or moved around within or between two containers? Clearly, DynObj<T> must know which context it is used in — if it is "free" (that is, not in an STL container). When free, it must disallow CCA. On the other hand, when used in a value-based container, then it must add the aforementioned three capabilities that, with the two starting assumptions, maintain the class invariant.
Unfortunately, the context of use of an object can't be added after the fact, not while remaining portable, anyway. Therefore, it's up to you to tell the compiler when to allow CCA. Furthermore, the context information changes the class, which implies that a second class definition is needed. Yet, I don't want the coder to think in terms of a different class for DynObj inside a container. To keep a handle on maintainability, I use the technique of adding an extra template parameter — the Context — with a default value; see Listing 2. This lets you declare "free" instances of DynObj<T> as simply DynObj<T>, but to declare instances inside containers as DynObj<T, InValueContainer> or DynObj<T>::InValueContainer. With the latter notation, you may find it easier to think of the element type of the container as a DynObj<T> with the context explicitly specified.
The Context is inherited privately (instead of being a data member) to take advantage of the empty base optimization that FreeDefaultContext allows. This means there is no cost to the "feature" if it is not used. The context class InValueContainer will be substantially more complex than FreeDefaultContext because it must keep track of the transient shared ownership, and provide a soleOwner() that returns true only if there is one owner left.
There are many ways for InValueContainer to keep track of ownership. The most straightforward is probably reference counting. A rough implementation of the InValueContainer context might be like Listing 3. Also, it is easy for DynObj to test Assumption #2 by using assert(soleOwner()) in every one of its methods.
This implementation leads to well-defined compile- and runtime behavior. When you use DynObj<T> in the "free" context, attempting to instantiate it by copy construction, or attempting to assign to it, causes a compile error about private members of FreeDefaultContext being inaccessible. For example, declaring std::list<DynObj<T> > and inserting DynObj<T> into it causes such a compile-time error. Furthermore, any interaction between DynObj<T>s requires explicit transfer of ownership (directly or, via DynTmp<T>, indirectly) via a member function call. Together these ensure that the strict ownership invariant for DynObj<T> is maintained in the free context.
On the other hand, when the std::list is declared with element type DynObj<T>::InValueContainer (see Listing 5 in [3]), inserting items into the container, reordering the list, or moving elements from one list to another, works as expected. The Context member of the DynObj elements take care of the shared transients during those operations and, via Context::soleOwner(), let DynObj methods assert Assumption #2 and determine if the DAO owned should be deleted upon destruction.
There are a few caveats to be aware of. First, the class invariant is enforceable only if you use the right context at the right time. Given the simple definition of the context here (either free or in a value-based container), getting this wrong is unlikely. Actually, declaring an STL container with a DynObj<T> element cannot lead to any problem, just possibly some compiler errors depending on what is done to the container. Therefore, the danger is really with instantiating DynObj<T>::InValueContainer, which should never be done since the context is then wrong. This mistake is made less likely by making the context name verbose so it stands out in the code, and so it is extra work to write, using the lazy-programmer principle (the C++ *_cast functions, for example).
Another caveat to watch for is a shallow copy of a container. Indeed, once you tell DynObj that it is going to be used in a value-based container, it is possible to copy it, so the container can be copied. Since this is not a transient operation and involves a shallow copy, the invariant is violated, and as soon as you try to do anything with any of the elements that were copied, the assertion that verifies Assumption #2 causes the bug to be clearly visible.
There is a pseudocaveat — the possibility to assign DynObj<T> to an element of the container. For example:
std::list< DynObj<T>::InValueContainer > list; list.push_back(dynTmp(0)); // null DynObj DynObj<T> otherT(new T); list.first() = otherT;
The last line leads to a compile error because the CCA is allowed only for the same context. However, this does not prevent interactions between free DynObj<T> and DynObj<T> inside a container. See Listing 4, where a free DynObj is giving up ownership of two DAOs to a DynObj inside the container.
One important caveat of this solution is that many checks are only possible at runtime in a debug build via assert(), though in principle they are available at compile time. For instance, in swapping two elements of a container the standard way (tmp=a, a=b, b=tmp), you know at compile time that by the end, the ownership is not shared because tmp is destroyed, but I haven't found a way of encoding this.
Again, there are many possible implementations for the InValueContainer context. Reference counting is foolproof, but slow due to the call to new that must be done for every DynObj<T> in the container. A much faster implementation is to replace the reference count with a pointer to another Context; see Listing 5. This works if there is at most one transient owner created at any given time. Whether this is the case depends on the STL implementation and the compiler, but again if it happens not to be true, you know by a failed assertion on the line commented by "line 1" in Listing 5. It is sufficient surprisingly often, at least with the two STL implementations I have tried.
Other alternative implementations are possible; for instance, a chain topology that has a slightly larger memory footprint than the reference count method, but is faster, again due to the lack of dynamic memory allocation for the reference count. This technique requires only two pointers to be stored in the context class.
The typical scenario would therefore be to use the InValueContainer context when in an STL container, but use one of the optimized ones available in the NoPtr library if you are certain the speed gain is worth it and to test it in a debug mode. The various implementations never need to interact directly so they can be freely mixed within a program.
It is interesting to note that the performance cost of using NoPtr rather than raw pointers is on the order of 10 percent. Since this is larger than the difference in performance between compilers and platforms, it is for all practical purposes negligible. One exception, however, is sorting a container of DynObj<T>, which takes about nine times what it would to sort the same container of raw pointers, the same as for boost::shared_ptr. This factor goes down to seven or eight when you use one of the optimized implementations of the InValueContainer context class. Not surprisingly, strict ownership, in the form of DynObj<T> and DynTmp<T>, is up to twice as fast as ownership as implemented by boost::shared_ptr<T>. For actual numbers, refer to the performance section at the NoPtr web site [5].
If you need strict ownership of dynamically allocated objects, usable even in STL containers, the NoPtr library provides three classes to support this:
NoPtr makes this possible by defining a Context that you specify only when you declare your container of DynObj<T> objects. This parameter is, in fact, a class that prevents copy construction and assignment by default, but allows it inside STL containers, and only under the two assumptions mentioned in the text.
This strict ownership library is on the order of 10 percent slower than if the smart references are replaced by raw pointers, a small price to pay for all the benefits of clear strict ownership semantics, automated lifetime control, and automated verification of existence of a DAO before access.
Compared to shared ownership, strict ownership requires more attention to the owner; i.e., you still have to worry about existence upon access, but the NoPtr classes automate this verification in a debug build. Also, it is equal or up to twice as fast, depending on the operation, as boost::shared_ptr, and greatly diminishes the likelihood of circular dependencies.
That said, the choice between raw pointers, shared ownership smart pointers, and NoPtr should be guided primarily by safety and design: Do you need the safety of automated lifetime management of DAOs? If so, via strict or shared ownership? If you don't care or don't need dynamically created resources to be shared, use strict ownership, unless you need capabilities of other smart pointers that are not currently available in NoPtr.
There are many things that could be improved, including adding multithread safety, supporting customized destruction, providing some smart-pointer equivalents to the smart references that NoPtr provides, and making the runtime checks into compile-time checks. Some of these will be added as the need arises.
Thanks to Sam Saariste and Terje Slettebö. Any mistakes are my own.
[1] See C++PL and C++FAQ, sections 28, 28.7, and 28.8 (http://www.faqs.org/faqs/C++-faq/part1/).
[2] Gamma, Erich, et al. Design Patterns, Elements of Reusable Object-Oriented Software, Addison-Wesley, 1995.
[3] http://noptrlib.sourceforge.net/.
[4] ISO/IEC 14882:1998(E), "Programming Languages — C++."
[5] http://noptrlib.sourceforge.net/page_performance.html.