http://www.possibility.com/Cpp/const.html

Great overview of C++ Const correctness... test bookmark for my blog How to I get this on my blog?

That's right... word counter. Jeanna's students will know what I'm talking about.

For those of you that don't, this word counter, for one whole semester, was my pride and joy. Jeanna used this toy example program to help demonstrate how even the simplest programs, if not properly thought out and designed, can cause you massive headaches in a world where software consumers can't make up their minds. Jeanna would change the definition of what constitutes a "word" weekly, and off we'd go to adjust our counters - keeping in mind the end goal of having the fastest and most correct counter.

I'm pleased to say that my counter -- fully object oriented and extremely well designed -- was the second fastest in the class; beat out only by a man who some know as a maniac, others as my then-nemesis (due to our massively conflicting approaches to this project). He wrote his counter as a state machine, driven by goto's, in C. While unbeatable in speed, the low-level implementation required a complete re-write with each iteration. Mine only required a single line change, perhaps two or three depending how drastic the definition change was. But at most, I spent minutes each week on this project after my initial implementation*.

This application was also the start of my years-long const correctness frenzy. Check out the source -- it's const correct to the extreme!

You can download it here: word counter

* not including the time spent doing optimizations.

Here's a very thorough article that supplements my recent const rant very nicely. I received a number of emails back arguing against my point that const is important and influential. While I realize that many developers maintain that const-correctness is a waste of time, I maintain that those people are unskilled and lazy ;).

Developing classes that are not const-correct severely limits its usage in well thought out applications, if for no other reason than that a constant instance of your class is unusable! You can't call non-const methods on const instances, nor can const-methods access non-const (or non-mutable) members. It's just plain lunacy to not keep const in mind when developing a solid object oriented system.

Just as a follow up to my last post, here's a quick overview of the const keyword

1. const int x = 5;
2. const int * px;
3. int const * px;
4. const int * const px;

1. A constant integer with a value of 5. The value of x will be 5 for its entire life.
2. A pointer to a constant integer. The value of the integer pointed to by px can not be changed; however you may point px to a different integer.
3. This is the same as #2. The const keyword may appear before or after the type it is qualified on. I prefer the style in #2, but both are syntactically correct.
4. A constant pointer to a constant integer. You can not change the value of the integer being pointed to, nor can you point px to a different integer.

const is, in my opinion, the most influential and least frequeuently used keyword in the C++ programming language.

This may seem like a very bold statement, but having recently started work on a relatively large C++ application, I'm finding that developer's lack of const usage is hindering my ability to write solid code. I'm trying desperately not to fall into the trap that many developers do, of abondonding const because it'd been forgotten; but the Software Engineer in me can't let go, and I'm spending a lot of time re-writing code with proper const usage.

Lets look at a simple example of how many developers would write a simple class:

#include <string>
using namespace std;

class Monkey {
public:
  Monkey( string name );

  string GetName();
  
private:
  string name;
};

Simple enough. It's a monkey with a name. Let's say I manage the Monkey House at the zoo. I might then want to have a collection of monkeys available to me:

#include <map>
#include <string>
#include "monkey.h"

using namespace std;

class MonkeyHouse {
public:
  bool containsMonkey( string & name );
  void addMonkey( Monkey* m );
  void removeMonkey( Monkey* m );
  Monkey * getMonkey( string &name );

private:
  map< string, Monkey* > myMonkeys;
};

Again, simple enough. Too bad it's horrendous. This simple API raises numerous questions that should be obvious to the conscientous developer:

1. Will containsMonkey( string& ) change the value of my name parameter?
2. Will addMonkey( Monkey* ) change the value of my monkey?
3. Will removeMonkey( Monkey* ) change the value of my monkey?

And more importantly for each of these questions, if the answer is yes, then when -- before or after it performs is expected function?

Lets say you were dropped into this project and wanted to make it "more solid". We can start by addressing those questions above with the const keyword:

class MonkeyHouse {
public:
  bool containsMonkey( const string & name );
  void addMonkey( const Monkey* m );
  void removeMonkey( const Monkey* m );
  Monkey * getMonkey( const string &name );

private:
  map< string, Monkey* > myMonkeys;
};

This simple addition of const to your method parameters ensures users of your API that objects passed will not be changed by that method. Remember that a const Monkey * m though is a pointer to a const monkey. The method could still change which monkey is pointed to my m if it so chooses. A slightly safer declaration might look like this:

class MonkeyHouse {
public:
  bool containsMonkey( const string & name );
  void addMonkey( const Monkey* const m );
  void removeMonkey( const Monkey* const m );
  Monkey * getMonkey( const string &name );

private:
  map< string, Monkey* > myMonkeys;
};

Now the methods that take monkey pointers take constant pointers to constant monkeys. Users of your API can now be utterly certain that the method will not change the monkey, nor will it change the monkey you're pointing too. Good! This is a great start.

Too bad it won't compile.

I think it's safe to assume that addMonkey( const Monkey* const m ) looks a lot like this:

void Monkey::addMonkey( const Monkey* const m ) {
  myMonkeys[ m->GetName() ] = m;
}

We can't assign m to myMonkeys[ key ] though, because myMonkeys contains pointers to monkeys, not pointers to constant monkeys. You'll get a cast error. Fixing the map declaration is easy enough though, we'll just make it:

  map< string, const Monkey* > myMonkeys;

Great! Too bad it won't compile.

You're now assigning a pointer to a constant monkey to myMonkeys[ m->GetName() ]. However, you can't call Monkey::GetName() on a constant monkey, because it's not a constant method! Argh! Lets revisit the Monkey API, shall we?

class Monkey {
public:
  Monkey( string name );

  string GetName() const;
  
private:
  string name;
};

By declaring GetName() to be const we are saying that GetName will not change the value of this Monkey instance. I can now call GetName() on constant monkeys.

Great! Too bad in won't compile...

MonkeyHouse's getMonkey( const string &name ); method returns a Monkey*. The implementation will look a lot like this:

Monkey * MonkeyHouse::getMonkey( const string &name ) {
   return myMonkeys[ name ];
}

But remember, myMonkeys[name] is a const Monkey*! We need to change the method signature to:

const Monkey * GetMonkey( const string &name );

Now call me crazy, but just for this toy example, that's an AWFUL lot of work to add some safety. Imagine having to do this in a large, 5th generation, production level desktop application! So my plea to all you developers out there, C++ or not, STOP BEING LAZY. Pay attention to your own work. Excersize your right to say "NO! You can't change this value, and NO! I won't change yours." It's only five little letters and a whitespace token. It's not difficult, and I won't feel the need to hunt you down later.

It never ceases to amaze me the drastic impact our choice of datastructures has on application performance, and how little thought many developers seem to give it. I was charged with the task of optimizing a specific feature of our application at work this week involving set logic -- since set logic is so common and well defined, I was nervous that there'd be little improvement to be had short of optimizing how the data in question was physically stored. Much to my horror, I found several blocks of code that did something like this:

void <method_name>( CObArray &aryObjects1, CObArray &aryObjects2) 
{
  int i, j;

  for ( i = aryObjects1.GetSize() - 1; i >= 0; i-- ) 
  {
     CObject * obj1 = aryObjects1.GetAt(i);

     for ( j = aryObjects2.GetSize() - 1; j >= 0; j-- ) 
     {
        CObject * obj2 = aryObjects2.GetAt(j);
        if ( obj1 == obj2 ) 
        {
           // do something
        }
     }
  }
}

So right off the bat I have two major complaints:

1. Who picks arrays to perform set logic? Especially a CObArray -- use a SET CLASS for SET LOGIC, I BEG OF YOU.
2. Why are we looping backwards? There's nothing wrong with it, but it's much more intuitive to start with 0 and work up.

Lets be more concrete though and talk about the specific method I worked on first -- set difference. The method takes 2 CObArray instances, and removes all occurrances of items in the first from the second. The do something block above then, looked like this:

delete obj2;
aryObjects2.RemoveAt( j );

While this seems innocent enough, that CObArray::RemoveAt(int) call just bumped your runtime from a horrendous O( n^2 ) to an even worse O( n^3 )!! Remember, this is an array, not a list - therefore deletion time is O( n )...

My immediate though was to just swap out the datastructure for something better, like a set, but as I found out, you can't always come into production code and start swapping out structures. There were thousands of places in the application that relied on this array being a CObArray instance :-\. So I decided to make use of an intermediate datastructure to optimize the task at hand.

The STL provides a number of template classes implementing various datastructures. I'll show you my re-write first, and then we'll discuss it's subtletees:

struct MyComparator 
{
   bool operator()( CObject* obj1, CObject* obj2 ) 
   {
      return obj1->Compare(obj2) < 0;
   }
}

typedef std::set< CObject*, MyComparator > ObjectSet

// Removes all objects occurring in aryObjects1 from 
// aryObjects2 in O( n * log(n) ) time.
void RemoveAll( CObArray &aryObjects1, 
                CObArray &aryObjects2 ) 
{
   ObjectSet myset;

   for ( int i = 0; i < aryObjects2.GetSize(); ++i ) 
   {
      myset.insert( aryObjects2.GetAt(i) );
   }

   ObjectSet::iterator itr;
   for ( int j = 0; j < aryObjects1.GetSize(); ++j ) 
   {
      itr = myset.find( aryObjects1.GetAt( j ) );

      if ( itr != myset.end() ) {
         delete *itr;
         myset.erase(itr);
      }
   }

   aryObjects2.RemoveAll();
   aryObjects2.SetSize( myset.size() );

   int i = 0;
   for ( itr = myset.begin(); 
         itr != myset.end(); 
         itr++ ) 
   {
      aryObjects2.SetAt( i++, *itr );
   }
}

It works by first creating a set with all the elements from aryObjects2. This takes O(n logn) time. I then iterator aryObjects1, searching for each item in the set I just built. This takes O(logn) per lookup. If I found the item, then I delete it from the set, which is a O(logn) operation as well. The final step is to copy the items from the set back into the target array. Note that I allocate the memory space all at once to avoid having to reallocate and copy the array items each time it grows.

This last point can cause major problems for you as well. I used a technique similar to this one to optimize an AddAll method as well -- the add all had an O( n^3 ) loop to detect duplicates, and then at the end did something like this:

aryObjects1.RemoveAll();

for ( int j = 0; j < aryTemp.GetSize(); j++ ) {
	aryObjects.Add( aryTemp.GetAt(i) );
}

While this looks like a O(n) on the surface, my handy debugger showed me that it was actually "growing" the array one insert at a time -- so for each insert, it allocated new memory space, copied the entire array over, and then inserted the item. That's O(n^2)! By simply realizing that we already knew how big the array was going to be, and statically allocating it up front, we can eliminate an order of magnitude from the runtime (that one's for you, Doug ;))!

So by simply introducing an intermediate datastructure to perform a specific task, you can greatly improve your runtime performance, while not having to recode for a new datastructure.

I recently posted a link to Bjorne Stroustrup's C++ FAQ, in which he points out that the value of:

int i = 2
int j = i++ + i++

is undefined. I decided to throw together a couple little sample problems to see just what it would do. My toy program looks like this:

#include <iostream>

using namespace std;

int main( int argc, char ** argv ) {
	int i = 2;
	int j = <expr1> + <expr2>;

	cout << j << endl;
}

Where expr1 and expr2 are either i++ or ++i. So for instance, when I throw in

int j = i++ + i++

I would expect j to take on a value of 5 -- since i is initially 2, the first i++ would evaluate to 2 and assign a value of 3 to i. The second i++ then evaluates to 3 and assigns a value of 4 to i. The results were, as expected, not what I would expect. The following table summarizes the combination of i++'s and ++i's, what I would evaluate it to in my head, and what actually happened:

Expr 1	Expr 2	Expected j	Actual j	i
++i	i++	6	6	4
i++	++i	6	6	4
i++	i++	5	4	4
++i	++i	7	8	4

As you can see, when we mix ++i and i++, things seem to evaluate as expected, however i++ + i++ and ++i + ++i are incorrect. As B.S. points out in his FAQ, this behavior is due to the fact that the order of evaluation of expressions is undefined. So when we do i++ + i++, there is no garuantee that expressions are evaluated left to right, and there is no garuantee that the ++ operators will be evaluated before the addition operation (even though, interestingly enough, ++ has a higher precendence than +)

Bjarne's answer to this nasty "problem"? Just don't do it. Expressions like this are confusing anyway, and simple enough to avoid.

That's right, a C++ FAQ by Bjarne Stroustrup himself (what did you think BS meant?) I ran across this faq this morning while googling for the forgotten name of the famed designer of C++.

This is easily the most interesting C++ FAQ I've ever come across, with interesting tidbits about why there's both pointers and references and C++ (turns out he only kept pointers in the language to maintain C compatibility), dispelling the commonly taught myth that "friend" access violates encapsulation, why you should stop using macros, and my favorite, "char" is NOT pronounced "KAR" as in "character", the "ch" is pronounced like it is in "cheese".

Definitely worth the read, even for you veteran C++'ers