next up previous contents
Next: Comparisons Up: Discussion Previous: Organization

Reference Counting

Aside from implementing the core set and sequence operations, the Collection hierarchy offers the programmer a major advantage when compared to the Container hierarchy.
The copying of Collections is implemented efficiently if possible, i.e., if the source object is a descendant of the destination object, using a reference counting scheme. This is of great importance when dealing with frequently passed groups of objects such as the neighbors of a vertex. In contrast, the initialization of one Container with another always accomplished by iteration through all of the elements.
All class derivation in the Collection hierarchy is public. In general, if a child class is derived publically from a parent class, it is convenient to say that a child class instance is a parent class instance. For example, a sequence is a multiset in which the the elements can appear in any specified order. This rule can be used to determine whether or not a given copy operation will involve an increment in reference count or the iteration through all of the elements. Reference counting occurs when the object being copied is an instance of the destination object. Otherwise the receiving object is incompatible with the source object and each element must be copied. For example, consider the code fragment in Figure [*].
  
Figure 3.18: Reference Counting in Collections
\begin{figure}
\begin{flushleft}
\begin{minipage}[t]
{\textwidth}
\hrulefill

\v...
 ...nd{verbatim}
\vspace*{-6mm}

\hrulefill\end{minipage}\end{flushleft}\end{figure}

The variable array_set is a multiset object which uses a SortedArray to store its elements. On the other hand, list_set1 and list_set2 use SortedList objects to store their elements. The reference counting scheme, which uses pointer aliasing to avoid unnecessary copying, will not work with incompatible containers. Under reference counting, it is possible for many Collection objects to have pointers to the same Container object. As long as no changes are made to this underlying implementation, such aliasing is all right. However, once a Collection attempts to insert or remove elements, it must be given its own copy of the elements. For examples, consider the code in Figure [*].
  
Figure 3.19: Reference Counting and Modifications in Collections
\begin{figure}
\begin{flushleft}
\begin{minipage}[t]
{\textwidth}
\hrulefill

\v...
 ...nd{verbatim}
\vspace*{-6mm}

\hrulefill\end{minipage}\end{flushleft}\end{figure}

When mset2 attempts to append an additional element, sharing a common Container with mset1 is no longer an option. A full copy of the elements is made before the insertion. In this manner, the integrity of mset1 is preserved. Since X(const X&) constructors are called automatically upon argument pass by value and function return by value (and since in the Collection hierarchy they control the reference counting along with the assignment operators), Collection objects can be passed around efficiently. This makes the efficient programmer's memory management job much easier. For example, consider the code in Figure [*].
  
Figure 3.20: Passing and Returning Collection Objects
\begin{figure}
\begin{flushleft}
\begin{minipage}[t]
{\textwidth}
\hrulefill

\v...
 ...nd{verbatim}
\vspace*{-6mm}

\hrulefill\end{minipage}\end{flushleft}\end{figure}

The return of a temporary object cannot be accomplished by reference, so without reference counting, an efficient return would require dynamic memory allocation. But this is not necessary; the return of Collection objects is an efficient operation.
next up previous contents
Next: Comparisons Up: Discussion Previous: Organization
RHS Linux User
1/26/1998