PREVIOUS NEXT
CLASSES
Q: What is a class?
A: A class is an expanded concept of a data structure: instead of holding only data, it can hold
both data and functions.
Q: What are the differences between a C++ struct and C++ class? A: The default member and base class access specifies are different. This is one of the
commonly misunderstood aspects of C++. Believe it or not, many programmers think that a C++
struct is just like a C struct, while a C++ class has inheritance, access specifes, member
functions, overloaded operators, and so on. Actually, the C++ struct has all the features of the
class. The only differences are that a struct defaults to public member access and public base
class inheritance, and a class defaults to the private access specified and private base-class
inheritance.
Q: How do you know that your class needs a virtual destructor?
A: If your class has at least one virtual function, you should make a destructor for this class
virtual. This will allow you to delete a dynamic object through a caller to a base class object. If
the destructor is non-virtual, then wrong destructor will be invoked during deletion of the
dynamic object.
Q: What is encapsulation?
A: Containing and hiding Information about an object, such as internal data structures and code.
Encapsulation isolates the internal complexity of an object's operation from the rest of the
application. For example, a client component asking for net revenue from a business object need
not know the data's origin.
Q: What is "this" pointer?
A: The this pointer is a pointer accessible only within the member functions of a class, struct, or
union type. It points to the object for which the member function is called. Static member
functions do not have a this pointer. When a nonstatic member function is called for an
object, the address of the object is passed as a hidden argument to the function. For example, the
following function call
myDate.setMonth( 3 );
can be interpreted this way:
setMonth( &myDate, 3 );
The object's address is available from within the member function as the this pointer. It is legal,
though unnecessary, to use the this pointer when referring to members of the class.
Q: What happens when you make call "delete this;"?
A: The code has two built-in pitfalls. First, if it executes in a member function for an extern,
static, or automatic object, the program will probably crash as soon as the delete statement
executes. There is no portable way for an object to tell that it was instantiated on the heap, so the
class cannot assert that its object is properly instantiated. Second, when an object commits
suicide this way, the using program might not know about its demise. As far as the instantiating
program is concerned, the object remains in scope and continues to exist even though the object
did itself in. Subsequent dereferencing of the pointer can and usually does lead to disaster.
You should never do this. Since compiler does not know whether the object was allocated on the
stack or on the heap, "delete this" could cause a disaster.
Q: What is assignment operator?
A: Default assignment operator handles assigning one object to another of the same class.
Member to member copy (shallow copy)
Q: What are all the implicit member functions of the class? Or what are all the functions which
compiler implements for us if we don't define one?A:
(a) default ctor
(b) copy ctor
(c) assignment operator
(d) default destructor
(e) address operator
Q: What is a container class? What are the types of container classes?
A: A container class is a class that is used to hold objects in memory or external storage. A
container class acts as a generic holder. A container class has a predefined behavior and a wellknown interface. A container class is a supporting class whose purpose is to hide the topology
used for maintaining the list of objects in memory. When a container class contains a group of
mixed objects, the container is called a heterogeneous container; when the container is holding a
group of objects that are all the same, the container is called a homogeneous container.
Q: What is Overriding?
A: To override a method, a subclass of the class that originally declared the method must declare
a method with the same name, return type (or a subclass of that return type), and same parameter
list.
The definition of the method overriding is:
· Must have same method name.
· Must have same data type.
· Must have same argument list.
Overriding a method means that replacing a method functionality in child class. To imply
overriding functionality we need parent and child classes. In the child class you define the same
method signature as one defined in the parent class.
Q: How do you access the static member of a class?
A: ::
Q: What is a nested class? Why can it be useful?
A: A nested class is a class enclosed within the scope of another class. For example:
// Example 1: Nested class
//
class OuterClass
{
class NestedClass
{
// ...
};
// ...
};
Nested classes are useful for organizing code and controlling access and dependencies. Nested
classes obey access rules just like other parts of a class do; so, in Example 1, if NestedClass is
public then any code can name it as OuterClass::NestedClass. Often nested classes contain
private implementation details, and are therefore made private; in Example 1, if NestedClass
is private, then only OuterClass's members and friends can use NestedClass. When you
instantiate as outer class, it won't instantiate inside class.
Q: What is a local class? Why can it be useful?
A: Local class is a class defined within the scope of a function _ any function, whether a
member function or a free function. For example:
// Example 2: Local class
//
int f()
{
class LocalClass
{
// ...
};
// ...
};
Like nested classes, local classes can be a useful tool for managing code dependencies.
Q: What a derived class can add?
A: New data members
New member functions
New constructors and destructor
New friends
Q: What happens when a derived-class object is created and destroyed?
A: Space is allocated (on the stack or the heap) for the full object (that is, enough space to store
the data members inherited from the base class plus the data members defined in the derived
class itself)
The base class's constructor is called to initialize the data members inherited from the base class
The derived class's constructor is then called to initialize the data members added in the derived
class
The derived-class object is then usable
When the object is destroyed (goes out of scope or is deleted) the derived class's destructor is
called on the object first
Then the base class's destructor is called on the object
Finally the allocated space for the full object is reclaimed
Q: How do I create a subscript operator for a Matrix class?
A: Use operator() rather than operator[].
When you have multiple subscripts, the cleanest way to do it is with operator() rather than with
operator[]. The reason is that operator[] always takes exactly one parameter, but operator() can
take any number of parameters (in the case of a rectangular matrix, two parameters are needed).
For example:
class Matrix {
public:
Matrix(unsigned rows, unsigned cols);
double& operator() (unsigned row, unsigned col); subscript operators often come in pairs
double operator() (unsigned row, unsigned col) const; subscript operators often come in pairs
...
~Matrix(); // Destructor
Matrix(const Matrix& m); // Copy constructor
Matrix& operator= (const Matrix& m); // Assignment operator
...
private:
unsigned rows_, cols_;
double* data_;
};
inline
Matrix::Matrix(unsigned rows, unsigned cols)
: rows_ (rows)
, cols_ (cols)
//data_ <--initialized below (after the 'if/throw' statement)
{
if (rows == 0 || cols == 0)
throw BadIndex("Matrix constructor has 0 size");
data_ = new double[rows * cols];
}
inline
Matrix::~Matrix()
{
delete[] data_;
}
inline
double& Matrix::operator() (unsigned row, unsigned col)
{
if (row >= rows_ || col >= cols_)
throw BadIndex("Matrix subscript out of bounds");
return data_[cols_*row + col];
}
inline
double Matrix::operator() (unsigned row, unsigned col) const
{
if (row >= rows_ || col >= cols_)
throw BadIndex("const Matrix subscript out of bounds");
return data_[cols_*row + col];
}
Then you can access an element of Matrix m using m(i,j) rather than m[i][j]:
int main()
{
Matrix m(10,10);
m(5,8) = 106.15;
std::cout << m(5,8);
...
}
Q: Why shouldn't my Matrix class's interface look like an array-of-array?
A: Here's what this FAQ is really all about: Some people build a Matrix class that has an
operator[] that returns a reference to an Array object (or perhaps to a raw array, shudder), and
that Array object has an operator[] that returns an element of the Matrix (e.g., a reference to a
double). Thus they access elements of the matrix using syntax like m[i][j] rather than syntax like
m(i,j).
The array-of-array solution obviously works, but it is less flexible than the operator() approach.
Specifically, there are easy performance tuning tricks that can be done with the operator()
approach that are more difficult in the [][] approach, and therefore the [][] approach is more
likely to lead to bad performance, at least in some cases.
For example, the easiest way to implement the [][] approach is to use a physical layout of the
matrix as a dense matrix that is stored in row-major form (or is it column-major; I can't ever
remember). In contrast, the operator() approach totally hides the physical layout of the matrix,
and that can lead to better performance in some cases.
Put it this way: the operator() approach is never worse than, and sometimes better than, the [][]
approach.
The operator() approach is never worse because it is easy to implement the dense, row-major
physical layout using the operator() approach, so when that configuration happens to be the
optimal layout from a performance standpoint, the operator() approach is just as easy as the [][]
approach (perhaps the operator() approach is a tiny bit easier, but I won't quibble over minor
nits).
The operator() approach is sometimes better because whenever the optimal layout for a given
application happens to be something other than dense, row-major, the implementation is often
significantly easier using the operator() approach compared to the [][] approach.
As an example of when a physical layout makes a significant difference, a recent project
happened to access the matrix elements in columns (that is, the algorithm accesses all the
elements in one column, then the elements in another, etc.), and if the physical layout is rowmajor, the accesses can "stride the cache". For example, if the rows happen to be almost as big as
the processor's cache size, the machine can end up with a "cache miss" for almost every element
access. In this particular project, we got a 20% improvement in performance by changing the
mapping from the logical layout (row,column) to the physical layout (column,row).
Of course there are many examples of this sort of thing from numerical methods, and sparse
matrices are a whole other dimension on this issue. Since it is, in general, easier to implement a
sparse matrix or swap row/column ordering using the operator() approach, the operator()
approach loses nothing and may gain something it has no down-side and a potential up-side.
Use the operator() approach.
Q: Should I design my classes from the outside (interfaces first) or from the inside (data first)?
A: From the outside!
A good interface provides a simplified view that is expressed in the vocabulary of a user. In the
case of OO software, the interface is normally the set of public methods of either a single class or
a tight group of classes.
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 // 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 template.
PREVIOUS NEXT
CLASSES
Q: What is a class?
A: A class is an expanded concept of a data structure: instead of holding only data, it can hold
both data and functions.
Q: What are the differences between a C++ struct and C++ class? A: The default member and base class access specifies are different. This is one of the
commonly misunderstood aspects of C++. Believe it or not, many programmers think that a C++
struct is just like a C struct, while a C++ class has inheritance, access specifes, member
functions, overloaded operators, and so on. Actually, the C++ struct has all the features of the
class. The only differences are that a struct defaults to public member access and public base
class inheritance, and a class defaults to the private access specified and private base-class
inheritance.
Q: How do you know that your class needs a virtual destructor?
A: If your class has at least one virtual function, you should make a destructor for this class
virtual. This will allow you to delete a dynamic object through a caller to a base class object. If
the destructor is non-virtual, then wrong destructor will be invoked during deletion of the
dynamic object.
Q: What is encapsulation?
A: Containing and hiding Information about an object, such as internal data structures and code.
Encapsulation isolates the internal complexity of an object's operation from the rest of the
application. For example, a client component asking for net revenue from a business object need
not know the data's origin.
Q: What is "this" pointer?
A: The this pointer is a pointer accessible only within the member functions of a class, struct, or
union type. It points to the object for which the member function is called. Static member
functions do not have a this pointer. When a nonstatic member function is called for an
object, the address of the object is passed as a hidden argument to the function. For example, the
following function call
myDate.setMonth( 3 );
can be interpreted this way:
setMonth( &myDate, 3 );
The object's address is available from within the member function as the this pointer. It is legal,
though unnecessary, to use the this pointer when referring to members of the class.
Q: What happens when you make call "delete this;"?
A: The code has two built-in pitfalls. First, if it executes in a member function for an extern,
static, or automatic object, the program will probably crash as soon as the delete statement
executes. There is no portable way for an object to tell that it was instantiated on the heap, so the
class cannot assert that its object is properly instantiated. Second, when an object commits
suicide this way, the using program might not know about its demise. As far as the instantiating
program is concerned, the object remains in scope and continues to exist even though the object
did itself in. Subsequent dereferencing of the pointer can and usually does lead to disaster.
You should never do this. Since compiler does not know whether the object was allocated on the
stack or on the heap, "delete this" could cause a disaster.
Q: What is assignment operator?
A: Default assignment operator handles assigning one object to another of the same class.
Member to member copy (shallow copy)
Q: What are all the implicit member functions of the class? Or what are all the functions which
compiler implements for us if we don't define one?A:
(a) default ctor
(b) copy ctor
(c) assignment operator
(d) default destructor
(e) address operator
Q: What is a container class? What are the types of container classes?
A: A container class is a class that is used to hold objects in memory or external storage. A
container class acts as a generic holder. A container class has a predefined behavior and a wellknown interface. A container class is a supporting class whose purpose is to hide the topology
used for maintaining the list of objects in memory. When a container class contains a group of
mixed objects, the container is called a heterogeneous container; when the container is holding a
group of objects that are all the same, the container is called a homogeneous container.
Q: What is Overriding?
A: To override a method, a subclass of the class that originally declared the method must declare
a method with the same name, return type (or a subclass of that return type), and same parameter
list.
The definition of the method overriding is:
· Must have same method name.
· Must have same data type.
· Must have same argument list.
Overriding a method means that replacing a method functionality in child class. To imply
overriding functionality we need parent and child classes. In the child class you define the same
method signature as one defined in the parent class.
Q: How do you access the static member of a class?
A: ::
Q: What is a nested class? Why can it be useful?
A: A nested class is a class enclosed within the scope of another class. For example:
// Example 1: Nested class
//
class OuterClass
{
class NestedClass
{
// ...
};
// ...
};
Nested classes are useful for organizing code and controlling access and dependencies. Nested
classes obey access rules just like other parts of a class do; so, in Example 1, if NestedClass is
public then any code can name it as OuterClass::NestedClass. Often nested classes contain
private implementation details, and are therefore made private; in Example 1, if NestedClass
is private, then only OuterClass's members and friends can use NestedClass. When you
instantiate as outer class, it won't instantiate inside class.
Q: What is a local class? Why can it be useful?
A: Local class is a class defined within the scope of a function _ any function, whether a
member function or a free function. For example:
// Example 2: Local class
//
int f()
{
class LocalClass
{
// ...
};
// ...
};
Like nested classes, local classes can be a useful tool for managing code dependencies.
Q: What a derived class can add?
A: New data members
New member functions
New constructors and destructor
New friends
Q: What happens when a derived-class object is created and destroyed?
A: Space is allocated (on the stack or the heap) for the full object (that is, enough space to store
the data members inherited from the base class plus the data members defined in the derived
class itself)
The base class's constructor is called to initialize the data members inherited from the base class
The derived class's constructor is then called to initialize the data members added in the derived
class
The derived-class object is then usable
When the object is destroyed (goes out of scope or is deleted) the derived class's destructor is
called on the object first
Then the base class's destructor is called on the object
Finally the allocated space for the full object is reclaimed
Q: How do I create a subscript operator for a Matrix class?
A: Use operator() rather than operator[].
When you have multiple subscripts, the cleanest way to do it is with operator() rather than with
operator[]. The reason is that operator[] always takes exactly one parameter, but operator() can
take any number of parameters (in the case of a rectangular matrix, two parameters are needed).
For example:
class Matrix {
public:
Matrix(unsigned rows, unsigned cols);
double& operator() (unsigned row, unsigned col); subscript operators often come in pairs
double operator() (unsigned row, unsigned col) const; subscript operators often come in pairs
...
~Matrix(); // Destructor
Matrix(const Matrix& m); // Copy constructor
Matrix& operator= (const Matrix& m); // Assignment operator
...
private:
unsigned rows_, cols_;
double* data_;
};
inline
Matrix::Matrix(unsigned rows, unsigned cols)
: rows_ (rows)
, cols_ (cols)
//data_ <--initialized below (after the 'if/throw' statement)
{
if (rows == 0 || cols == 0)
throw BadIndex("Matrix constructor has 0 size");
data_ = new double[rows * cols];
}
inline
Matrix::~Matrix()
{
delete[] data_;
}
inline
double& Matrix::operator() (unsigned row, unsigned col)
{
if (row >= rows_ || col >= cols_)
throw BadIndex("Matrix subscript out of bounds");
return data_[cols_*row + col];
}
inline
double Matrix::operator() (unsigned row, unsigned col) const
{
if (row >= rows_ || col >= cols_)
throw BadIndex("const Matrix subscript out of bounds");
return data_[cols_*row + col];
}
Then you can access an element of Matrix m using m(i,j) rather than m[i][j]:
int main()
{
Matrix m(10,10);
m(5,8) = 106.15;
std::cout << m(5,8);
...
}
Q: Why shouldn't my Matrix class's interface look like an array-of-array?
A: Here's what this FAQ is really all about: Some people build a Matrix class that has an
operator[] that returns a reference to an Array object (or perhaps to a raw array, shudder), and
that Array object has an operator[] that returns an element of the Matrix (e.g., a reference to a
double). Thus they access elements of the matrix using syntax like m[i][j] rather than syntax like
m(i,j).
The array-of-array solution obviously works, but it is less flexible than the operator() approach.
Specifically, there are easy performance tuning tricks that can be done with the operator()
approach that are more difficult in the [][] approach, and therefore the [][] approach is more
likely to lead to bad performance, at least in some cases.
For example, the easiest way to implement the [][] approach is to use a physical layout of the
matrix as a dense matrix that is stored in row-major form (or is it column-major; I can't ever
remember). In contrast, the operator() approach totally hides the physical layout of the matrix,
and that can lead to better performance in some cases.
Put it this way: the operator() approach is never worse than, and sometimes better than, the [][]
approach.
The operator() approach is never worse because it is easy to implement the dense, row-major
physical layout using the operator() approach, so when that configuration happens to be the
optimal layout from a performance standpoint, the operator() approach is just as easy as the [][]
approach (perhaps the operator() approach is a tiny bit easier, but I won't quibble over minor
nits).
The operator() approach is sometimes better because whenever the optimal layout for a given
application happens to be something other than dense, row-major, the implementation is often
significantly easier using the operator() approach compared to the [][] approach.
As an example of when a physical layout makes a significant difference, a recent project
happened to access the matrix elements in columns (that is, the algorithm accesses all the
elements in one column, then the elements in another, etc.), and if the physical layout is rowmajor, the accesses can "stride the cache". For example, if the rows happen to be almost as big as
the processor's cache size, the machine can end up with a "cache miss" for almost every element
access. In this particular project, we got a 20% improvement in performance by changing the
mapping from the logical layout (row,column) to the physical layout (column,row).
Of course there are many examples of this sort of thing from numerical methods, and sparse
matrices are a whole other dimension on this issue. Since it is, in general, easier to implement a
sparse matrix or swap row/column ordering using the operator() approach, the operator()
approach loses nothing and may gain something it has no down-side and a potential up-side.
Use the operator() approach.
Q: Should I design my classes from the outside (interfaces first) or from the inside (data first)?
A: From the outside!
A good interface provides a simplified view that is expressed in the vocabulary of a user. In the
case of OO software, the interface is normally the set of public methods of either a single class or
a tight group of classes.
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 // 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 template.
PREVIOUS NEXT
No comments:
Post a Comment