Introduction
------------
STL containers are mighty and flexible tools for the management of object collections.
In their current form, anyways, at least some incarnations of them can only
be efficiently used for rather small objects or objects which can be copied
with little cost (i.e. objects, which implement so called "copy on write").
Why, you may ask!
The reason is that there are a lot of algorithms and operations on the container that must move objects around in the container and for certain containers (most notably "vector") that means actually copying objects around. A few examples of these algorithms would be: unique, make_heap, reverse, sort, remove_if. (See [STL References])
Another operation that may provoke copying is increasing the container by adding elements at its tail (with push_back): if this operation triggers a reallocation of the storage holding the elements, in some cases (again especially with "vector") all container elements have to be copied.
In such a case, you'll be probably better of using "indirect containers". What I call "indirect containers" are containers of pointers to the elements rather than containers that hold their elements directly. The elements themselfs will be allocated from the free store, piece by piece, and only the pointers to the elements have to be managed by the container. With many commercial container libraries this technique is commonplace; anyhow there is no direct support for it using STL containers.
This is due to the fact that STL containers have no notion of object ownership, when pointers to objects are used instead of objects: when the container goes out of scope, only the pointers are "destroyed", not the elements pointed to.
In the following I'll call a container that knows about object ownership an
"owning container".
Typically you would make an owning container out of a normal container by providing
a container destructor, that gets rid of the elements pointed to, before returning.
Period.
However - there are more complicated object ownership issues:
During the lifetime of a container there are many situations where objects must
be deleted accordingly as well. Think about such algorithms as "remove_if":
this algorithm removes all objects from a container, that do fulfill a certain
predicate (a condition). In our case of an indirect container, again, that would
mean removing only the pointers, and possibly leaving some of the objects pointed
to, waised in the free store.
Having so said, it seems necessary to create an abstraction layer on top of the STL container to let the container deal with object ownership. In the following I'll try to outline 6 different aproaches, each having it's merits and traps.
Solution 1
----------
You work with 2 containers: one of them is a direct container, actually managing
the memory for the contained objects, the other is just a kind of a "directory"
and holds pointers to the objects. Whenever you need to sort or otherwise change
the sequence of objects or remove entries, use the "directory". When
you are done with your elements you only have to remove the direct container,
thereby removing all elements as well.
Pros: easy to understand, cheap to implement.
Cons: the program gets unnecessarily complicated by the need to manage two containers
and hold them in sync; this is furthermore a potential source of errors.
Solution 2
----------
This is based on the same idea as solution 1, but takes the mechanism a bit
further, by automating the memory managment: The contained objects manage by
themselves an owning container behind the scenes. Whenever such an object is
allocated from the free store, it inserts a reference (i.e. a pointer) to itself
into this container. Again you use other containers just as indirect containers
- during normal program operation you don't care about the memory the objects
hold.
On well defined points of the program flow, you force the "behind the scenes"
container to be emptied and to release all owned objects. (this can be easily
done by providing a member function, that loops through all elements deleting
them; the same member should be called in the destructor of the container)
Pros: no more need to synchronize 2 containers.
Cons: you have to identify the points, where all objects of the given class
can safely be removed. Actually you can consider this as a very primitive "all
or nothing" garbage collector. In a few systems these points may be easily
identified, like in document/view based applications: when a document is closed,
we can often remove all objects of a given type. The same holds true for certain
batch oriented programs, that create massive amounts of objects during the processing
stage, but can throw everything away when they go back to a suspended mode (that
is, when the processing is done). Compilers and parsers come to mind, when thinking
about applications for this idea.
Anyways the semantics of such an operation are quite confusing and far from
beeing a general solution: often you'll find yourself deleting objects, you
did not want to delete at that point.
Furtheron, memory is allocated longer than necessary. Imagine a CAD System with
thousands of polygons, where removal of polygons through user interaction would
not help to get back the memory for other tasks until the document currently
being worked on is closed, thereby triggering the described garbage collection.
That's not the way we wish the system to behave (notwithstanding the fact, that
there are lots of systems that SEEM to behave that way).
I do use a similar solution from time to time in another context: as a debugging
aid for controlling memory leaks. I give an implementation of such a system
in GOBJECT.H
To use the mechanism, you'll have to derive your controlled objects from GObject;
the static member GObject::ShowAll will then show you at any given time which
objects are still in existence. (via calling Show on the objects - this member
should be overloaded and could possibly print the objects ids to the console.)
Solution 3
----------
By far the cheapest solution to the problem, though not the best:
Overload the global "destroy" function. This function is part of the
STL and was meant to aid in the problems we are dealing with. It's prototype
is like:
void destroy( T *pObject ) ;
where T denotes the class of the contained objects. Actually it is a template function, with T being its template parameter. For the sake of simplicity I'll omit template specifications here. In our case, T would correspond to a pointer type, since we are dealing with indirect containers. So, if TO denotes the class of our objects, we'll have to deal with a function of type:
void destroy( TO **ppObject ) ;
Having clarified this, I'll replace T for TO in the following again.
If you overload this function, to delete the objects pointed to whenever it is called, there are no more memory leaks. Like so:
void destroy( T **ppObject )
{
delete *pObject ;
}
Pros: cheap to implement; no code changes in the clients code
Cons: it is now not possible any more to have containers in your program, that
do NOT own their elements, since we overloaded a global function. This is a
massive drawback, since it is often necessary to have both types of containers.
(again think of a CAD system, where the document has to own the polygons; but
groups or layers of polygons would not own their polygons.)
Also, think about the semantics we got now: we changed the semantics of the
contained object, instead of the semantics of the container which was our original
goal!
Solution 4
----------
Write a container adaptor. Container adaptors are wrappers around containers,
modifying their semantics in the intended way. An example of a container adaptor
is the STL stack class. It's typically based on either a deque, a vector or
a list.
Without going into too much detail about the implementation here, I give an
implementation example in VECADAP.H.
Pros: easy to understand, no further complications for the client
Cons: the container gets unnecessary constrained.
Especially the possibility to use algorithms by specifying begin and end iterators
is lost. As you propably know, algorithms in STL are not member functions of
the containers they work on, but global functions, which typically take 2 iterators:
a begin and an end iterator, thereby denoting a range. Iterators are similar
to pointers, in that they designate certain elements of a container; the algorithm
then works on a subset of the container, specified by the begin and the end
iterator.
From this you can determine, that the algorithm generally has no knowledge about
how the container manages its memory; some algorithms like "remove_if"
even require that certain container member functions be called immediately after
they have been applied to ensure the container releases memory as necessary
(i.e "erase"). A simple example for a direct container, releasing
memory properly:
vector<MyTest> v ;
...
vector<MyTest>::iterator &iter = remove_if( v.begin(), v.end(), toBeRemoved()
) ;
v.erase( iter, v.end() ) ; // erases all MyObjects for which toBeRemoved.operator()
was true
For an explanation of predicates like "toBeRemoved()", see [STL References]
Now if we have an indirect container, we would have to write:
vector<MyTest *> v ;
vector<MyTest *>::iterator &iter = remove_if( v.begin(), v.end(),
toBeRemoved() ) ;
v.erase( iter, v.end() ) ; // erases pointers to MyObjects for which toBeRemoved.operator()
was true
In this example, the memory holding the pointers will be correctly released - not so with the memory for the objects being pointed at.
Note as well, that it is neither enough nor correct to loop over the pointers
from iter to v.end() in the above example and delete the objects pointed to
by the pointers in this range: these pointers are simply garbage; leftovers
from the remove_if process, and NOT pointers to the elements to be removed -
this range may even contain 2 or more pointers pointing to the same element
after remove_if completes.
When remove_if returns, it is actually too late to do the necessary memory frees.
This should clarify that the container adaptor cannot allow access to the adapted container in such a way. We can loosen this restriction a little bit, by at least allowing access to constant iterators, therefore at least allowing nonmodifying algorithms like "for_each" for constant elements (i.e. constant containers) to be applied. The CTEST.CPP sample makes use if this technique for showing the contents of a container via "for_each".
Modifying algorithms can be supported as member functions: identify the algorithms
you need and add a member that internally uses the STL algorithms as building
blocks, but ensures, that memory gets freed as necessary. For a certain class
of algorithms, e.g. sort, this is trivial:
These alogrithms are modifying, but non destructive algorithms - that is: they
change the sequence of elements but do not remove any elements.
For algorithms destroying elements further measure needs to be taken to ensure
proper memory handling - see the example for "remove_if" in listing
VECADAP.H for reference; in this case, I use the predicate to destroy the object
properly: after having determined that an object fulfills the condition and
must be removed, I free the memory held by the object, before returning to the
algorithm, which in turn takes care of the pointer to the object.
As a container implementor it is often difficult (if not impossible) to decide which algorithms will be needed by the container client. It would therefore be best, to declare access to the non constant begin and end iterators protected and not private; by that means, it is possible to derive from the container and add further member algorithms, if necessary.
Solution 5
----------
Derive from the container in question, overload all necessary members (like
the destructor), and hide all dangerous members (like the above mentioned access
functions for non constant begin and end iterators, or the non constant index
operator).
This solution resembles solution 4 quite closely; its advantage is that certain
members can simply be inherited without further work; herein also lies its biggest
disadvantage: it's often difficult to determine which members are "dangerous"
in our sense (managing memory properly in the face of algorithms and other container
manipulations). One example is the element acccess operator "operator[]":
the non constant version should definitely be overloaded, since assigning to
an element at a certain index via operator[] would otherwise overwrite the pointer,
without deleting the object beeing pointed at.
Again, i.m.h.o. it would be best to change the access specification of these
members to "protected", and to provide another member like "insertAt",
that does both random access AND replacement in one step, and can therefore
manage object memory properly.
A sample implementation of that can be found in RVECT.H: this one is based on the STL "vector" container; versions for other STL containers like list or deque can be written in a similar fashion.
One problem that can still be seen in RVECT.H is that we have to give up some quite elementary member functions like erase in their natural form: since erase takes two non constant iterators as parameters (a begin and an end iterator) and we do not allow the client to get these iterators (for reasons explained above), we should hide this function (as well as all other functions using non constant iterators) and provide alternative versions, e.g. an erase function taking an index range (begin and end index). Since hiding all dangerous functions may be difficult and errorprone, solution 4 might be considered a better alternative.
A little sidenote:
Both solutions 4 and 5 suffer from another problem thats not so easy to realize:
Some algorithms take so called predicates (e.g. sort: the predicate determines
the sort order).
These are implemented in terms of a templatized argument. If we try to make
these functions members of the container (as seems to be necessary to do proper
memory managment), we are faced with the challenge of declaring a member template:
as of this writing, there are not many C++ compilers available that support
member templates. So for the near future it may be necessary to provide predicates
as function pointers (comparable to the situation with the C standard library
function "qsort"), which may suffer a certain performance penalty.
See the [STL References] on that for a deeper discussion.
It might as well be possible to make these adapted algorithms friends of the
derived container (instead of members). This would prevent the member function
template problem.
Solution 6
----------
Use smart pointers. Create a special, user defined class (the smart pointer)
whose copy cost is comparable to that of a pointer, let this class manage the
objects beeing pointed at, and use objects of that class instead of pointers
as the container elements.
Smart, in this context, means:
the pointer knows, when and how to delete the objects it points to. A simple
example of a smart pointer is part of the C++ runtime library: auto_ptr. Anyways,
auto_ptr is not up to our task, since it has destructive copy semantics: when
assigning one auto_ptr to another, the original auto_ptr gives ownership of
the object to the new auto_ptr; if the new auto_ptr goes out of scope, the object
is deleted, even if the original auto_ptr still points to the object: since
this situation is quite common in algorithms, this is a recipe for desaster.
Do NEVER use an auto_ptr as element in an STL container, especially, if you're
going to apply algorithms.
So we need something more smart: a reference counted implementation. It's a
pity, that in the C++ runtime library, there is no such creature, so we'll have
to roll our own for now.
Let's call it var_ptr.
A sample implementation of such a var_ptr is contained in VAR_PTR.H
As you can see when studying the listing, the var_ptr alone is not enough, since
the reference count must be maintained by the object being pointed at, NOT the
pointer. So, all you need to do, is: derive your objects from "Object"
(comparable to objects in Java), and use var_ptr's to your objects, instead
of plain pointers. Whenever you need to create a new object, allocate it from
the free store like this:
var_ptr<MyObject> o1 = new MyObject(...) ;
Again, for those of you a little bit familiar with Java, note the close similarity
to Java variables.
Do NEVER delete such a variable explicetly (again comparable to the situation
in Java): if you want to get rid of a reference to an object explicitly, simply
assign NULL to the variable - the object will be deleted if necessary.
Since all these restrictions are automatically fulfilled by the STL algorithms,
we have an ideal candidate for our smart pointer. A client of our smart pointer
could then write code like:
vector<var_ptr<MyObject> > v ;
v.push_back( new MyObject( ... ) ) ;
...
v.push_back( new MyObject( ... ) ) ;
sort( v.begin(), v.end(), MyObjectLessThan() ) ;
vector<var_ptr<MyObject> >::iterator iter = remove_if( v.begin(),
v.end(), MyObjectIsSelected() ) ;
v.erase( iter, v.end() ) ;
Storage managment would happen automatically here.
All that convenience comes at a cost, however:
var_ptr assignment is more expensive in terms of execution time than is assignment
of plain pointers, since a reference count has to be maintained and checked.
Note however, that there is no space penalty: a var_ptr typically has the same
size as a plain pointer (as long as you don't define any virtual members for
it)
Still, for many applications of indirect containers, this cost is not a big
problem: compared to the cost that a direct container would have imposed, this
cost is rather small; furtheron it should be considered that in the next years
many commercial software systems will start using Java. Compared to the performance
of Java, a C++ program making consistent use of var_ptr's will still be much
quicker, and at the same time provide a similar ease of development and code
maintenance; in fact, var_ptr or a similar solution might help C++ compete with
Java in the next years.
I must stress again, that using var_ptr's requires some coding discipline:
1. var_ptr's may only point to objects allocated from the free store.
They may specifically not point to objects with automatic storage specification
(stack based objects), static objects (part of the datasegment of the program)
or to any part of an object. Compare this to the restrictions for auto_ptr,
which wouldn't work with such constructs as well.
2. Objects pointed to by var_ptr shall never be deleted directly. Since var_ptr takes care of object deletion, this would compromise the mechanism. Again, compare this to auto_ptr, which doesn't allow that either.
3. Do never delete an object manually through the var_ptr; this could be accomplished with the following statement:
var_ptr ptr<MyTest> = new MyTest(200) ;
delete ptr.GetObjec() ; // this is wrong; ptr will manage the storage automatically
However you will not inadvertedly write such code; the more common
delete ptr;
will not compile, therefor aiding you in the proper handling of var_ptr's.
Again the situation is similar with auto_ptr.
4. var_ptr's can only point to objects derived from "Object".
5. In its current incarnation var_ptr cannot be used for arrays of objects.
Both restrictions have no counterpart in auto_ptr; point 4 is again comparable to Java, and only point 5 is a restriction unique to our var_ptr implementation. You will however not stumble inadvertedly into these restrictions, since offending constructs won't compile.
6. There is no special relationship between a var_ptr<Derived> and a
var_ptr<Base>, even if class 'Derived' is derived from class 'Base'; you
can especially not assign a var_ptr<Derived> to a var_ptr<Base>
if you do not provide further mechanisms.
There are ways to work around this that have their own merits and drawbacks;
a discussion of this topic can be found in [C++ Language], Chapter 13.6.3.1
In my var_ptr example, I used a simple solution: I do allow a variable of type
var_ptr<T> to decay into a pointer of type T *, which in turn can be used
as argument to the copy constructor of var_ptr<T>. Therefor the compiler
can first convert to T *, then apply i's usual conversion between different
pointer types, and than back to var_ptr (which it happily does.)
All in all it can be said, that there are not much more restrictions on using var_ptr than on using auto_ptr; furthermore var_ptr behaves very similar to Java variables (variables holding objects of structured type to be exact) and it is to be expected that the semantics if Java variables will be widely known in the near future - therefore it should be easy to use var_ptr properly for the average C++ programmer.
So I'd say, if performance is important but not at a premium, you may well
consider using solution 6: var_ptrs as elements in STL containers, your objects
being derived from a common base class like "Object".
If performance is rather critical, you'll propably have to use either Solution
4 or 5, but loose a lot of flexibility in applying algorithms to your containers.
Let me make 2 more final notes about this topic:
Some objects behave similar to var_ptr's on their own. They implement intelligent copy semantics: shallow copying, wherever possible, and deep copying, if necessary. This is normally called COW (Copy On Write), and a typical class that implements this technique is the C++ runtime library class "string". If you use strings or similar COW objects in STL containers, you don't have to bother about copy cost, and need not use any of the above techniques - especially a var_ptr is not necessary. In fact, you can view "string" as a class which has a mechanism similar to var_ptr already built in.
Anyhow, as of this writing, it seems that COW mechanisms are difficult to get right, especially in the presence of multithreading, and in fact, many commercial "string" implemetations behave either erroneous in multithreaded programs, or simply perform poorly (partly because of the need to serialize access to static data members). Some reference implementations of the C++ runtime library (like that of SGI) have therefore abandoned COW for strings altogether; again this would be a possibility to use var_ptr's, if you have to manage big strings, and mind the cost of copying them around in memory.
A mechanism like var_ptr does not only have it's merits when used in conjunction
with STL containers - this is a field where I consider it rather necessary,
but there are other applications as well:
Writing exception safe code.
Since this is an article on its own, just a few words:
Knowing when and how to delete an object, allocated from the free store, properly
is a challenging task in the face of exceptions; most programmers concerned
with this task come to the conclusion that the so called "resource acquisition
is allocation" technique is the best solution for that.
Typically that means using small, stack based objects (that is: objects of automatic
storage type), that hold a pointer to the object they manage and delete this
object upon their own destruction. This ensures leak free code, since during
exception handling the stack is unwound, thereby properly removing the managed
objects as well.
A typical well known construct of this type is auto_ptr. var_ptr provides you
with the same semantics. If you can afford to use var_ptr consistently throughout
a whole project, you get the basic level of exception safety for free: the so
called "weak promise", which basically means, that your program will
neither leak nor crash in the course of exception handling.
Furtheron, as you can see from the listing VAR_PTR.H the var_ptr class also has a built in safety mechanism to guard against referencing uninitialized pointer variables: first, every instance of a var_ptr is implicetly initialized to the equivalent of a NULL pointer (that is the GetObject() member will return NULL). Second, accessing such a NULL var_ptr will result in a C++ exception, namely NullPointerException, be thrown, instead of an operating system exception that would normally lead to program termination. The program can therefore either recover from such a situation or gracefully shut down. Once again I want to emphasize the similarity to Java, where the same mechanism is established.
See [Effective C++] "More Effective C++" or "Effective C++ CD",
Items 9-15 by Scott Meyers,
as well as 3 articles in [C++ Report] for details on exception handling and
the weak and strong promises.
Code
----
Additionally to the code listings already mentioned I provide a little program
(VARTEST.CPP) to test the var_ptr mechanism. The program prints messages to
the console explaining what is supposed to happen next, so you can verify the
mechanism works as promised. I invite you to modify the program with more difficult
and interesting cases and stress the var_ptr implementation in ways I was not
able to imagine.
Another test program CTEST.CPP tests the funcionality of RVECT.H and VECADAP.H.
For the sake of brevity and clarity I did not insert any additional code into
the headers for automatic inclusion of needed headers or prevention of multiple
inclusion; error handling is reduced to the bare minimum.
The code was compiled both using Watcom C++ together with SGI's excellent and
free STL implementation and Visual C++ with its native STL. When using a compiler
that implements the standard namespace std, define _STD_NAMESPACE_IMPL bevor
translating.
Conclusion
----------
We examined 6 more or less successfull ways of dealing with "indirect STL
containers"; 3 of them, namely 4,5 and 6 should be seriously considered
in production programming. Solution 6, making use of smart pointers, might be
the solution of the future and offers other merits, like easy coding and maintenance
and exception safety as well, and may help C++ compete with it's closely related
cousin Java.
Further Reading and References
------------------------------
[STL References]
[C++ Language]
Bjarne Stroustroup: The C++ Programming Language, Third Edition
Addison Weseley
The SGI STL provides additional documentation. You can get it at: http://www.sgi.com
[Effective C++]
Scott Meyers: Effective C++, More Effective C++ or Effective C++ CD
Addison Weseley
[C++ Report]
1994 Nov/Dec Issue - Tom Cargill: Exception Handling: A False Sense of Security
1996 March Issue - Jack W. Reeves: Coping with Exceptions
1997 Nov/Dec Issue - Herb Sutter: Exception-Safe Generice Containers
These articles are all contained on the Effective C++ CD by Scott Meyers as well.
Author
------
Harald Nowak
InfraSoft
email: Harald.Nowak@web.de
http://xwww.infrasoft.co.at/hn/
File References: