Contents Up << >>
How can I insert/access/change elements from a linked list/hashtable/etc?
I'll use an "inserting into a linked list" as a prototypical example.
It's easy to allow insertion at the head and tail of the list, but limiting
ourselves to these would produce a library that is too weak (a weak library is almost
worse than no library).
This answer will be a lot to swallow for novice C++'ers, so I'll give a
couple of options. The first option is easiest; the second and third are
better.
- Empower the "List" with a "current location," and methods such as
advance(), backup(), atEnd(), atBegin(), getCurrElem(),
setCurrElem(Elem),
insertElem(Elem), and removeElem(). Although this works in small
examples, the
notion of "a" current position makes it difficult to access elements at
two or
more positions within the List (e.g., "for all pairs x,y do the
following...").
- Remove the above methods from the List itself, and move them to a
separate class, "ListPosition." ListPosition would act as a "current position"
within a List. This allows multiple positions within the same List.
ListPosition would be a friend of List, so List can hide its innards from the outside world
(else the innards of List would have to be publicized via public methods in
List). Note: ListPosition can use operator overloading for things like
advance() and backup(), since operator overloading is syntactic sugar for normal
methods.
- Consider the entire iteration as an atomic event, and create a class
template to embodies this event. This enhances performance by allowing
the public access methods (which may be virtual fns) to be avoided during
the inner loop. Unfortunately you get extra object code in the application, since
templates gain speed by duplicating code. For more, see [Koenig,
"Templates as interfaces", JOOP, 4, 5 (Sept 91)], and [Stroustrup, "The C++
Programming Language Second Edition," under "Comparator"].