The C++ Standard Library by Nicolai M. Josuttis has been the C++ book I referred to the most in the past few years. It was time I made a plug for it, it can be seen here.
Monthly Archives: October 2010
Book: .Net Book Zero
My long search for a good introductory C# book ended with .Net Book Zero by the legendary Charles Petzold. My review of the book can be seen here.
Orientation
Orientation is a fundamental concept in computational geometry. It is the most important predicate too. Calculating the orientation of a triangle (2D), tetrahedron (3D) or pentachoron (4D) reduces to the calculation of the sign of a determinant. The following code is in C++, but can easily be adapted to any language.
First, it is helpful to define an orientation type:
enum ORIENT_TYPE
{
ORIENT_NEG = -1,
ORIENT_ZERO = +0,
ORIENT_POS = +1,
};
ORIENT_ZERO indicates a degeneracy in the simplex. For example, in 2D this means that the 3 points are collinear. This is typically not preferred and symbolic perturbation techniques like Simulation of Simplicity might have to be used to handle such cases.
A helper function to convert a determinant value to orientation:
ORIENT_TYPE detToOrient( const int det )
{
return ( det > 0 ) ? ORIENT_POS : ( ( det < 0 ) ? ORIENT_NEG : ORIENT_ZERO );
}
2D Orientation:
ORIENT_TYPE orientation2
(
const int* p0,
const int* p1,
const int* p2
)
{
// | m00 m01 |
// | m10 m11 |
const int m00 = p1[0] - p0[0];
const int m01 = p1[1] - p0[1];
const int m10 = p2[0] - p0[0];
const int m11 = p2[1] - p0[1];
const int det = ( m00 * m11 ) - ( m10 * m01 );
return detToOrient( det );
}
3D Orientation:
ORIENT_TYPE orientation3
(
const int* p0,
const int* p1,
const int* p2,
const int* p3
)
{
// | m00 m01 m02 |
// | m10 m11 m12 |
// | m20 m21 m22 |
const int m00 = p1[0] - p0[0];
const int m01 = p1[1] - p0[1];
const int m02 = p1[2] - p0[2];
const int m10 = p2[0] - p0[0];
const int m11 = p2[1] - p0[1];
const int m12 = p2[2] - p0[2];
const int m20 = p3[0] - p0[0];
const int m21 = p3[1] - p0[1];
const int m22 = p3[2] - p0[2];
const int m00Det = ( m11 * m22 ) - ( m21 * m12 );
const int m01Det = ( m10 * m22 ) - ( m20 * m12 );
const int m02Det = ( m10 * m21 ) - ( m20 * m11 );
const int det = ( m00 * m00Det ) - ( m01 * m01Det ) + ( m02 * m02Det );
return detToOrient( det );
}
4D Orientation:
ORIENT_TYPE orientation4
(
const int* p0,
const int* p1,
const int* p2,
const int* p3,
const int* p4
)
{
// | m00 m01 m02 m03 |
// | m10 m11 m12 m13 |
// | m20 m21 m22 m23 |
// | m30 m31 m32 m33 |
const int m00 = p1[0] - p0[0];
const int m01 = p2[0] - p0[0];
const int m02 = p3[0] - p0[0];
const int m03 = p4[0] - p0[0];
const int m10 = p1[1] - p0[1];
const int m11 = p2[1] - p0[1];
const int m12 = p3[1] - p0[1];
const int m13 = p4[1] - p0[1];
const int m20 = p1[2] - p0[2];
const int m21 = p2[2] - p0[2];
const int m22 = p3[2] - p0[2];
const int m23 = p4[2] - p0[2];
const int m30 = p1[3] - p0[3];
const int m31 = p2[3] - p0[3];
const int m32 = p3[3] - p0[3];
const int m33 = p4[3] - p0[3];
const int m00m11Det = ( m22 * m33 ) - ( m32 * m23 );
const int m00m12Det = ( m21 * m33 ) - ( m31 * m23 );
const int m00m13Det = ( m21 * m32 ) - ( m31 * m22 );
const int m01m10Det = m00m11Det;
const int m01m12Det = ( m20 * m33 ) - ( m30 * m23 );
const int m01m13Det = ( m20 * m32 ) - ( m30 * m22 );
const int m02m10Det = m00m12Det;
const int m02m11Det = m01m12Det;
const int m02m13Det = ( m20 * m31 ) - ( m30 * m21 );
const int m03m10Det = m00m13Det;
const int m03m11Det = m01m13Det;
const int m03m12Det = m02m13Det;
const int m00Det =
+ ( m11 * m00m11Det )
- ( m12 * m00m12Det )
+ ( m13 * m00m13Det );
const int m01Det =
+ ( m10 * m01m10Det )
- ( m12 * m01m12Det )
+ ( m13 * m01m13Det );
const int m02Det =
+ ( m10 * m02m10Det )
- ( m11 * m02m11Det )
+ ( m13 * m02m13Det );
const int m03Det =
+ ( m10 * m03m10Det )
- ( m11 * m03m11Det )
+ ( m12 * m03m12Det );
const int det =
+ ( m00 * m00Det )
- ( m01 * m01Det )
+ ( m02 * m02Det )
- ( m03 * m03Det );
return detToOrient( det );
}
Doxygen: Generating CHM
Compressed HTML (CHM) files are a convenient medium to view and browse through documentation on Windows. Doxygen can produce documentation of source code in the CHM format. Here is how to configure Doxywizard to produce CHM files:
- In Wizard → Output, choose the Output Format as Prepare for compressed HTML (.chm). Configure the rest of the Wizard settings as usual.
- In Expert → HTML, provide the CHM filename you want in the CHM_FILE field and the full path of the Microsoft HTML Help Compiler (hhc.exe) tool in the HHC_LOCATION field. This is typically
C:\Program Files (x86)\HTML Help Workshop\hhc.exe
- In the Run section choose Run Doxygen and a freshly compressed copy of your CHM documentation will be prepared for you by Doxygen!
Doxygen
Doxygen is a useful tool to automatically generate documentation for code. It can produce beautiful documentation if the code comments are written in its custom format. Thankfully, even if this is not the case it can still produce documentation that can be useful for understanding a mass (or mess) of code written by someone else.
Doxygen uses a configuration file, typically named doxygen, to generate documentation. Doxygen ships with a GUI tool named Doxywizard that makes it easy to create a configuration file and generate documentation.
As an example, assume the code in a project has the following directory structure:
C:
+---Foobar
+---Code
+---Docs
That is the project root directory is C:\Foobar, source code directory is C:\Foobar\Code and the documentation produced by Doxygen will reside in C:\Foobar\Docs.
To produce this, fill the fields in Doxywizard as follows:
In the Run tab choose Run Doxygen to generate the documentation. It will be produced in the format you chose: HTML, CHM, XML, RTF or many others.
It is a good idea to save the configuration to a file named doxygen in the project directory. Do this in the Doxywizard by choosing File → Save As. By having a configuration file around, the documentation can be updated whenever the code in the project changes. This can be done directly by invoking doxygen.exe in that directory or can be automatically invoked by your build tool.
C++: One Definition Rule (ODR)
Every C++ programmer is aware of the One Definition Rule (ODR), but in a vague sense: “Only one definition of something is allowed in something.” I was surprised to learn that the ODR stumps not just us mortals, but the architects of C++ itself. More than a decade after the birth of C++, in a 1995 C++ Standards meeting it took the architects 2 entire days to put down this rule to paper!
Attempt 1
Here is a simple breakdown of the ODR:
- In a program, there can be only one definition of:
- (Non-inline) Function
- Variable
- In a translation unit (a .cpp file), there can be only one definition of:
- Class
Attempt 2
Alternatively, we can flip around the definition of the rule and try to understand it from the point-of-view of the entities:
- Class: There can be only one definition of a class in a translation unit.
- Note: This means that the same class definition can appear in several translation units. In fact, this is what happens when the header file of a class in included in several source files.
- (Non-inline) Function or (global) Variable: There can be only one definition of such a function or variable in the entire program.
- When this rule is broken, a redefinition error is produced by the linker.
References
- Standard for C++ Programming Language: The ODR section is arcane and runs to 3 pages!
- Section 9.2.3 in The C++ Programming Language by Stroustrup: Surprisingly, the C++ creator himself only describes the ODR with relation to classes, clearly skipping (or assuming) it for functions and variables!
- Articles Diary of an Observer by Francis Glassborow and The Casting Vote by Sean A. Corfield in Issue 9 (August 1995) of Overload magazine: C++ architects describe in entertaining detail how nailing the ODR definition took them 2 full days at the C++ standards meeting.
Visual Studio: Intellisense Icons
No matter what programming language you program in Visual Studio, you will be familiar with the Intellisense icons that Visual Studio uses for the different types of entities in your code. The icons used by Intellisense are also called Babel Icons and are available in a Visual Studio installation, whether to pique your curiosity or for use in your own programs.
These icons are stored in the Visual Studio Image Library. This is a file named VS2010ImageLibrary.zip that can be found in C:\Program Files (x86)\Microsoft Visual Studio 10.0\Common7\VS2010ImageLibrary\1033\. Unzip this file and navigate to the directory VS2010ImageLibrary\Objects\bmp_format\Office and VS. The Intellisense icons are the ones named VSObject_*.bmp. I found a staggering 156 different Intellisense icons on my Visual Studio 2010 installation!
I have listed the most common Intellisense icons for Visual C++ here.
C++: Function Pointers
There are 2 kinds of pointers to class functions in C++:
- Pointer to static function of a class
- Pointer to (non-static) function of a class
Pointer to Static Function of a Class
For most practical purposes, the static function of a class behaves like a C-style function defined at the same scope of the class and which can be accessed by invoking the name of the class. Hence, a pointer to a static function is defined, assigned and invoked just like a C-style function pointer.
It is useful to first define a type of the pointer required:
typedef void ( *StaticFunctionPointer ) ( int );
The above type definition can be understood by reading outwards starting from the middle. It reads as “The type FooStaticFunctionPointer is a pointer to a function that takes an integer parameter and returns void”. So, we have defined a pointer type that can point to any static function of any class with the above described signature.
After this, we can define a variable of the above type and initialize it by assigning the memory address of a function that matches the above signature:
class Foo
{
public:
static void StaticFunc( int val )
{}
};
StaticFunctionPointer statFp = &Foo::StaticFunc;
To invoke the function pointed to by this function pointer, use the indirection operator on the pointer:
(*statFp)( 10 );
Pointer to (Non-Static) Function of a Class
This pointer is a bit different in the invocation, but the definition and assignment is the same as that of static function. Note that this pointer will finally be invoked on a class object (and not a class).
The type definition and assignment of this function pointer is similar to that of static function pointer:
class Foo
{
public:
void Func( int val )
{}
};
typedef void ( Foo::* FooFunctionPointer ) ( int );
FooFunctionPointer fp = &Foo::Func;
To invoke a non-static function pointer, we need an object of the class which was used to initialize the function pointer. The invocation looks a bit more involved:
Foo foo; (foo.*fp)( 30 );
Sample Code
Finally, here is code that illustrates both kinds of C++ function pointers:
#include <iostream>
using namespace std;
class Foo
{
public:
// *** Static Functions
static void StaticFunc0( int val )
{
cout << __FUNCTION__ << ": Value is " << val << endl;
}
static void StaticFunc1( int val )
{
cout << __FUNCTION__ << ": Value is " << val << endl;
}
// *** (Non-Static) Functions
void Func0( int val )
{
cout << __FUNCTION__ << ": Value is " << val << endl;
}
void Func1( int val )
{
cout << __FUNCTION__ << ": Value is " << val << endl;
}
};
// Pointer to a static function of a class
// The function has an integer parameter and returns void
typedef void ( *FooStaticFunctionPointer ) ( int );
// Pointer to a (non-static) function of a class
// The function has an integer parameter and returns void
typedef void ( Foo::* FooFunctionPointer ) ( int );
int main()
{
// *** Static Function Pointer
// Initialize the pointer
FooStaticFunctionPointer statFp0 = &Foo::StaticFunc0;
// Invoke the function pointed by pointer passing 10 as parameter
(*statFp0)( 10 );
// Same as above, but different static function
FooStaticFunctionPointer statFp1 = &Foo::StaticFunc1;
(*statFp1)( 20 );
// *** (Non-Static) Function Pointer
Foo foo; // Object of Foo class
// Initialize the pointer to a function of Foo class
FooFunctionPointer fp0 = &Foo::Func0;
// Invoke the function pointed by pointer passing 30 as parameter
(foo.*fp0)( 30 );
// Same as above, but different function
FooFunctionPointer fp1 = &Foo::Func1;
(foo.*fp1)( 40 );
return 0;
}
C++: <iosfwd>
C++ header files should introduce as few definitions as possible. This is why it is advisable to use forward declarations of the types needed in a header file. This leads to less coupling and faster compilation times.
To help with this, the C++ standard provides the <iosfwd> header file for use in header files. This header file contains the forward declarations of the definitions from other input-output header files like <iostream>. <iosfwd> should only be used in header files, since it is not really useful to include it in a source file (.cpp) that needs the definitions.
The definitions whose forward declarations that <iosfwd> provides can be seen here. I find it easier to know what are the standard header files whose definitions <iosfwd> provides for. These are:
<cstdio> <cstdlib> <cwchar> <fstream> <iomanip> <ios> <iostream> <istream> <ostream> <sstream> <streambuf>
C++: Return Value versus Output Parameter
The C++ programmer has to be constantly aware of the performance of the code he is writing. One conundrum that arises often is with the output of a function. If this output is an object of substantial size, is it better to return it as the return value or as an output parameter?
Question: Which of these functions is faster?
Foo Function1(); void Function2( Foo& );
Answer: It depends. Typically it is Function2, sometimes both are comparable.
- Function1 looks elegant, both for a programmer and for a mathematician. However, it breaks down as soon as one wants to return multiple values from a function. One could use modern C++ constructs like pair or tuple, but that is extra machinery.
- Function2 does not look as elegant as Function1. One needs to be careful here to pass the output parameter as a reference (or pointer) parameter. However, this format can handle multiple output parameters easily.
- Returning built-in types (like integer) or tiny objects are easy for the C++ compiler to optimize. They should be equally fast with both Function1 and Function2.
- Function1 typically needs to construct the object it is returning. Depending on the class of the object, this might take substantial amount of time. After construction, it may need to modify or fill the object with data.
Foo Function1() { Foo foo; // Construction cost foo.fillSomething(); return foo; } - Function2 assumes that the parameter object is already created. It only modifies or fills the object with data.
void Function1( Foo& foo) { foo.fillSomething(); return; } - The performance also depends on what is happening in the caller. The caller might be assigning the return value to initialize a new object or to an already existing object.
int main() { // New object Foo f1 = Function1(); Foo f2; Function2( f2 ); // Existing object Foo f; while ( x ) { // Do something f = Function1(); // Do something f.clear(); Function2( f ); } return 0; } - Function1 involves one object creation inside the function and one copy of this object to the destination object. That looks very expensive! However, all modern C++ compilers perform Return Value Optimization (RVO) that eliminates the expensive copy operation.
- Note that RVO cannot always be applied by the compiler. When this happens, Function1 becomes all the more expensive.
I conducted a simple test using the STL vector as the return object. The code used for this can be seen here. The code was compiled using the Visual C++ 2010 compiler (16.00.30319.01) in Release mode.
New object ... Function1: 1.753 Function2: 1.615 Existing object ... Function1: 1.671 Function2: 1.035
The results clearly show that output parameter is always faster. When assigning to a new object, the speed difference is negligible. However, when reusing an existing object, the speed difference is substantial!
