operator overloading

Operator Overloading

What’s the deal with operator overloading?

It allows you to provide an intuitive interface to users of your class, plus makes it possible for templates to work equally well with classes and built-in/intrinsic types.

Operator overloading allows C/C++ operators to have user-defined meanings on user-defined types (classes). Overloaded operators are syntactic sugar for function calls:

class Fred {
public:
  // ...
};

#if 0

  // Without operator overloading:
  Fred add(const Fred& x, const Fred& y);
  Fred mul(const Fred& x, const Fred& y);

  Fred f(const Fred& a, const Fred& b, const Fred& c)
  {
    return add(add(mul(a,b), mul(b,c)), mul(c,a));    // Yuk...
  }

#else

  // With operator overloading:
  Fred operator+ (const Fred& x, const Fred& y);
  Fred operator* (const Fred& x, const Fred& y);

  Fred f(const Fred& a, const Fred& b, const Fred& c)
  {
    return a*b + b*c + c*a;
  }

#endif

What are the benefits of operator overloading?

By overloading standard operators on a class, you can exploit the intuition of the users of that class. This lets users program in the language of the problem domain rather than in the language of the machine.

The ultimate goal is to reduce both the learning curve and the defect rate.

What are some examples of operator overloading?

Here are a few of the many examples of operator overloading:

  • myString + yourString might concatenate two std::string objects
  • myDate++ might increment a Date object
  • a * b might multiply two Number objects
  • a[i] might access an element of an Array object
  • x = *p might dereference a “smart pointer” that “points” to a disk record — it could seek to the location on disk where p “points” and return the appropriate record into x

But operator overloading makes my class look ugly; isn’t it supposed to make my code clearer?

Operator overloading makes life easier for the users of a class, not for the developer of the class!

Consider the following example.

class Array {
public:
  int& operator[] (unsigned i);      // Some people don't like this syntax
  // ...
};

inline
int& Array::operator[] (unsigned i)  // Some people don't like this syntax
{
  // ...
}

Some people don’t like the keyword operator or the somewhat funny syntax that goes with it in the body of the class itself. But the operator overloading syntax isn’t supposed to make life easier for the developer of a class. It’s supposed to make life easier for the users of the class:

int main()
{
  Array a;
  a[3] = 4;   // User code should be obvious and easy to understand...
  // ...
}

Remember: in a reuse-oriented world, there will usually be many people who use your class, but there is only one person who builds it (yourself); therefore you should do things that favor the many rather than the few.

What operators can/cannot be overloaded?

Most can be overloaded. The only C operators that can’t be are . and ?: (and sizeof, which is technically an operator). C++ adds a few of its own operators, most of which can be overloaded except :: and .*.

Here’s an example of the subscript operator (it returns a reference). First without operator overloading:

class Array {
public:
  int& elem(unsigned i)        { if (i > 99) error(); return data[i]; }
private:
  int data[100];
};

int main()
{
  Array a;
  a.elem(10) = 42;
  a.elem(12) += a.elem(13);
  // ...
}

Now the same logic is presented with operator overloading:

class Array {
public:
  int& operator[] (unsigned i) { if (i > 99) error(); return data[i]; }
private:
  int data[100];
};

int main()
{
  Array a;
  a[10] = 42;
  a[12] += a[13];
  // ...
}

Why can’t I overload . (dot), ::, sizeof, etc.?

Most operators can be overloaded by a programmer. The exceptions are

    . (dot)  ::  ?:  sizeof

There is no fundamental reason to disallow overloading of ?:. So far the committee just hasn’t seen the need to introduce the special case of overloading a ternary operator. Note that a function overloading expr1?expr2:expr3 would not be able to guarantee that only one of expr2 and expr3 was executed.

sizeof cannot be overloaded because built-in operations, such as incrementing a pointer into an array implicitly depends on it. Consider:

    X a[10];
    X* p = &a[3];
    X* q = &a[3];
    p++;    // p points to a[4]
        // thus the integer value of p must be
        // sizeof(X) larger than the integer value of q

Thus, sizeof(X) could not be given a new and different meaning by the programmer without violating basic language rules.

What about ::? In N::m neither N nor m are expressions with values; N and m are names known to the compiler and :: performs a (compile time) scope resolution rather than an expression evaluation. One could imagine allowing overloading of x::y where x is an object rather than a namespace or a class, but that would – contrary to first appearances – involve introducing new syntax (to allow expr::expr). It is not obvious what benefits such a complication would bring.

operator. (dot) could in principle be overloaded using the same technique as used for ->. However, doing so can lead to questions about whether an operation is meant for the object overloading . or an object referred to by .. For example:

    class Y {
    public:
        void f();
        // ...
    };

    class X {   // assume that you can overload .
        Y* p;
        Y& operator.() { return *p; }
        void f();
        // ...
    };

    void g(X& x)
    {
        x.f();  // X::f or Y::f or error?
    }

This problem can be solved in several ways. So far in standardization, it has not been obvious which way would be best. For more details, see D&E.

Can I define my own operators?

Sorry, no. The possibility has been considered several times, but each time it was decided that the likely problems outweighed the likely benefits.

It’s not a language-technical problem. Even when Stroustrup first considered it in 1983, he knew how it could be implemented. However, the experience has been that when we go beyond the most trivial examples people seem to have subtly different opinions of “the obvious” meaning of uses of an operator. A classical example is a**b**c. Assume that ** has been made to mean exponentiation. Now should a**b**c mean (a**b)**c or a**(b**c)? Experts have thought the answer was obvious and their friends agreed – and then found that they didn’t agree on which resolution was the obvious one. Such problems seem prone to lead to subtle bugs.

Can I overload operator== so it lets me compare two char[] using a string comparison?

No: at least one operand of any overloaded operator must be of some user-defined type (most of the time that means a class).

But even if C++ allowed you to do this, which it doesn’t, you wouldn’t want to do it anyway since you really should be using a std::string-like class rather than an array of char in the first place since arrays are evil.

Can I create a operator** for “to-the-power-of” operations?

Nope.

The names of, precedence of, associativity of, and arity of operators is fixed by the language. There is no operator** in C++, so you cannot create one for a class type.

If you’re in doubt, consider that x ** y is the same as x * (*y) (in other words, the compiler assumes y is a pointer). Besides, operator overloading is just syntactic sugar for function calls. Although this particular syntactic sugar can be very sweet, it doesn’t add anything fundamental. I suggest you overload pow(base,exponent) (a double precision version is in <cmath>).

By the way, operator^ can work for to-the-power-of, except it has the wrong precedence and associativity.

The previous FAQs tell me which operators I can override; but which operators should I override?

Bottom line: don’t confuse your users.

Remember the purpose of operator overloading: to reduce the cost and defect rate in code that uses your class. If you create operators that confuse your users (because they’re cool, because they make the code faster, because you need to prove to yourself that you can do it; doesn’t really matter why), you’ve violated the whole reason for using operator overloading in the first place.

What are some guidelines / “rules of thumb” for overloading operators?

Here are a few guidelines / rules of thumb (but be sure to read the previous FAQ before reading this list):

  1. Use common sense. If your overloaded operator makes life easier and safer for your users, do it; otherwise don’t. This is the most important guideline. In fact it is, in a very real sense, the only guideline; the rest are just special cases.
  2. If you define arithmetic operators, maintain the usual arithmetic identities. For example, if your class defines x + y and x - y, then x + y - y ought to return an object that is behaviorally equivalent to x. The term behaviorally equivalent is defined in the bullet on x == y below, but simply put, it means the two objects should ideally act like they have the same state. This should be true even if you decide not to define an == operator for objects of your class.
  3. You should provide arithmetic operators only when they make logical sense to users. Subtracting two dates makes sense, logically returning the duration between those dates, so you might want to allow date1 - date2 for objects of your Date class (provided you have a reasonable class/type to represent the duration between two Date objects). However adding two dates makes no sense: what does it mean to add July 4, 1776 to June 5, 1959? Similarly it makes no sense to multiply or divide dates, so you should not define any of those operators.
  4. You should provide mixed-mode arithmetic operators only when they make logical sense to users. For example, it makes sense to add a duration (say 35 days) to a date (say July 4, 1776), so you might define date + duration to return a Date. Similarly date - duration could also return a Date. But duration - date does not make sense at the conceptual level (what does it mean to subtract July 4, 1776 from 35 days?) so you should not define that operator.
  5. If you provide constructive operators, they should return their result by value. For example, x + y should return its result by value. If it returns by reference, you will probably run into lots of problems figuring out who owns the referent and when the referent will get destructed. Doesn’t matter if returning by reference is more efficient; it is probably wrong. See the next bullet for more on this point.
  6. If you provide constructive operators, they should not change their operands. For example, x + y should not change x. For some crazy reason, programmers often define x + y to be logically the same as x += y because the latter is faster. But remember, your users expect x + y to make a copy. In fact they selected the + operator (over, say, the += operator) precisely because they wanted a copy. If they wanted to modify x, they would have used whatever is equivalent to x += y instead. Don’t make semantic decisions for your users; it’s their decision, not yours, whether they want the semantics of x + y vs. x += y. Tell them that one is faster if you want, but then step back and let them make the final decision — they know what they’re trying to achieve and you do not.
  7. If you provide constructive operators, they should allow promotion of the left-hand operand (at least in the case where the class has a single-parameter ctor that is not marked with the explicit keyword). For example, if your class Fraction supports promotion from int to Fraction (via the non-explicit ctor Fraction::Fraction(int)), and if you allow x - y for two Fraction objects, you should also allow 42 - y. In practice that simply means that your operator-() should not be a member function of Fraction. Typically you will make it a friend, if for no other reason than to force it into the public: part of the class, but even if it is not a friend, it should not be a member.
  8. In general, your operator should change its operand(s) if and only if the operands get changed when you apply the same operator to intrinsic types. x == y and x << y should not change either operand; x *= y and x <<= y should (but only the left-hand operand).
  9. If you define x++ and ++x, maintain the usual identities. For example, x++ and ++x should have the same observable effect on x, and should differ only in what they return. ++x should return x by reference; x++ should either return a copy (by value) of the original state of x or should have a void return-type. You’re usually better off returning a copy of the original state of x by value, especially if your class will be used in generic algorithms. The easy way to do that is to implement x++ using three lines: make a local copy of *this, call ++x (i.e., this->operator++()), then return the local copy. Similar comments for x-- and --x.
  10. If you define ++x and x += 1, maintain the usual identities. For example, these expressions should have the same observable behavior, including the same result. Among other things, that means your += operator should return x by reference. Similar comments for --x and x -= 1.
  11. If you define *p and p[0] for pointer-like objects, maintain the usual identities. For example, these two expressions should have the same result and neither should change p.
  12. If you define p[i] and *(p+i) for pointer-like objects, maintain the usual identities. For example, these two expressions should have the same result and neither should change p. Similar comments for p[-i] and *(p-i).
  13. Subscript operators generally come in pairs; see on const-overloading.
  14. If you define x == y, then x == y should be true if and only if the two objects are behaviorally equivalent. In this bullet, the term “behaviorally equivalent” means the observable behavior of any operation or sequence of operations applied to x will be the same as when applied to y. The term “operation” means methods, friends, operators, or just about anything else you can do with these objects (except, of course, the address-of operator). You won’t always be able to achieve that goal, but you ought to get close, and you ought to document any variances (other than the address-of operator).
  15. If you define x == y and x = y, maintain the usual identities. For example, after an assignment, the two objects should be equal. Even if you don’t define x == y, the two objects should be behaviorally equivalent (see above for the meaning of that phrase) after an assignment.
  16. If you define x == y and x != y, you should maintain the usual identities. For example, these expressions should return something convertible to bool, neither should change its operands, and x == y should have the same result as !(x != y), and vice versa.
  17. If you define inequality operators like x <= y and x < y, you should maintain the usual identities. For example, if x < y and y < z are both true, then x < z should also be true, etc. Similar comments for x >= y and x > y.
  18. If you define inequality operators like x < y and x >= y, you should maintain the usual identities. For example, x < y should have the result as !(x >= y). You can’t always do that, but you should get close and you should document any variances. Similar comments for x > y and !(x <= y), etc.
  19. Avoid overloading short-circuiting operators: x || y or x && y. The overloaded versions of these do not short-circuit — they evaluate both operands even if the left-hand operand “determines” the outcome, so that confuses users.
  20. Avoid overloading the comma operator: x, y. The overloaded comma operator does not have the same ordering properties that it has when it is not overloaded, and that confuses users.
  21. Don’t overload an operator that is non-intuitive to your users. This is called the Doctrine of Least Surprise. For example, although C++ uses std::cout << x for printing, and although printing is technically called inserting, and although inserting sort of sounds like what happens when you push an element onto a stack, don’t overload myStack << x to push an element onto a stack. It might make sense when you’re really tired or otherwise mentally impaired, and a few of your friends might think it’s “kewl,” but just say No.
  22. Use common sense. If you don’t see “your” operator listed here, you can figure it out. Just remember the ultimate goals of operator overloading: to make life easier for your users, in particular to make their code cheaper to write and more obvious.

Caveat: the list is not exhaustive. That means there are other entries that you might consider “missing.” I know.

Caveat: the list contains guidelines, not hard and fast rules. That means almost all of the entries have exceptions, and most of those exceptions are not explicitly stated. I know.

Caveat: please don’t email me about the additions or exceptions. I’ve already spent way too much time on this particular answer.

How do I create a subscript operator for a Matrix class?

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);
  // ...
}

See the next FAQ for more detail on the reasons to use m(i,j) vs. m[i][j].

Why shouldn’t my Matrix class’s interface look like an array-of-array?

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 row-major, 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.

I still don’t get it. Why shouldn’t my Matrix class’s interface look like an array-of-array?

The same reasons you encapsulate your data structures, and the same reason you check parameters to make sure they are valid.

A few people use [][] despite its limitations, arguing that [][] is better because it is faster or because it uses C-syntax. The problem with the “it’s faster” argument is that it’s not — at least not on the latest version of two of the world’s best known C++ compilers. The problem with the “uses C-syntax” argument is that C++ is not C. Plus, oh yea, the C-syntax makes it harder to change the data structure and harder to check parameter values.

The point of the previous two FAQs is that m(i,j) gives you a clean, simple way to check all the parameters and to hide (and therefore, if you want to, change) the internal data structure. The world already has way too many exposed data structures and way too many out-of-bounds parameters, and those cost way too much money and cause way too many delays and way too many defects.

Now everybody knows that you are different. You are clairvoyant with perfect knowledge of the future, and you know that no one will ever find any benefit from changing your matrix’s internal data structure. Plus you are a good programmer, unlike those slobs out there that occasionally pass wrong parameters, so you don’t need to worry about pesky little things like parameter checking. But even though you don’t need to worry about maintenance costs (no one ever needs to change your code), there might be one or two other programmers who aren’t quite perfect yet. For them, maintenance costs are high, defects are real, and requirements change. Believe it or not, every once in a while they need to (better sit down) change their code.

Admittedly my thongue wath in my theek. But there was a point. The point was that encapsulation and parameter-checking are not crutches for the weak. It’s smart to use techniques that make encapsulation and/or parameter checking easy. The m(i,j) syntax is one of those techniques.

Having said all that, if you find yourself maintaining a billion-line app where the original team used m[i][j], or even if you are writing a brand new app and you just plain want to use m[i][j], you can still encapsulate the data structure and/or check all your parameters. It’s not even that hard. However it does require a level of sophistication that, like it or not, average C++ programmers fear. Fortunately you are not average, so read on.

If you merely want to check parameters, just make sure the outer operator[] returns an object rather than a raw array, then that object’s operator[] can check its parameter in the usual way. Beware that this can slow down your program. In particular, if these inner array-like objects end up allocating their own block of memory for their row of the matrix, the performance overhead for creating / destroying your matrix objects can grow dramatically. The theoretical cost is still O(rows × cols), but in practice, the overhead of the memory allocator (new or malloc) can be much larger than anything else, and that overhead can swamp the other costs. For instance, on two of the world’s best known C++ compilers, the separate-allocation-per-row technique was 10x slower than the one-allocation-for-the-entire-matrix technique. 10% is one thing, 10x is another.

If you want to check the parameters without the above overhead and/or if you want to encapsulate (and possibly change) the matrix’s internal data structure, follow these steps:

  1. Add operator()(unsigned row, unsigned col) to the Matrix class.
  2. Create nested class Matrix::Row. It should have a ctor with parameters (Matrix& matrix, unsigned row), and it should store those two values in its this object.
  3. Change Matrix::operator[](unsigned row) so it returns an object of class Matrix::Row, e.g., { return Row(*this,row); }.
  4. Class Matrix::Row then defines its own operator[](unsigned col) which turns around and calls, you guessed it, Matrix::operator()(unsigned row, unsigned col). If the Matrix::Row data members are called Matrix& matrix_ and unsigned row_, the code for Matrix::Row::operator[](unsigned col) will be { return matrix_(row_, col); }

Next you will enable const overloading by repeating the above steps. You will create the const version of the various methods, and you will create a new nested class, probably called Matrix::ConstRow. Don’t forget to use const Matrix& instead of Matrix&.

Final step: find the joker who failed to read the previous FAQ and thonk him in the noggin.

If you have a decent compiler and if you judiciously use inlining, the compiler should optimize away the temporary objects. In other words, the operator[]-approach above will hopefully not be slower than what it would have been if you had directly called Matrix::operator()(unsigned row, unsigned col) in the first place. Of course you could have made your life simpler and avoided most of the above work by directly calling Matrix::operator()(unsigned row, unsigned col) in the first place. So you might as well directly call Matrix::operator()(unsigned row, unsigned col) in the first place.

Should I design my classes from the outside (interfaces first) or from the inside (data first)?

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 <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.

How can I overload the prefix and postfix forms of operators ++ and --?

Via a dummy parameter.

Since the prefix and postfix ++ operators can have two definitions, the C++ language gives us two different signatures. Both are called operator++(), but the prefix version takes no parameters and the postfix version takes a dummy int. (Although this discussion revolves around the ++ operator, the -- operator is completely symmetric, and all the rules and guidelines that apply to one also apply to the other.)

class Number {
public:
  Number& operator++ ();    // prefix ++
  Number  operator++ (int); // postfix ++
};

Note the different return types: the prefix version returns by reference, the postfix version by value. If that’s not immediately obvious to you, it should be after you see the definitions (and after you remember that y = x++ and y = ++x set y to different things).

Number& Number::operator++ ()
{
  // ...
  return *this;
}

Number Number::operator++ (int)
{
  Number ans = *this;
  ++(*this);  // or just call operator++()
  return ans;
}

The other option for the postfix version is to return nothing:

class Number {
public:
  Number& operator++ ();
  void    operator++ (int);
};

Number& Number::operator++ ()
{
  // ...
  return *this;
}

void Number::operator++ (int)
{
  ++(*this);  // or just call operator++()
}

However you must not make the postfix version return the this object by reference; you have been warned.

Here’s how you use these operators:

Number x = /* ... */;
++x;  // calls Number::operator++(), i.e., calls x.operator++()
x++;  // calls Number::operator++(int), i.e., calls x.operator++(0)

Assuming the return types are not ‘void’, you can use them in larger expressions:

Number x = /* ... */;
Number y = ++x;  // y will be the new value of x
Number z = x++;  // z will be the old value of x

Which is more efficient: i++ or ++i?

++i is sometimes faster than, and is never slower than, i++.

For intrinsic types like int, it doesn’t matter: ++i and i++ are the same speed. For class types like iterators or the previous FAQ’s Number class, ++i very well might be faster than i++ since the latter might make a copy of the this object.

The overhead of i++, if it is there at all, won’t probably make any practical difference unless your app is CPU bound. For example, if your app spends most of its time waiting for someone to click a mouse, doing disk I/O, network I/O, or database queries, then it won’t hurt your performance to waste a few CPU cycles. However it’s just as easy to type ++i as i++, so why not use the former unless you actually need the old value of i.

So if you’re writing i++ as a statement rather than as part of a larger expression, why not just write ++i instead? You never lose anything, and you sometimes gain something. Old line C programmers are used to writing i++ instead of ++i. E.g., they’ll say, for (i = 0; i < 10; i++) .... Since this uses i++ as a statement, not as a part of a larger expression, then you might want to use ++i instead. For symmetry, I personally advocate that style even when it doesn’t improve speed, e.g., for intrinsic types and for class types with postfix operators that return void.

Obviously when i++ appears as a part of a larger expression, that’s different: it’s being used because it’s the only logically correct solution, not because it’s an old habit you picked up while programming in C.