Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
If you don t know how many objects you re going to need to
solve a particular problem, or how long they will last, you also don t know
ahead of time how to store those objects. How can you know how much space to
create? The answer is you don t until run time.
The solution to most problems in object-oriented design
seems simple; you create another type of object. For the storage problem, the
new type of object holds other objects or pointers to objects. This new type of
object, which is typically referred to in C++ as a container (also
called a collection in some languages), expands itself whenever
necessary to accommodate everything you place inside it. You don t need to know
ahead of time how many objects you re going to place in a container; you just
create a container object and let it take care of the details.
Fortunately, a good object-oriented programming language comes
with a set of containers. In C++, it s the Standard Template Library (STL). In
some libraries, a generic container is considered good enough for all needs,
and in others (C++ in particular) the library has different types of containers
for different needs: a vector for efficient access to all elements, and
a linked list for efficient insertion at all positions, and several
more, so you can choose the particular type that fits your needs.
All containers have some way to put things in and get things
out. The way you place something into a container is fairly obvious; there s a
function called push or add or a similar name. The way you retrieve things
from a container is not always as apparent; if an entity is array-like, such as
a vector, you might be able to use an indexing operator or function. But
in many situations this doesn t make sense. Also, a single-selection function
is restrictive. What if you want to manipulate or compare a group of elements
in the container?
The solution for flexible element access is the iterator,
an object whose job is to select the elements within a container and present
them to the user of the iterator. As a class, an iterator also provides a level
of abstraction, which you can use to separate the details of the container from
the code that s accessing that container. The container, via the iterator, is
seen as a sequence. The iterator lets you traverse the sequence without
worrying about the underlying structure that is, whether it s a vector,
a linked list, a set, or something else. This gives you the
flexibility to easily change the underlying data structure without disturbing
the code in your program that traverses the container. Separating iteration
from the container s control also allows multiple simultaneous iterators.
From a design standpoint, all you really want is a sequence
that can be manipulated to solve your problem. If a single type of sequence
satisfied all your needs, there would be no reason to have different types. You
need a choice of containers for two reasons. First, containers provide
different types of interfaces and external behavior. A stack has an
interface and a behavior that is different from that of a queue, which
is different from that of a set or a list. One of these might
provide a more flexible solution to your problem than the other, or it might
provide a clearer abstraction that conveys your design intent. Second,
different containers have different efficiencies for certain operations.
Compare a vector to a list, for example. Both are simple
sequences that can have nearly identical interfaces and external behaviors. But
certain operations can have radically different costs. Randomly accessing
elements in a vector is a constant-time operation; it takes the same
amount of time regardless of the element you select. However, it is expensive
to move through a linked list to randomly access an element, and it
takes longer to find an element if it is farther down the list. On the
other hand, if you want to insert an element in the middle of a sequence, it s
cheaper with a list than with a vector. The efficiencies of these
and other operations depend on the underlying structure of the sequence. In the
design phase, you might start with a list and, when tuning for
performance, change to a vector, or vice-versa. Because of iterators,
code that merely traverses sequences is insulated from changes in the
underlying sequence implementation.
Remember that a container is only a storage cabinet that
holds objects. If that cabinet solves all your needs, it probably doesn t
really matter how it is implemented. If you re working in a programming
environment that has built-in overhead due to other factors, the cost
difference between a vector and a linked list might not matter.
You might need only one type of sequence. You can even imagine the perfect
container abstraction, which can automatically change its underlying
implementation according to the way it is used.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |