Next: Comparisons
Up: Discussion
Previous: Organization
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}](img63.gif) |
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}](img64.gif) |
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}](img65.gif) |
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: Comparisons
Up: Discussion
Previous: Organization
RHS Linux User
1/26/1998