First think about what the object logically represents, not how you intend to physically build it. For example, suppose you have a
Stack class that will be built by containing a
LinkedList:
class Stack {
public:
...
private:
LinkedList list_;
};
Should the Stack have a
get() method that returns the
LinkedList? Or a
set() method that takes a
LinkedList? Or a constructor that takes a
LinkedList? Obviously the answer is
No, since you should design your interfaces from the outside-in. I.e., users of
Stack objects don't care about
LinkedLists; they care about pushing and popping.
Now for another example that is a bit more subtle. Suppose class
LinkedList is built using a linked list of
Node objects, where each
Node object has a pointer to the next
Node:
class Node { /*...*/ };
class LinkedList {
public:
...
private:
Node* first_;
};
Should the
LinkedList class have a
get() method that will let users access the first
Node? Should the
Node object have a
get() method that will let users follow that
Node to the next
Node in the chain? In other words, what should a
LinkedList look like from the outside? Is a
LinkedList really a chain of
Node objects? Or is that just an implementation detail? And if it is just an implementation detail, how will the
LinkedList let users access each of the elements in the
LinkedList one at a time?
The key insight is the realization that a
LinkedList is
not a chain of
Nodes. That may be
how it is built, but that is not
what it is. What it is is a sequence of elements. Therefore the
LinkedList abstraction should provide a
LinkedListIterator class as well, and that
LinkedListIterator might have an
operator++ to go to the next element, and it might have a
get()/
set() pair to access its
value stored in the
Node (the value in the
Node element is solely the responsibility of the
LinkedList user, which is why there is a
get()/
set() pair that allows the user to freely manipulate that value).
Starting from the user's perspective, we might want our
LinkedList class to support operations that look similar to accessing an array using pointer arithmetic:
void userCode(LinkedList& a)
{
for (LinkedListIterator p = a.begin(); p != a.end(); ++p)
std::cout << *p << '\n';
}
To implement this interface,
LinkedList will need a
begin() method and an
end() method. These return a
LinkedListIterator object. The
LinkedListIterator will need a method to go forward,
++p; a method to access the current element,
*p; and a comparison operator,
p != a.end().
The code follows. The important thing to notice is that
LinkedList does
not have any methods that let users access
Nodes.
Nodes are an implementation technique that is
completely buried. This makes the
LinkedList class safer (no chance a user will mess up the invariants and linkages between the various nodes), easier to use (users don't need to expend extra effort keeping the node-count equal to the actual number of nodes, or any other infrastructure stuff), and more flexible (by changing a single
typedef, users could change their code from using
LinkedList to some other list-like class and the bulk of their code would compile cleanly and hopefully with improved performance characteristics).
#include <cassert> // Poor man's exception handling
class LinkedListIterator;
class LinkedList;
class Node {
// No public members; this is a "private class"
friend class LinkedListIterator; // A friend class
friend class LinkedList;
Node* next_;
int elem_;
};
class LinkedListIterator {
public:
bool operator== (LinkedListIterator i) const;
bool operator!= (LinkedListIterator i) const;
void operator++ (); // Go to the next element
int& operator* (); // Access the current element
private:
LinkedListIterator(Node* p);
Node* p_;
friend class LinkedList; // so LinkedList can construct a LinkedListIterator
};
class LinkedList {
public:
void append(int elem); // Adds elem after the end
void prepend(int elem); // Adds elem before the beginning
...
LinkedListIterator begin();
LinkedListIterator end();
...
private:
Node* first_;
}; Here are the methods that are obviously inlinable (probably in the same header file):
inline bool LinkedListIterator::operator== (LinkedListIterator i) const
{
return p_ == i.p_;
}
inline bool LinkedListIterator::operator!= (LinkedListIterator i) const
{
return p_ != i.p_;
}
inline void LinkedListIterator::operator++()
{
assert(p_ != NULL); // or if (p_==NULL) throw ...
p_ = p_->next_;
}
inline int& LinkedListIterator::operator*()
{
assert(p_ != NULL); // or if (p_==NULL) throw ...
return p_->elem_;
}
inline LinkedListIterator::LinkedListIterator(Node* p)
: p_(p)
{ }
inline LinkedListIterator LinkedList::begin()
{
return first_;
}
inline LinkedListIterator LinkedList::end()
{
return NULL;
}
Conclusion: The linked list had two different kinds of data. The values of the elements stored in the linked list are the responsibility of the user of the linked list (and
only the user; the linked list itself makes no attempt to prohibit users from changing the third element to 5), and the linked list's infrastructure data (
next pointers, etc.), whose values are the responsibility of the linked list (and
only the linked list; e.g., the linked list does not let users change (or even look at!) the various
next pointers).
Thus the only
get()/
set() methods were to get and set the
elements of the linked list, but not the infrastructure of the linked list. Since the linked list hides the infrastructure pointers/etc., it is able to make very strong promises regarding that infrastructure (e.g., if it were a doubly linked list, it might guarantee that every forward pointer was matched by a backwards pointer from the next
Node).
So, we see here an example of where the values of
some of a class's data is the responsibility of
users (in which case the class needs to have
get()/
set() methods for that data) but the data that the class wants to control does not necessarily have
get()/
set() methods.
Note: the purpose of this example is
not to show you how to write a linked-list class. In fact you should
not "roll your own" linked-list class since you should use one of the "container classes" provided with your compiler. Ideally you'll use one of the
standard container classes such as the
std::list<T> template.
