The Singleton Design Pattern

One of the most famous design patterns is Singleton: http://en.wikipedia.org/wiki/Singleton_pattern

Sample Code

Sample code should be written in the style of production code, because many times sample code becomes production code.

Reference: “C++ Design” by Steve Weinrich, unpublished manuscript.

Header Files

When you publish a header file, anything that you #include into that header file is a part of your interface. “C++ Design” by Steve Weinrich, unpublished manuscript.

Indentation

Indent case statements one space. Indent other statements three spaces.“C++ Design” by Steve Weinrich, unpublished manuscript.

Indentation

Indent public/private/protected access specifiers one space. Indent member variables 3 spaces. “C++ Design” by Steve Weinrich, unpublished manuscript.

Library and Implementation

There are differences between library code and implementation code. Application programmers do not care about creating reusable code. “C++ Design” by Steve Weinrich, unpublished manuscript.

Classes

A class should do only one thing, and one thing only. And do it well.“C++ Design” by Steve Weinrich, unpublished manuscript.

Member Variables

Start member variable names with an ‘m’. “C++ Design” by Steve Weinrich, unpublished manuscript.

Underscores in Names

Do not use underscores in type names and object names.“C++ Design” by Steve Weinrich, unpublished manuscript.

Member Functions

Put member functions in alphabetical order. “C++ Design” by Steve Weinrich, unpublished manuscript.

Member Variables

Put member variables in alphabetical order. “C++ Design” by Steve Weinrich unpublished manuscript.

Mapping C++ Feature to OOD Feature

Mapping C++ Feature to OOD Feature

common base class - common traits
public inheritance - isa
private inheritance -implemented in terms of
layering (aka composition) - has-a or implemented in terms of
pure virtual function - only interface inherited
simple virtual function - interface and default implementation inherited
nonvirtual function - interface and mandatory implementation inherited

Effective C++: 55 Specific Ways to Improve Your Programs and Designs (3rd Edition) by Scott Meyer. Addison-Wesley, 2005.

Complex Type Declarations

The following declaration:typedef int(*(* (func()) )[]); means: func is a function returning a pointer to an array of pointers to integers.

I first saw the rule in the paper:

"This Simple "Clockwise" Rule Helps Decipher Complex Declarations", by Andrew Binstock in "The C User's Group Newsletter", June 1987 issue.

The only reference I found to it on the Web was: http://www.dbforums.com/archive/index.php/t-1097162.html

The rule applies only when C constructs are used in a declaration and not C++.

Basically, you start with the symbol you are defining, go to the right in a clockwise manner. Read off what you see. You need to obey any parentheses.

Deques

Deque stands for Double Ended Queue.

Deques

Inserting at the beginning or end of a deque invalidates all of its iterators.

Deques

Inserting at the beginning or end of a deque does not invalidate any of the references and pointers to the deque's items.

Kinds of STL Containers

The two kinds of standard containers are sequence and associative.

Sequence Containers

The sequence containers are: basic_string, string, wstring, deque, list, and vector.

Associative Containers

The associative containers are: map, multimap, set, and muliset.

Sets and Maps

Inserts, deletes, and finds on set and map are of logarithmic complexity.

Container Adapters

All of the following are container adapters: priority_queue, queue, and stack.

Equivalence

Equivalence between two objects is different than equality and is defined as (!(A<B) &!(B&<A)).

STL Containers

Every STL container contains all of the following typedefs: allocator_type, const_iterator, const_pointer, const_reference, difference_type, iterator, pointer, reference, size_type, and value_type.

STL Containers

The following member functions belong to all STL containers: begin(), clear(), empty(), end(), erase(), get_allocator(), max_size(), operator=(), rbegin(), rend(), size(), and swap().

STL Ranges

Ranges in STL are or Half-Open, [ begin() , end() )

STL Containers

The following member functions are optional for STL containers: at(), back(), front(), operator[], pop_back(), pop_front(), push_back(), push_front().

STL Sequence Containers

All STL sequence containers contain the following member functions: assign(), insert().

STL Associative Containers

All STL associative containers contain the following member functions: count(), equal_range(),erase(), find(), insert(), key_comp(), lower_bound(), value_comp(), upper_bound().

The list Container

The list container does not support at() and operator[]().

If you need these operators, use vector instead.

Exceptions

The erase(), pop_back(), and pop_front() member functions must not throw an exceptions.

The list Container

The following are list member functions: merge(), remove(), remove_if(), resize(), reverse(), sort(), splice(), and unique().

The map Container

The map container contains the operator[]() member function, but the multimap container doesn't.

The priority_queue Container

The priority_queue container has the top() member function and the queue container does not have the top() member function.

top() gives you the highest priority item in the priority queue.

priority_queue

The template parameters for priority_queue are T, Container, and Compare.

priority_queue

The default Container for the priority_queue is vector.

queue

The default Container for queue is deque.

The template parameters for set and multiset are: Key, Compare, and Allocator.

stack

The default Container for stack is deque.

string

string is just a typedef for basic_string<char>.

basic_string

The template parameters for basic_string are: charT, Traits, and Alloc.

npos

basic_string::npos is defined as follows: static const size_type npos = -1;

Vector

Elements (except of type bool) of a vector are store contigously, so you can pass a pointer to the first element of a vector to a C function as an array.

Categories of Iterators

There are five categories of iterators: Input, Output, Forward, Bidirectional and Random access.

Set Algorithms

The following functions are set algorithms: includes(), set_difference(), set_intersection(), set_union(), and set_symmetric_difference().


The complexity of these algorithms is O(n).

Heap Algorithms

The following functions are heap algorithms: make_heap(), pop_heap(), push_heap(), sort_heap().

Heap Algorithms

The complexity of make_heap() is O(n); The complexity of pop_heap() and push_heap() is O(logn); The complexity of sort_heap() is O(nlogn).

Permutation Algorithms

The two permutation functions are next_permutation() and prev_permutation(): They have the complexity of O(n).

Sorting Algorithms

nth_element() has the complexity in the average case of O(n).

Sorting Algorithms

partial_sort(), partial_sort_copy(), partition(), and stable_partition() have the complexity of O(nlogk), where k is the number of items to sort.

These will be the first k smallest items in the set (of size n).

Sorting Algorithms

sort() and stable_sort() usually have the complexity of O(nlogn).

Vector Algorithms

vector() has the complexity of O(n); capacity() has the complexity of O(1); reserve() has the complexity of O(n); resize() has the complexity of O(n).

List Algorithms

The following are list functions: size(), merge(), remove(), remove_if(), reverse() and sort(). size() is allowed to have the complexity of either o(1) or o(n).

List Algorithms

merge() has the complexity of O(n); remove() has the complexity of O(n); remove_if() has the complexity of O(n); reverse() has the complexity of O(n); sort() has the complexity of O(nlogn).

structs and classes

struct A:public B{A();C();}; is functionally equivalent to class A:public B{public:A();C();};

Note that the public in struct is unnecessary.

Functors

In STL, 'function objects' are called functors.

bind2nd

The value of bind2nd(std::plus<int>(), 99)(1) is 100.

bind1st

The value of bind1st(std::plus<int>(), 99)(1) is 100.

binary_function and unary_function

The classes binary_function and unary_function are base class templates of all functor classes. Theyare they defined in .

binary_function

The binary_function class template defines the following typedefs: first_argument_type, second_argument_type and result_type.

Functors

Adapters convert a pointer to a function or member function and return a functor.

Adapters

Non-member and static member functions use the ptr_fun adapter.

Non-static member with objects use the mem_fun_ref adapter.

Non-static member with pointer to objects mem_fun.

Binder Templates

The names of the two binder templates are bind1st and bind2nd.

Functors

All of the following are STL functors: divides, logical_and, logical_or, minus, modulus, multiplies, plus, logical_not, negate, not1, not2.

Functors

All of the following are STL functors: equal_to, greater, greater_equal, less, less_equal, not_equal.

The 'less' Functor

The default comparison functor for associatve containers is 'less'.

The 'less' Functor

The following is the declaration for the less functor:

   template <typename T>
   struct less : binary_function<T, T, bool> {
      bool operator()(const T& x, const T& y) const;
   };

Binders

Standard algorithms typically work with one argument functors.

You can use a binder (bind1st, bind2nd) to convert a function with two arguments into a one argument functor.

Adapters

The standard library does not provide adapters for functions of two arguments.

This feature was added to Boost. Boost was created to help make up some features missing in the STL.

unary_function

The unary_function class template defines the following: typedefs: argument_type and result_type.

Boost

Boost (boost/bind.hpp) let's you bind more then one argument at a time.

Boost

Boost (boost/mem_fn.hpp) let's you adapt functions with more then one argument.

Boost

Boost (boost/compose.hpp) let's you combine multiple multiple functors into a single functor.

Allocators

An STL allocator is an abstraction of the two operators new and delete.

Exception Specifications

The prototype: allocator() throw(); means the allocator constructor does not throw exceptions.

The exception specification (whose use is typically discouraged by the C++ community) says that the function does not intentionally throw any exceptions. If an exception is inadvertently thrown, the function unexpected() would be called. This function can be set by <unexpected.h>::set_unexpected(). If the default one is called, then the function terminate() is called.

This function can be set by <terminate.h>::set_terminate(). If the default one is called, then the function abort() is called. If the user-defined terminate() does not call abort(), abort() will be called automatically at the end of the user-defined terminate function.

Allocators

An object of type allocator<int> is equal to an object of type allocator.

The allocator's operator == and and operator != are defined so that allocators of different template parameters are considered to be equal.

Allocators

All of the following are typedefs of the allocator template: const_pointer, const_reference, difference_type, pointer, reference, size_type, value_type.

Allocators

allocator<T>::destroy(pointer p) calls reinterpret_cast<T*>(p)->~T().

Global Operator New

allocate(size_type n, allocator::hint = 0) calls the global operator new.

Placement New

construct(pointer p, const T& val) calls the global placement new.

Template Specialization

allocator<void> is a template specialization that declares fewer functions than allocator<T>. It does not declare the functions allocate() or construct().

Allocators

An allocator object can be copied.

The Address Function

The name of the function that when given a reference to an object, returns a pointer to the object is address.

copy

Given:vector<int> v;copy(v.begin(), v.end(), cout);

For the above statement to work, there needs to be ostream_iterator<int>() wrapped around the cout.

copy() needs the third argument to be an output iterator. cout is a stream, and ostream_iterator<int>() returns an output iterator that accepts integers via operator=() and translates them into calls to operator>>().

copy

Given: vector v1, v2; v1.size() == v2.size(), and copy(v1.begin(), v1.end(), v2.begin());

The above statement works, without needing an ostream_iterator() wrapped around the v2.

Since v2.begin() is already an iterator, ostream_iterator() is not used here.

Typical bugs with the above copy() include:
1) Not having enough space available in v2; and
2) Trying to use v2.end() as the third argument, in an attempt to append the v1 data to the v2 vector.

Note that v2.end() points 1 item past the data part of v2, so it is uninitialized memory.

Note also that pointers are also iterators, so the following code is also valid:

int int_array1[5] = {1,2,3,4,5}, int_array2[5];
int *p_int_array1 = &int_array1[0];
int *p_int_array2 = &int_array2[0];

copy(p_int_array1, p_int_array1+sizeof(int_array1), p_int_array2);
vector<int> vec;
vec.reserve(5);
copy(p_int_array1, p_int_array1+sizeof(int_array1), vec.begin());

Note that p_int_array1+sizeof(int_array1) points one item past the data in int_array1, which is similar to vec.end();

Also note (see below), when inserter() is used, vec.end() is not a problem as the third argument to copy().

back_inserter

Given:

ifstream myInputFileStream( "input_file.txt" );
vector<string> v;
copy(istream_iterator<string>( myInputFileStream ),istream_iterator<string>(),v);

For the above statement to work, there needs to be a back_inserter() wrapped around the v.

back_inserter() returns an iterator, that calls push_back() on the vector v for each call to its operator=() function.

copy

Say you want to insert from one vector v1 into another vector v2 starting at location offset 2 of v2. You could use the following function call:copy(v1.begin(), v1.end(), inserter(v2, v2.begin()+2);

You use inserter() because your input is vector and an iterator pointing where you want to insert() within that vector. If you want to insert at the end of vector v2, the third argument would be back_inserter(v2), which calls v2.push_back(). You can't use front_inserter(), because that calls v2.push_front(), which does not exist for vectors.

end-of-stream (eos)

Given:

vector<int> ints;
copy(istream_iterator<int,char>(cin),
istream_iterator<int,char>(),
inserter(ints, ints.begin()));

This copies any ints from standard input to the vector ints. The name of the character that ends this stream is end-of-stream (eos), also known as end-of-file.

The keystroke to generate this on Unix, and later versions of Windows is ctrl-d. On MSDOS it was ctrl-z. Note that when you call <stdio.h>::getc() on the EOS, it returns the constant EOF (which is typically -1, but is implementation dependent).

istreambuf_iterator

The following call is about 40% faster than the next:

copy(istreambuf_iterator<string>( myInputFileStream ),
     istreambuf_iterator<string>(),
     back_inserter(v));

copy(istream_iterator<string>( myInputFileStream ),
     istream_iterator<string>(),
     back_inserter(v));

The reason why it is faster, is that it does not do a lot of checking, and it also uses the rdbuf() member function directly, dealing with characters of type char or wchar_t.

istream_iterator<> uses operator>>().

ostreambuf_iterator

You can pass an ostreambuf_iterator to any algorithm that accepts an output iterator.

back_inserter and front_inserter

back_inserter() calls push_back(), front_inserter() calls push_front(). You cannot call front_inserter() on a vector, because a vector does not support push_front().

reverse_iterator

If you have a vector with numbers 0 through 9 in it, and a vector::reverse_iterator ri; pointing to the number 5, vectoriterator ri.base() is pointing 6.

Many STL algorithms will not take a reverse_iterator as an argument, so you have to convert it to an iterator. To do this you must increment it then convert it using the base() member

function or convert it using the base() member function, then decrement the result.

istreambuf_iterator

When you create an istreambuf_iterator with its default constructor, it becomes equal to the special end-of-stream iterator.

All end-of-stream iterators are equal, and not equal to non-end-of-stream iterators.

Overloaded Template

The following is an example of an Overloaded Template:
    template <typename T> T f(T &a);
    template <typename T> T f(T *a);

An Overloaded Template is where one template declaration is overloading another template declaration.

Explicit Specialization

The following is an example of 'Explicit Specialization':
    template <typename T> T f(T &a);
    template <> int f(int &a);

In this case, you are saying how you want the function to behave when T is int.

Explicit Instantiation

The following is an example of 'Explicit Instantiation':
    template <typename T> T f(T &a);
    template <> f<int>(int &a);

The second declaration creates an instance of the function with 'int' as the template parameter.

Implicit Instantiation

The following is an example of 'Implicit Instantiation':
    template <typename T> T f(T &a) {return a*a;}
    int a = 1;
    int b=f(a);

When the compiler sees f(a) with f being a template, and a being an int, the compiler is able to deduce the template parameter to be int. The compiler instantiates the template automatically to f<int>. If the statement was 'int b=f<int>(a);' then this would be an example of explicit instantiation.

Explicit Specialization and Explicit Instantiation

The following does not compile:
    template <typename T> T f(T &a);
    template <> int f(int &a);
    template <> f<int>(int &a);
    int a = 1;
    int b=f(a);

The standard says it is not permitted to have a function with Explicit Specialization and Explicit Instantiation in the same compilation unit. Otherwise,

the function to use would be ambiguous for the compiler.

Template Compilation

The following program compiles:
    template <typename T> T f(T &a) {abcd;}
    int main() {return 0;}

This is because the template body is not compiled until it is instantiated. If it is not used in a compilation unit, it will not be instantiated. Note

that this is a typical latent error. The error could be in the code for years before it shows up as a compile error.

Non-template Function overriding a Template Function

A non-template function can override a template function with a compatible signature.

Template typename

The following are functionally equivalent:
    template <typename T> T f(T &a);
    template <class T> T f(T &a);

'typename' was added to the standard to make the declarations less confusing. 'typename' is the preferred keyword to use.

Vectors of Vectors

The following does not compile:
    #include <vector>
    std::vector<std::vector<int>> vectorOfVectorsOfInts;

This is because there is no space between the ">>". ">>" looks like the stream extraction operator to the compiler. In the next version of

C++ tentatively called C++09), no space between the ">"s is supposed to be allowed.

Template Value Parameters

The following compiles:
    template <int returnCode> int func() {return returnCode;}
    int main() {return func<5>();}

Template parameters can include both types and values.

In this case, the template parameter specification include only a value and no types.

Class Size

class A {}; is 1 byte on Solaris.

The size needs to be at least one byte, so that a reference can be declared using an object of the class. For example: ...; A a; A& ra = &a; ... This is the same value given in Microsoft

C++;

Note that the size is still one even when the 'struct' keyword is used instead of the 'class' keyword. Also note, in C, the size of an empty struct is 0 and not 1 as in C++. This is

because there are no references in C.

Class Size

class B {}; is 1 byte on Solaris.

Class Size

class AC : public A {}; is 1 byte on Solaris.

Data is empty, but the object still needs one byte.

Class Size

class ABC : public A, B {}; is 1 byte on Solaris.

Class Size

class VAC : public virtual A {}; is 4 bytes on Solaris.

This comes from the vptr (Virtual Table Pointer) that is needed to point to the vtable (Virtual Table). The compiler needs to allocate them for virtual functions and virtual inheritance.

Class Size

class VABC : public virtual A, virtual B {}; is 4 bytes on Solaris.

Class Size

class IA {public: int i;}; is 4 bytes on Solaris.

This is an example of POD (Plain Old Data). There is nothing funny added to the structure. It is compatible with C. It can be sent across the wires between machines without worrying about

vptrs. You may still have to worry about endian, alignment, and padding though.

Class Size

class IB {public: int i;}; has 4 bytes on Solaris.

Class Size

class IAC : public IA {public: int i;}; is 8 bytes on Solaris.

An object of type IAC has two integers in it; one from IA, and one from IAC. If you had an object iac of type IAC, you can access the integer in the IA subcomponent with this: iac.IA::i;

Class Size

class IABC : public IA, IB {int i;}; is 12 bytes on Solaris.

There are three integers in this object: one in IA, one in IB, and one in IABC.

Class Size

class IVAC : public virtual IA {int i;}; is 12 bytes on Solaris.

There are two integers and one vptr. Since IA is being used as virtual base for IVAC. It's integer will be shared and not replicated by any of the subclasses. A strange thing with virtual

bases, is that their constructor is called from the most derived subclass. This means if you deepen the class hierachy under a virtual base, the new furthest derived class will be

responsible for properly initializing the virtual base class. This can be a point of instability in the system.

Class Size

class IVABC : public virtual IA, virtual IB {int i;}; is 16 bytes on Solaris.

There are 3 integers (one in each IA, IB and IVABC) plus a virtual pointer.

Class Size

class FA {int f() {return 1;}}; is 1 byte on Solaris.

Non-virtual Functions do not add any size to a class/struct, so from a size point of view, this is an empty structure, which just requires the one byte for reference.

Class Size

class FB {int f() {return 1;}}; is 1 byte on Solaris.

Class Size

class FAC : public FA {int f() {return 1;}}; is 1 byte on Solaris.

Class Size

class FABC : public FA, FB {int f() {return 1;}}; is 1 byte on Solaris.

Class Size

class FVAC : public virtual FA {int f() {return 1;}}; is 4 bytes on Solaris.

The compiler adds a vptr for virtual inheritance.

Class Size

class FVABC : public virtual FA, virtual FB {int f() {return 1;}}; is 4 bytes on Solaris.

Note that size is not added for non-virutual functions.

Class Size

class VFA {virtual int f() {return 1;}}; is 4 bytes on solaris.

A vptr is added to the object if there are any virtual functions declared in it, or if virtual inheritance is use.

Class Size

class VFB {virtual int f() {return 1;}}; is 4 bytes on Solaris.

Class Size

class VFAC : public VFA {virtual int f() {return 1;}}; is 4 bytes on Solaris.

For the vptr, because there is a virtual function declared in the class, and the fact that the derived class and the first base class share the same vptr.

Class Size

class VFABC : public VFA, VFB {virtual int f() {return 1;}}; is 8 bytes on Solaris.

The derived class (VFABC) and the first base class share the same vptr. This is the first 4 bytes. The second 4 bytes come from the vtpr in VFB.

Reference: http://www.openasthra.com/tutorials/c-advanced-tutorial-lesson-1/

Class Size

class VFVAC : public virtual VFA {virtual int f() {return 1;}}; is 4 bytes on Solaris.

Four bytes for the vptr in VFVAC, which handles the virtual inheritance and the virtual function in VFVAC.

Class Size

class VFVABC : public virtual VFA, virtual VFB {virtual int f() {return 1;}}; is 8 bytes on Solaris.

There are two vptrs in VFABC. One to handle the virtual inheritance to VFA and one to handle the virtual inheritance to VFB. An extra vptr for the virtual functions declared in VFABC is not

needed, because the other vptrs can be used for this function.

Class Size

class VFGVABC : public virtual VFA, virtual VFB {virtual int f() {return 1;}int g() {return 2;}}; is 8 bytes on Solaris.

The extra function, does not added any extra size.

Reference: http://www.codesourcery.com/cxx-abi/abi.html#vtable

auto_ptr

auto_ptrs should not be used in STL containers.

The C++ Standard says this should not even compile, but some compilers allow it. An auto_ptr object does not have value semantics, because when you copy it, it changes the source object.

When you store auto_ptrs in STL containers and manipulate them, temporaries are sometimes created. This causes the source auto_ptr to have its pointer set to null, and when the temporary is

deleted, it deletes the object that the auto_ptr points to. The Boost smart pointers are usable in STL containers.

auto_ptr

auto_ptr is defined in #include <memory<.

auto_ptr

One of the goals of auto_ptr is to prevent multiple deletes.

The auto_ptr passes ownership of an underlying pointer around so that only the auto_ptr object that owns the pointer will delete the object.

auto_ptr

When an auto_ptr is copied or assigned, the pointer held in the source auto_ptr is set to NULL.

This is the one of the reasons that the auto_ptr does not have value semantics. By changing the source object on assignments and copies causes strange behavior when temporaries are created.

auto_ptr

The "explicit" in the declaration: explicit auto_ptr(T* p = 0) throw(); means that a pointer to T will not automatically be cast by the compiler to auto_ptr and that an auto_ptr constructor

needs to be explicitly constructed.

You do not want pointers to be automatically converted to auto_ptrs.

auto_ptr

Boost smart pointers were designed to be used in STL containers.

auto_ptr

auto_ptr<T>::get() returns the owned pointer.

auto_ptr

auto_ptr<T>::release() returns the owned pointer, and sets the owned pointer to 0.

auto_ptr

auto_ptr<T>::reset(T* p = 0) deletes the owned pointer (if not equal to p), and then sets the owned pointer to p.

auto_ptr

auto_ptrs cannot be used with arrays.

auto_ptrs only have one contained pointer in them. The boost library has classes that work with arrays.

The following are Boost smart pointer class templates and their corresponding header files:
scoped_ptr <class T> <boost/scoped_ptr.hpp >
scoped_array <class T> <boost/scoped_array.hpp >
shared_ptr <class T> <boost/shared_ptr.hpp >
shared_array <class T> <boost/shared_array.hpp >
weak_ptr <class T> <boost/weak_ptr.hpp >
intrusive_ptr<class T> <boost/intrusive_ptr.hpp>

Reference: http://www.boost.org/libs/smart_ptr/smart_ptr.htm

The Order of the Initialization of Member Variables

Given:
    int g_a;
    class A {public: A(int a) : m_a(a) {} int m_a;};
    class B {public: B(): m_a2(++g_a), m_a1(++g_a) {} A m_a1; A m_a2;};
    int main() {B b; return b.m_a2.m_a;}

The return code of this program is 2.

The order of the initialization of member variables is based on the order of their declaration and not on the order that they are listed in the MIL (Member Initialization List), which is the part of the constructor between the ":" and "{".

The Order that Function Parameters are Evaluated

Given:
    int f(int a1, int a2) {return (10*a1 + a2);}
    int main() {int a=0; return f(++a, ++a);}

The return code of this program is undefined, because the order that function parameters are evaluated is undefined. This order could change from version to version or even compile to compile.

The Comma Operator

The value of the following expression (1235 or 234): (1 + 1,234) is 234. The comma is the comma operator.

It has the lowest precedence, so the "1 + 1" is evaluated first, and then the "234" is evaluated next. The value of an expression with commas, is the value of the last expression separated by a comma.

The Comma Operator

The value of x after the following statements (1 or 2): int x; x = 1, 2; is 1.

Assignment has higher precedence than the comma operator.

Note that the following does not compile: int x = 1, 2; because, in this case, another variable is expected with an "=" sign before the "2".

IO Manipulators

IO Manipulators are declared in #include <iomanip>.

IO Manipulators

The following are IO Manipulators: boolalpha(), noboolalpha(), showbase(), noshowbase(), showpoint(), noshowpoint(), showpos(), noshowpos().

IO Manipulators

The following are IO Manipulators: skipws(), noskipws(), uppercase(), nouppercase(), internal(), left(), right(), dec(), hex() oct(), fixed().

IO Manipulators

The following are IO Manipulators: resetiosflags(), setiosflags(), setbase(), setfill(), setprecision(), setw().

IO Manipulators

IO Manipulators with the following declaration: ios_base& xxx(ios_base&) are used in statements like: std::cout << std::xxx; (i.e. without parentheses) or else they will not compile.

For example:
    cout << hex << 15 << endl;
compiles, but the following doesn't compile:
    cout << hex() << 15 << endl;

IO Manipulators

<iomanip> only needs to be included for IO Manipulators that take arguments when they are used.

For example it is needed for:
    cout << setprecision(4) << 15.12345 << endl;

Liskov Substitution Principle (LSP)

Liskov Substitution Principle (LSP) - An object of a derived type should behave fine when passed to a function that accepts objects of the base type.

References:
Liskov, Barbara; Wing, Jeannette (1993-07-16). Family Values: A Behavioral Notion of Subtyping
http://en.wikipedia.org/wiki/Liskov_substitution_principle

Design by Contract (DbC)

Design by Contract (DbC) -
1. Preconditions should not be strengthened in a subclass, and
2. Postconditions should not be weakened in a subclass, and
3. Invariants should not be weakened in a subclass.

References:
Object-Oriented Software Construction by Bertrand Meyer. Prentice Hall, 2000.
http://en.wikipedia.org/wiki/Design_by_contract

Open/Closed Principle (OCP)

Open/Closed Principle (OCP) - Software entities should be open for extension, but closed for modification.

References:
Object-Oriented Software Construction by Bertrand Meyer. Prentice Hall, 2000.
http://en.wikipedia.org/wiki/Open/closed_principle

Dependency Inversion Principle (DIP)

Dependency Inversion Principle (DIP) - High-level modules should not depend on lower-level modules or vice versa; instead they should both depend on abstractions.

References:
Agile Software Development, Principles, Patterns, and Practices by Robert C. Martin, 2002.
http://en.wikipedia.org/wiki/Dependency_inversion_principle

Single Responsibility Principle (SRP)

Single Responsibility Principle (SRP) - Every object should have a single responsibility.

References:
Structured Analysis and Systems Specification by Tom DeMarco, Yourdon Press Computing Series, 1979.
http://en.wikipedia.org/wiki/Single_responsibility_principle

Interface Segregation Principles (ISP)

Interface Segregation Principles (ISP) - Clients should not be forced to depend on interfaces they do not use.

References:
Object-Oriented Software Construction by Bertrand Meyer. Prentice Hall, 2000.

Reuse/Release Equivalence Principle (REP)

Reuse/Release Equivalence Principle (REP) - The granule of reuse is the granule of release.

References:
Agile Software Development, Principles, Patterns, and Practices by Robert C. Martin, 2002.

The Common Closure Principle (CCP)

The Common Closure Principle (CCP) - Components that change together should be packaged together.

References:
Agile Software Development, Principles, Patterns, and Practices by Robert C. Martin, 2002.

Common Reuse Principle (CRP)

Common Reuse Principle (CRP) - Dependency graphs of packages (Namespaces) should have no cycles.

References:
Agile Software Development, Principles, Patterns, and Practices by Robert C. Martin, 2002.

Acyclic Dependencies Principle (ADP)

Acyclic Dependencies Principle (ADP) - Classes that are used together are packaged together.

References:
Large Scale C++ Software Design by John Lakos. Addison-Wesley, 1996.

Stable Dependencies Principle (DSP)

Stable Dependencies Principle (DSP) - Depend in the direction of stability.

Reference:
Object-Oriented Software Construction (Book/CD-ROM) (2nd Edition) by Bertrand Meyer. Prentice Hall, 2000.

Stable Abstractions Principle (SAP)

Stable Abstractions Principle (SAP) - Abstractness increases with stability.

Reference:
Succeeding with Agile: Software Development Using Scrum by Robert C. Martin, 2002.

Tell, Don't Ask (TDA)

Tell, Don't Ask (TDA) - Objects should tell other objects what to do, rather than Objects asking other objects what they should do.

References:
Smalltalk by Example: The Developer's Guide by A. Sharp. McGraw-Hill, 1997.

Law of Demeter (LoD)

Law of Demeter (LoD) - Only talk to your immediate friends.

References:
Karl J. Lieberherr, and I. Holland, Assuring good style for object-oriented programs. IEEE Software, September 1989, pp 38-48
http://en.wikipedia.org/wiki/Law_of_Demeter

Information Hiding

Information Hiding - If chunk of code doesn't need to know about how a chunk of code does its job, don't make it know it.

References:
"On the Criteria to Be Used in Decomposing Systems Into Modules", Communications of the ACM in December, 1972.
http://en.wikipedia.org/wiki/Information_hiding

Encapsulation

Encapsulation - Bundling code and data together.

References:
"On the Criteria to Be Used in Decomposing Systems Into Modules", Communications of the ACM in December, 1972.

Low Coupling

Low Coupling - Grouped code and data should not be highly interdependent on other groups of code and data.

References:
Stevens, Wayne P., Glenford J. Myers and Larry L. Constantine, Structure Design, IBM Systems Journal, Vol. 13. No. 2. (1974), pp 115-139.
http://en.wikipedia.org/wiki/Coupling

High Cohesion

High Cohesion - Grouped code and data are highly related.

References:
Stevens, Wayne P., Glenford J. Myers and Larry L. Constantine, Structure Design, IBM Systems Journal, Vol. 13. No. 2. (1974), pp 115-139.
http://en.wikipedia.org/wiki/Cohesion

Inversion of Control (IoC)

Inversion of Control (IoC) - 'Don't call us, we'll call you'. Example: Registering callbacks with a framework.

References:
Johnson, Ralph E. and Brian foot, Designing Reusable Classes, Journal of Object-Oriented Programming, June/July 1988, Volume 1, Number 2, pages 22-35.
http://en.wikipedia.org/wiki/Inversion_of_control

Defensive Programming

Defensive Programming - Server/Supplier (not Client) figures out what to do when a precondition is broken.

This is not a principle; it is a method.

References:
Rogers, Lawrence R., rlogin(1): The Untold Story, TECHNICAL REPORT CMU/SEI-98-TR-017 ESC-TR-98-017
http://en.wikipedia.org/wiki/Defensive_programming

Preferred main() Prototype

The preferred function definition fragment is int main() and not int main(void).

Slicing

Given class Base and class Derived derived from Base. f(Base base); would slice a derived object.

dynamic_cast

dynamic_cast uses RTTI (Real Time Type Information) for downcasting.

Constructors

The declaration: Shape s; is not functionally equivalent to: Shape s(); s is an object declaration. s() is a function declaration.

Default Constructors

If B is a class, then if B(int a = 1, int b = 2, int c = 3) is declared in B. Then it is B's default constructor.

Storage Classes

The following are C++'s storage classes: auto, register, static, and extern.

Storage Qualifiers

The following are C++'s storage qualifiers: const, volatile, and mutable.

Conversion Constructors

A conversion constructor takes one argument.

Converstion Operators

A conversion operator does not take any arguments.

Nested Classes versus Local Classes

An example of a nested class is: class C { class D {};}; An example of a Local class is: int f() {class C {}; return 0;}

Equality

(x == x == x) evaluates to true when x is true.

Assuming x = true, (x == x == x) <=>
    ((x == x) == x) <=>
    ((true == true) == true) <=>
    (true == true) <=> true.
Assuming x = false, (x == x == x) <=>
    ((false == false) == false) <=>
    (true == false) <=> false.

Inequality

(x != x != x) evaluates to true when x is true.


Assuming x = true, (x != x != x) <=>
    ((x != x) != x) <=>
    ((true != true) != true) <=>
    (false != true) <=> true.
Assuming x = false, (x != x != x) <=>
    ((false != false) != false) <=>
    (false != false) <=> false.

Inequality

(3 >= 2 >= 1) is equal to true.

(3 >= 2 >= 1) == ((3 >= 2) >= 1) = (1 >= 1) == true.

Inequality

(9 >= 8 >= 7) is equal to false.

(9 >= 8 >= 7) == ((9 >= 8) >= 7) == (1 >= 7) = false.

Pointers to Members

Given the following:

class A
{
 public:
   int i1;
   int i2; 
   int f1()
   {
      return 1;
   }
   int f2()
   {
      return 2;
   }
};

int main()
{
   int A::*pmi = &A::i1;
   int (A::*pmf)();
   A a;
   A *a2 = new A; 
   a.*pmi = 99;
   int *pi = &a.i1;
   *pi = 98;
   pmf = &A::f1;
   return 0;
}

The value of pmi is not equal to the value of pi.

pi is an address. pmi is a structure with several components. The number of components depends on whether the class contains virtual functions or not.

Pointers to Member

Given the following:

class A
{
 public:
   int i1;
   int i2; 
   int f1()
   {
      return 1;
   }
   int f2()
   {
      return 2;
   }
};

int main()
{
   int A::*pmi = &A::i1;
   int (A::*pmf)();
   A a;
   A *a2 = new A; 
   a.*pmi = 99;
   int *pi = &a.i1;
   *pi = 98;
   pmf = &A::f1;
   return 0;
}

The syntax to call f1 through pmf is (a.*pmf)().

Pointers to Members

Given the following:

class A
{
 public:
   int i1;
   int i2; 
   int f1()
   {
      return 1;
   }
   int f2()
   {
      return 2;
   }
};

int main()
{
   int A::*pmi = &A::i1;
   int (A::*pmf)();
   A a;
   A *a2 = new A; 
   a.*pmi = 99;
   int *pi = &a.i1;
   *pi = 98;
   pmf = &A::f1;
   return 0;
}

To use pmi with a2 do a2->*pmi=99;

Pointers to Members

Given the following:

class A
{
 public:
   int i1;
   int i2; 
   int f1()
   {
      return 1;
   }
   int f2()
   {
      return 2;
   }
};

int main()
{
   int A::*pmi = &A::i1;
   int (A::*pmf)();
   A a;
   A *a2 = new A; 
   a.*pmi = 99;
   int *pi = &a.i1;
   *pi = 98;
   pmf = &A::f1;
   return 0;
}

You would use pmf with a2: a2->*pmf().

Pointers to Members

Pointers to member functions need to be used with objects.

Pointers to Members

You can't use (pointer to member) to point to a static class member, because the member will not be associated with an object.

If you are using pointers to static function, then you would use the normal function pointer syntax.

RAII (Resource Acquisition is Initialization)

RAII (Resource Acquisition is Initialization) - Acquire resources in a constructor and release them in the destructor.

Reference: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms

Scope Guard

Scope Guard - Acquire resources in a constructor and release them in destructor only when there is an exception.

Like RAII, except when there is no exception, the resources are not released.

Reference: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms

Shrink-to-fit

Shrink-to-fit - Minimize the capacity of a container just enough to hold existing range: std::vector(v).swap(v);

Reference: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms

Erase-Remove

Erase-Remove - To eliminate elements from an STL container. v.erase(std::remove(v.begin(), v.end(), 99), v.end());

Reference: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms

Handle-Body

Handle-Body - class Body; class Handle {private: Body *d_body;}

Reference: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms

Named Constructor Idiom

Named Constructor Idiom - Make constructor private, and then create static functions that do the construction.

Reference: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms

Construct on First Use Idiom

Construct on First Use Idiom - Fixes the static initialization fiasco. Puts static data in a functions as singletons.

Reference: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms

Named Parameter Idiom

Named Parameter Idiom - Using member functions that have the name of parameters that can be chained together.

Reference: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms

Basic Guarantee

Basic Guarantee - Operations will not leak resources when throwing exceptions.

Reference: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms

Strong Guarantee

Strong Guarantee - Operations succeed or has no effects.

Includes Basic Guarentee.

Reference: http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms

vector<bool>

vector<bool> does not behave like other vectors such as vector<int>.

vector<bool> is template specialization of the vector template class. It was was done to optimize space by using 1 bit per element. It does not contain values with the bool type.

Reference: http://en.wikipedia.org/wiki/Boolean_datatype

vector<> is the Container of Choice

If it is feasible, vector<> should be the container of choice. http://www.cplusplus.com/reference/stl/vector/

Reference: http://www.cplusplus.com/reference/stl/vector/

Member Functions versus Non-member Functions

It is better to use a member function instead of a corresponding non-member function in STL.

The copy_if() Function

There isn't a copy_if function in the STL. The Standardization committee forgot to include it.

The string data() member function

One of the differences between the c_str() and data() member functions is that the data() function may not return a null terminated string where as c_str() will always return a null terminated string.

Using empty() instead of (size() == 0)

It is better to call empty() rather than compare size() to 0 on an STL containter. empty() has a low time complexity guarantee.

Catching Exceptions

The best way to catch an exception is by reference. There is no slicing of exception info.

Rethrowing Exceptions

The best way to rethrow an exception caught by catch(AnException &e) is 'throw;' instead of 'throw e;'

The full information of the exception will be kept, instead of keeping only the info of the derived exception class that caught the exception.

Default cout Number Precision

Without setting the precision with setprecision(...), the number 12345.12345 is printed to cout as 12345.1, 123456.123450, and 1.234512e+4 if nothing, 'fixed', and 'scientific', respectively, were previously inserted into cout.

The default is printing a total 6 digits, if possible. For fixed and scientific, the default number of digits after the decimal point is 6.

Argument Dependent Lookup (ADL)

C++ uses the arguments and the namespace of arguments to look up a function.

This is called Argument Dependent Lookup (ADL), and is also known as Koening's lookup. This process is sometimes reponsible for strange compile errors.

Reference: http://en.wikipedia.org/wiki/Argument_dependent_name_lookup


Here is a short video on an application of ADL:
Video: Using ADL to Stream Out Objects

bitset

bitset<> does not have iterators.

bitset

The Most Significant Bit (MSB) in a bitset<>, is N-1.

bitset

bitset<30> represents 30 bits of information.

bitset

The largest number of bits that can be represented in a bitset is (1 << (sizeof(byte)*sizeof(size_t)) limited by memory.

Eventhough, there is the conversion routine to_long(), that is supposed to convert the bits to an unsigned long, bitset can be used with a lot more bits.

bitset

For bitset: There is a set() function sets every bit.

bitset

For bitset: There is a flip() function flips every bit.

bitset

For bitset: There is a reset() function that clears every bit.

bitset

For bitset: There is a count() function that counts every bit that is set.

bitset

For bitset: there is an any() function that indicates if any bits are set.

bitset

For bitset: there is a none() function that returns true if no bits are set.

bitset

For bitset: there is a test(size_t n) function that returns true if bit n is set.

bitset

The following are member operators of bitset:
   ~
   []
   ==
   !=
   &
   ^
   <<
   >>
   &=
   |=
   ^=
   <<=
   >>=

bitset

For bitset: to_string() returns the bits as a string of ones and zeros.

bitset

For bitset: to_ulong() returns the bits as a unsigned long.

bitset

For bitset: operator[] can be used to see if a bit is set or not.

bitset

For bitset: operator[] can be used to get a reference to one bit.

bitset

For bitset: access to one bit is guaranteed to be in constant time.

bitset

bitset is the only template in the STL that uses a non-type template

Reference: http://www.oopweb.com/CPP/Documents/ThinkingInCpp2/Volume/TicV2.html#_Toc53985793

bitset

For bitset: set(0,1) sets bit 0 to 1.

If the second parameter is 0, then the function sets bit 0 to 0.

bitset

For bitset: set(0) does the same thing as set(0,1). The second parameter has a default value of 1.

bitset

bitset was added to the STL to help the compatibility between C and C++. There is a lot of legacy C Code that used bits, and masks.

Casts

It is better to use static_cast<int>() rather than (int).

Some of the reasons are that static_cast<...>() sticks out and is easier to grep for.

Overloading and Overriding

Overloading is compile time polymorphism. Overriding is runtime polymorphism.

Deleting this

Given the statement: delete this; If the object was a global, static or local object, then it is deleted twice. Once during the call to

"delete this" and once when the object goes out of scope. If the object is created with "new" and is not deleted with "delete", it

will only be deleted once, but this would be another bug.

The main() function calling itself

The following program:int main() {return main();} recursively calls itself until the stack runs out causing a segmentation fault.

Member Initialization Lists

A Member Initializer List (MIL) cannot initialize an array.

Linkage Specifications

All of the following linkage specifications compile:
    extern "C" int f1();
    extern "C" {int f2();}
    extern "C++" int f3();
    extern "C++" {int f4();}

The Enum Hack

The following code compiles:
class myClass
{
public:
static const int MAX = 1024; int x[MAX];
};

const int myClass::MAX;

class myClass
{
public:
enum {MAX = 1024};
int x[MAX];
};

The last class is called the enum hack, because for a while many compilers did not handle the previous class declaration.

C++ Header Files

The following are functionally equivalent:
#include <cstdio>
using namespace std;

#include <stdio.h>

The standard C header files have corresponding C++ versions that prepend "c" to the name, and remove ".h" from the end. The C++ version

puts the symbols in the std namespace. The C++ version is preferred.

The Unnamed Namespace

The following are functionally equivalent:
int static func() {return 0;}
namespace {int func() {return 0;}}

The namespace version is preferred.

Namespaces

The following code compiles:

namespace Galaxy {};
namespace GLX = Galaxy;

The second namespace statement is useful for abbreviating long namespace names.

Magic Numbers

A a magic number is an undocumented number used in a program.

It is better to use a const with a descriptive name, so that it is apparent to maintainers what the number means, and also allows a change in one place to be reflected in several places.

Const Declarations

It is better to use a const declaration than a macro to declare a constant.

In some cases, a macro might be preferable, if memory is a concern.

Pointer Ownership

If a library allocates memory for information returned to a client, the library should also deallocate that memory.

The library may have different compile and link options, and may be using a different heap. This problem happens a lot with Microsoft C++ when one component uses multithreadded DLL options and the other component uses singlethreaded options. The problem shows up during runtime. If everyone uses the same allocator, this is not a problem.

Pointer Ownership

If a client allocates memory for a library to use to return information, the client should deallocate that memory.

Unsafe Functions

The following functions that are unsafe: strcpy() strcat() sprintf().

This is because there is no limit on what is being written to the destination. Instead strncpy(), strncat(), and snprintf() should be used, because you can limit what is being written to the destination, and also guarantee that the string is null terminated. The problem with strncpy(), and strncat() is they do not guarantee the array of characters will be null-terminated.

Unsafe Functions

The function gets() is unsafe, because there is no way to limit the size written to the destination.

Unsafe Functions

The function execve() is safer to use than system(), because with the system() call, an attacker can change the PATH variable, causing an attacker program to run instead of the program passed in the system() call.

The last 'e' in execve() stands for environment. The 'v' means that the command line parameters are passed with a pointer to an array of ascii-zero strings with a zero in the last array element.

Dynamic Dispatching

Dynamic Dispatching - Determining which function to run based on the run-time type of its arguments.

Polymorphism

Polymorphism - Ability of an object to be handled like an object in a super class.

The malloc() Function

The following compiles in C but not in C++:int *i = malloc(sizeof(int));

malloc() returns void*. C++ requires a cast to int*.

Null Pointers

In C++, the prefered way to initialize pointers is with a 0 instead of a NULL.

Reference: http://www.research.att.com/~bs/bs_faq2.html#null

Mixin

mixin - A class not really designed for being an object, but for adding functionality to other classes.

Sometimes you see a NoCopy mixin, that prevents objects from being copied.

STL Functor

STL functor - Objects that override operator().

STL Trait

STL trait - A small policy object used to describe aspects of a type.

Traits are usually collections of typedefs that map template parameter to standard typedef names, for example, value_type.

STL Binder

STL binder - A function taking a function and a value and returning a function object.

STL Adapter

STL adapter - A function taking arguments and producing a function object.

Lvalues

lvalue - An expression referring to an object.

Incomplete Type

incomplete type - A type that allows an object to be copied, but not otherwise used.

Linkage

linkage - Whether a name is visible only inside or also outside its translation unit.

Reference

reference - Another name for an object.

Handle

handle - An object that controls access to another.

Design Pattern

Design Pattern - Reusable design, which describes a context, problem in that context, solution to problem, consequences for using solution. It also provides hints and examples.

Return Value Optimization

return value optimization - Avoidance of creation and destruction of temporaries when a function returns an object by value.

Diamond Inheritance

diamond inheritance - A class is derived from two difference base classes, which in turn are derived from the same base class. The inheritance diagram forms a diamond.

Integral Promotion

integral promotion - When a bool, char short, enumerator, bit field is converted to an int.

Double Dispatch

double dispatch - Selecting a functon based on dynamic type of two operands, aka multi-method.

Partial Specialization

partial specialization - A template used for the subset of template parameters that matches a specialization pattern.

Upcast

upcast - Casting from derived type to base type.

Downcast

downcast - Casting from base type to derived type.

Static Type

static type - The type given by a declaration.

Dynamic Type

dynamic type - The type given by an assignment.

Incrementing a bool Variable

You can increment (++) a bool variable.

If the variable is false, it will become true.
If the variable is true , it will stay true.

Decrementing a bool Variable

You cannot decrement (--) a bool variable, but you can subtract 1 from the variable.

Infinite Loop

The following is an infinite loop:

for (unsigned int i = 10; i < 0 ;--i) { printf("%d",i); }

The test part can never be false, because i can never become negative. This problem occurs more often, when the declation of i is farther from the loop.

Default Arguments

A static variable be used as a default argument.

You can even change the default argument's value during runtime, which can change the behavior of a function that is called without all of it's arguments. I don't know if there are any practical uses for this.

Initialization

Five elements are initialized to zero here: {int x[5] = {0};}

The first one is set because you specified the {0} initializer. The other four are set to zero, just because you specified an initializer. If you did not specify an initializer, the array would have random values in it.

Initialization

Only one element is initialized to 7 here: {int y[5] = {7};}

The first is set to seven, the rest are set to zero.

Postfix Increment

const MyClass operator++(int); is a postfix increment operator prototype.

MyClass& operator++(void); is a prefix increment operator prototype.

This can be remembered by the fact that the postfix increment needs to return a temporary value, and not an lvalue to the original object. So, the function return const is the postfix.

Note: postfix, infix, and prefix refer to the location of operator with respect to the operand.

Prefix Increment

The following statements compile:
    int i=0; ++i=2;

The prefix increment returns an lvalue.

Postfix Increment

The following statements do not compile:
    int i=0; i++=2

Return Statements

The value returned by the following function is undefined:

int func() { if (0) return; }

This is a source of some nasty latent errors.

Time Complexity

The complexity of

int f(vector v)
{
   int sum = 0;
   for (int i = 0; i < v.size(); ++i)
   {
      sum+=v[i];
   }
   return sum;
}

is O(n).

Time Complexity

The complexity of:

int f(vector v)
{
   int sum = 0;
   for (int i = 0; i < v.size(); ++i)
   {
      for (int j=0; j < v.size(); ++j)
      {
         sum+=v[i];
      }
   }
   return sum;
}

is O(n**2).

Time Complexity

The complexity of int f(vector v) {return v.size();} is O(1).

Time Complexity

The complexity of

int f(vector v)
{
   int sum = 0;
   for (int i = 0; i < v.size()/2; ++i)
   {
      sum+=v[i];
   }return sum;
}

is O(n).

Note: O(1/2 n) is the same as O(n).

Time Complexity

The complexity of

int f(vector<int> v)
{
   int sum = 0;
   for (int i = 0; i < log(v.size()); ++i)
   {
      sum+=v[i];
   }
   return sum;
}

is O(log n).

Time Complexity

The complexity of 3-SAT Problem is O(2**n).

1. The 3-SAT Problem is a variation of the Satisfiability problem. In the Satisfiability problem, you are given logic expression with N boolean variables, and asked if there is an assignment to these variables that will make the expression return true. The 3-SAT problem restricts the logic expression to or'd clauses of three variables.

2. The Satisfiability is the first algorithm that was proved to be NP-Complete. This is Cook's Theorem.

Reference: Computers and Intractability by M. R. Garey, D. S. Johnson. W. H. Freeman, 1979.

Time Complexity

The complexity of vector<int> quicksort(vector<int> v); is O(nlogn).

Time Complexity

The complexity of void f(vector<int> v) {} is O(1).

Time Complexity

An algorithm is PN-Complete if it can be transformed in polynomial-time to the 3-SAT problem.

Actually, it is PN-Complete if it can be transformed to an NP-Complete problem in polynomial time.

Reference: Computers and Intractability by M. R. Garey, D. S. Johnson. W. H. Freeman, 1979.

The long long Conversion String

The format conversion string "%lld" exists in ANSI C, but not in the C++ standard.

The size prefix "ll" was defined for ANSI C to correspond to the type 'long long', which has a size of at least 64-bits. Many C++ compilers allow "%lld" as a compiler with the corresponding type of 'long long int' as a compiler extension. The C++0x standard is expected to include 'lld" and the "long long" type.

Instantiation Order of Global Objects

The following program my crash:

#include <iostream>
using namespace std;

class MyClass
{
 public:
   MyClass()
   {
      cout << "Entering constructor\n";
   }
};

static MyClass myObject;

int main()
{
   return 0;
}

On SunOs 5.9, it crashes because the order of the instantiation of the global objects are not guaranteed. In this case the cout object is not created before the myObject object. If you add <stdio.h> and call printf() instead of cout, the program does not crash.

ANSI C Fuzzy Language Behavior

In the ANSI C standard, fuzzy language behavior is marked as one of the following, in order from least to most restrictive:
    undefined
   unspecified
   implementation-defined
   locale-specific

C Declarations and Definitions

In C, the difference between a declaration and a definition, is that the definition reserves storage.

In C, a definition is a declaration with a restriction (it reserves storage).

Declarations and Definitions

In C++, all declarations are definitions, while in C, all definitions are declarations.

In C++, a declaration is defined as a definition with restrictions.

The decl-specifiers

These are all or the C++ decl-specifiers:
    storage class specifiers
    type specifiers
    function specifiers

Storage Class Specifiers

The following are C++ storage class specifiers:
    auto
    register
    extern
    static
    mutable

Const

const a type specifier.

The decl-specifiers

The order of decl-specifiers does not matter to C++ compilers.

Template Points of Customization

The following are possible template points of customization:
    Member function
    Nonmember function + ADL (Argument-Dependent Lookup)
    Specialization
    Type lookup

Reference: www.ddj.com/cpp/184401876

Unnamed Namespace

An unnamed namespace can be defined in inside another namespace.

Natural Form of Operators

To use ADL (Argument-Dependent Lookup) on operators, operators must be used in their natural form, e.g. 'a+b' instead of 'a.operator+(b)'.

Partial Specialization

A class template can be partially specialized, but a function template cannot.

Explicit Qualification

ADL (Argument-Dependent Lookup) can be turned off by using explicit qualification.

Functions in Parentheses

ADL (Argument-Dependent Lookup) can be turned off by putting the function name in parentheses.

Reference: www.ddj.com/cpp/184401876

C++ Style Headers

All of the following headers have both the <x.h> and <cx> forms:
    assert.h
    ctype.h
    errno.h
    iso646.h
    float.h
    limits.h
    locale.h
    math.h
    setjmp.h
    signal.h
    stdarg.h
    stddef.h
    stdlib.h
    string.h
    time.h
    wchar.h
    wctype.h

Reference: www.ddj.com/cpp/184403367

Arrays of Functions

C and C++ do not allow arrays of functions. They allow arrays of function pointers.

Operators that cannot be Overloaded

The following operators cannot be overloaded:
    sizeof
    ::
    :?
    .
    .*

String

string is a typedef and not a class.

The virtual Base-specifier

The virtual base classes of the following class are C and E:

class A : B, virtual C, D, virtual E, F {};

The default base-specifier access-specifier is non-virtual.

Template Template Parameters

In the C++98 Standard, a template can take a template as a parameter.

template <template <typename> class T> class A {};

This was not implemented on several compilers. It does not compile on the studio8-v10/SUNWspro/bin/CC, but does compile on gcc.

C/C++ Standards

The following is a list of C/C++ standards in time order from earliest release to latest:
    C89
    C90
    C++98
    C99
    C++03

Reference: http://www.suodenjoki.dk/us/archive/2007/cpp-standard-history.htm

ANSI C

ANSI C is also known as C89.

The ISO ratification of ANSI C

The ISO ratification of ANSI C is also known as C90.

Kernighan and Ritchie (K&R) C

Kernighan and Ritchie (K&R) C was published in 1978.

C++'s Original Name

C++'s original name was C with Classes.

Reference: http://en.wikipedia.org/wiki/C%2B%2B

The First Commerial C++ Compiler

The first C++ compiler became comercially available in 1985.

Base Class Access Specfiers

The private base classes of: class A : B, public C, D, private E, F {}; are B, D, E, and F.

The access specifiers: public, protected, and private are only associated with the immediately next class. This is different than when access specifiers are used with members, where an access modifier affects all members after it in a class, until another access modifier is seen by the compiler.

Public inheritance is usually associate with the ISA relationship, where as private inheritance is associated with the implemented-in-terms-of relationship. The use of protected inheritance is not as understandable, in terms of connecting it with a relationship, but protected inheritance allows the derived class to access all of the public and protected data of the base class. By members, I mean member functions and member data.

Template Bodies

If your template body is in a cpp file that does not instantiate the template, you will get a linker error if you try to instantiate the
template in another cpp file.


When the compler compiles the file (aka translation unit) that contains the template, it will only instantiate the types of the template that are in that file. These will be the only instantiations in the generated object file. This can seem mysterious, because the template might work for some types and not for others.

This is why it is recommended to put template bodies in the header that defines them.

Nested Templates

You can have nested templates.

Example:
template <class U, class V> class A {
public: template <class V> V function() {return V();} };

Note the the first 'class V' is unrelated to the second 'class V'. It is like having the second 'class V' being 'class W'. To fully instantiate the template, you to provide for class U, class V, and class V again. The following program shows a usage:

int main () {
   A<int,int> a;
   cout << a.function<float>(); 
   return 0;
}

The Writer of STL

The main writer of the STL was Alexander Stepanov. The writer of the Microsoft implementation of the STL was P. J. Plauger.

Templates in Typedefs

You use a template in a typedef.

Example: typedef template class Base_tag
{public: T data;} Base;

Typedefs

The following compiles: typedef struct Base_tag {int data;} Base;

Typedefs

The following compiles: typedef class Base_tag {int data;} Base;

Tags

The C++ grammer name of Base in: typedef class Base_tag {int data;} Base; is tag.

Tags

The C++ grammer name of Base in: class Base {public: int data;}; is tag, but it is also called class-name.

Enumerations

Given typedef enum Basic_tag {One = 1, Some = 2, Many = 10};Basic_tag is the enumeration and One is an enumerator.

Reference: http://www.glenmccl.com/glos.htm

Implicit Conversions

Converting a pointer to bool in an if statement is an example of implicit conversion.

It is an implicit conversion from pointer to bool. An integral promotion is when bool, char, short, enumerator or bit field is contverted to int. There is also integral conversion, where a signed int is converted to an unsigned int or vice versa.

Reference: http://www.glenmccl.com/glos.htm

Template Include is not Defined

When you get the following compiler error: "Template include is not defined", you are missing an '#' before an include directive.

Template Argument Deduction

All of the following template structures (plus more) that can be used in Template Argument Deduction:

    T
    const T
    volatile T
    T&
    T*

The full list is given in the reference below.

Reference: http://publib.boulder.ibm.com/infocenter/lnxpcomp/v8v101/index.jsp?topic=/com.ibm.xlcpp8l.doc/language/ref/template_argument_deduction.htm

Include Paths

When using Windows, the paths in your #includes should use "/" and not "\", because it is guarenteed to work by the C++ standard.

Using "\" will only work in Windows. What sometimes happens when developing in Windows, is that developers use "\" in the include statements and also use mixed case for the header file names in the include statement. When it is decided to port to Linux or other Unix variant, there are a lot of compile errors.

The Pre-increment Operator

The following compiles: int i = 1;++++++i;

The preincrement operator returns an lvalue. Note that i++++++; does not compile, since the postincrement operator returns an rvalue. I would not

recommend coding like this.

Trick to Reducing the Copying of Large Vectors into Maps

When calling insert() on a map object. The value_type is copied once.

If you have a map from something to large vectors, to insert into that map, you would first call value_type(). This would cause
the large vector to be copied. When you call insert(), the large vector would be copied a second time.

Here is a technique to get rid of one of the large vector copies:

#include <iostream>
#include <map>
using namespace std;

namespace {
   typedef vector<unsigned> MyVectorType;
   typedef map<unsigned, MyVectorType, less<unsigned> > U2VU;
   U2U  g_myU2U (less<unsigned>());
   U2VU g_myU2VU(less<unsigned>());
} // end unnamed namespace

int main()
{
   MyVectorType myVector;
   myVector.push_back(1);
   myVector.push_back(2);
   myVector.push_back(3);
   U2VU::value_type vt1(1,MyVectorType());
   U2VU::value_type vt2(2,MyVectorType());
   g_myU2VU.insert(vt1);
   pair<U2VU::iterator, bool> ret;
   ret = g_myU2VU.insert(vt2);
   if (ret.second == true) { // This means the key was not already there, 
                             // so the item was inserted.
      std::cout << "Inserting vector into map via iterator" << std::endl;
      ret.first->second = myVector;
   }
   std::cout << "U2VU has " << g_myU2VU.size() << " items in it." << std::endl;
   return 0;
}

The trick was to insert a value_type() with an empty vector, and then use the returned iterator to set the vector part to the large vector, thus saving a copy of the large vector.

Order of Function Parameters

The reason why some people recommend that the output parameters are listed first, and then input parameters in a call to a function is because default

input parameters must be on the right.

Although default parameters can also be used for output parameters (Steve Read).

Forward Class Declarations

A forward class declaration is not useful if the size of the class is needed, before the class was defined.

Reinterpret Cast

In C++, the reinterpret_cast<>() is used for implementation-dependent casts.

Translation Units

If five *.cpp files are included into one *.cpp file that is compiled; then there will be only one translations unit.
This is not recommended, though.

The Modulus Operator

In C, the value of (1 % (-2) ) is 1. Prior to C99 it could be 1 or -1, depending on the compiler.

Template Point of Declaration

The template's point of declaration is just before the word template.

When explicitly specializing a template, the decaration of the primary template must be in scope at "the point of declaration" of the explicit declaration.

Template parameters have the scope from their point of declaration to the end of it template; so, you can immediately follow a class T template parameter by a T *p template parameter.

References:
http://publib.boulder.ibm.com/infocenter/comphelp/v7v91/index.jsp?topic=/com.ibm.vacpp7a.doc/language/ref/clrc16name_binding.htm

http://publib.boulder.ibm.com/infocenter/comphelp/v8v101/index.jsp?topic=/com.ibm.xlcpp8a.doc/language/ref/explicit_specialization.htm

http://www.kuzbass.ru/docs/isocpp/template.html

Template Point of Instantiation

Given:

template <T> 
int f(T a) {
    return sizeof(a);
} 

int main() {
   f<float>(4.0);
   return 0;
}

The template's point of instantiation is just before "int main".

A template declaration must be in scope at a template's point of instantiation.

Reference: http://publib.boulder.ibm.com/infocenter/compbgpl/v9v111/index.jsp?topic=/com.ibm.xlcpp9.bg.doc/language_ref/name_binding.htm

Function Specifiers

All of these are function specifiers: inline, virtual, explicit.

File Scope

The use of static for meaning file scope is deprecated in C++. The unnamed namespace should be used instead.

Reference: The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section:B.2.3

The char Type

Whether the char is signed or unsigned is implementation-defined.
Note that 'char', 'unsigned char', and 'signed char' are three different types.

Converting an Integer to Less Bits

When converting an integer into an unsigned integer with less bits, the MSBs are lost.

The following program demonstrates this:

#include <iostream>
using namespace std;
int main() {
   unsigned char c = 0xabcd;
   cout << "c: " << hex << static_cast<int>(c) << endl;
   return 0;
}

Unions

Any of the following disqualifies a class for being an element of a union: having a constructor, having a destructor, having a copy operation.

Otherwise the compiler would not know what constructor/destructor/copy operation to call.

Reference: The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section:C.8.3

Namespaces

When the goal is only to encapsulate names, namespaces are preferred over classes.

Reference: The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section:C.10.3

Inner Classes

Members of an inner class cannot access private members of an enclosing class.

Friends

If A is a friend of B and B is a friend of C, then A is not automatically a friend of C. I.e, the friend relationship is not transitive.

Disguised Pointer

A "disguised pointer" is a pointer stored as a non-pointer.
Although, this is not official C++ Standard terminalogy.

Reference: The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section: C.9.1.1

Using Directives

If a name in one namespace clashes with a name in another namespace, and both namespaces are in using-directives, it is not a compiler error if the name is not used.

This sometimes causes problems to suddenly appear, and motivates minimizing the scope of using statements. For example, it is not recommended having using statements in header files.

Reference: The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section: C.10.1

Friendship

Friendship is not inherited.

Reference: The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section: C.11.4

Assembly Code

C++ allows you to embed assembly code in the C++ code.
There is an 'asm' keyword that allows you to do this. Some platforms and compilers do not allow this though.

Declarations

The following are all parts of a declaration: specifier, base type, declarator, and initializer.

The format of a declaration is:
[specifier] <base type> <declarator> [initializer];

An example of a declaration with all of the parts is:
    const int i = 9;
Where
    'const' is a specifier
    'int' is the base type
    'i' is the declarator
    '= 9' is the initializer
Notes:
    1. The declarator is the name of the object, type or function
      that is introduced into a scope by the declaration.
    2. The following are examples of specifiers:
      {extern, static, mutable, auto, register} -- Storage Class Specifiers
    {virtual, inline, explicit} -- Function Specifiers
    {const, volatile} -- cv-qualifiers (also Type Specifiers)
    {struct, class, union, typename} -- Class Specifiers
    {long, long long, short, signed, unsigned} -- Type Specifiers
    {enum} -- enum Specifier
    {private, public, protected} -- Access Specifiers
    friend, inline, typedef
    template

References:
The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section: 4.9.1
http://www.kuzbass.ru/docs/isocpp/dcl.html

Declarations

The optional parts of a declaration are the specfier and the initializer. For example, the following is okay: int i;

Reference: The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section: 4.9.1

Declarations

Not all declarations are terminated by a semi-colon.
namespaces and function definitions don't use a semi-colon in the declaration.

Reference: The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section: 4.9.1

Declarator Operators

All of the following are declarator operators:
    *
    *const
    &
    []
    ()

Reference: The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section: 4.9.1

Declarator Operators

Postfix declarator operators have higher precedence than prefix declarator operators.

References:
The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section:4.9.1
http://www.velocityreviews.com/forums/t450319-declarator-operators.html

Using Declarations

When you use a using declaration, you create a local synonym.

References:
The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000. Section: 8.2.2
http://www.research.att.com/~bs/glossary.html

Using Declarations versus Using Directives

A using-declaration is different than a using-directive.

A using-declaration brings one name into a scope. This name can be used as if it was declared locally.
For example,
    using std::vector;
Note that the keyword 'namespace' is not used.
A using-directive brings all the names of the namespace into a scope.
For example,
    using namespace std;
You can also have a namespace alias, which can be used make a namespace name shorter or clearer.
For example,

namespace WHAT_YOU_SEE_IS_WHAT_YOU_GET {
    void widget();
}
namespace WYSIWYG = WHAT_YOU_SEE_IS_WHAT_YOU_GET;

Reference: The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000, Section: 8.2.2-3

External Linkage

A name has external linkage if it can be used in a translation unit that is different that the one in which it was defined.

Destructors

You call a destructor explicitly, but you probably don't want to do it.

Reference: The C++ Programming Language by Bjarne Stroustrup. Addison-Wesley, 2000, Section: 10.4.1

The setw() Function

When writing to a stream, setting the width property only lasts to the write of the stream.

For example, if you want to put three 4's in a field width of 20, you would do this:
cout << setw(20) << 4 << setw(20) << 4 << setw(20) << endl;

IOS Flags

When writing to a stream, setting the justification property (e.g., right and left) continues until it is changed.

If you are writing a logger, it is programmatically polite to first save the ios flags with a statement like:
    ios::fmtflags flags = cout.flag(); // Save the flags.
    // Change cout flags the way you want.
    cout.flags(flags); // Restore the flags.

The difftime() Function

One of the reasons difftime() returns a double is because time_t can be either an integer or floating point type.
Otherwise, it would have been an int type.

The Default Allocator

The default allocator for type T is allocator<T>.

Template Parameters

Template parameters can refer to previous template parameters.

Here is an example:

template <class T, class CONTAINER = std::vector<T> > 
class MyContainer
{
 public:
   CONTAINER container;
};

operator void*()

The return value of the following prototype: operator void *(); has the type: 'void *

operator void *()

The following code compiles:

#include <iostream>
using namespace std;
struct MyStrm
{
  MyStrm()
  {
    d_cnt = 5;
  }
  operator void *()
  {
    return d_cnt ? &d_cnt : 0;
  }
  int get() {
    return d_cnt--;
  }
  int d_cnt;
};

int main()
{
  MyStrm myStrm;
  while (myStrm)
    cout << myStrm.get() << endl;
  return 0; 
}

The above program prints out the following:

5
4
3
2
1

Const

The folloiwng compiles:

      int                g_int        = 1;
const int               g_c_int       = 61;
const int       &       g_c_int_ref   = g_c_int;
      int const &       g_int_c_ref   = g_c_int;
      int       * const g_int_ptr_c   = &g_int;
      int const * const g_int_c_ptr_c = &g_int;
const int       * const g_c_int_ptr_c = &g_int;
      int const *       g_int_c_ptr_c = &g_int;

But the following does not compile:

const int const * const g_c_int_c_ptr_c = &g_int;

The const before or after the int specifies that the int cannot be change. The const after the '*' specifies that the pointer to the int cannot change. When you have three consts, you are specifying that the int is const twice, which is an error.

Try-Catch Block around MIL

A try-catch block can be wrapped around a constructor's member initialization list (MIL).

Here is an example of the syntax:

C::C()
   try
   :
   d_b(0)
   {
      // No exception
   } catch(...) {
      // Exception
   }

This is an example of the function try-catch block. I did not find it useful for constructors. It seems even if you catch the exception from d_b's constructor, your program is going to seg-fault using the Sun compiler and abort using the gnu compiler. The gnu compiler lets you do some work first in the catch block before it aborts you. With the gnu compiler on cywin, I was able to print out a message before being aborted.

Reference: http://www.cygwin.com
Cygwin has a free unix environment for Windows, that includes the gnu compiler, Perl and a lot of other utilities.

The ostringstream Member Function str()

The ostringstream member function str() converts an ostringstream to a string.

Here is a trivial example:

  std::string my_string;
  std::ostringstream my_ostringstream(
                      std::stringstream::in | 
                      std::stringstream::out );
  my_ostringstream << "Total: " << total;
  my_string = my_ostringstream.str();
  std::cout << my_string << std::endl;

Default Constructors for Elements in a Map

If you have a map to a class or struct, that class or struct needs a default constructor.

The default constructor is needed because of operator[]. When you try to access a map element that doesn't exist, operator[] creates the element with the element's default constructor

GNU Compilers

You should use the gcc compiler for C and the g++ compiler for C++.

Although gcc will compile C++ code, you will either need to 1) add switches; or 2) use g++ to link the C++ code.

Using the Gnu Math Library

If you want to use sin() in the gnu compiler for C, you have to use the -lm compiler option. You don't need it for the C++ compiler.

Note the library name will be libm.so, which is usually a symbolic link to a library name that includes the version such as libm.so.2

The wchar_t Type

In C++, you do not have to include a header file to use the wchar_t type. In C++, it is a primitive type. In C, you need to include wchar.h.

The strtoull() Function

The value of strtoull("15", 0 , 16) is 21.

strtoull() converts a string to an integer. In the case above, the string is interpreted as base 16. So 15 maps to (1*16) + 5*1 = 21. There are several strtoxxx()-like functions, here are some: atoi, atol, atoll, strtol, strtod

Reference: http://www.cplusplus.com/reference/clibrary/cstdlib/strtoul.html

Rethrowing Exceptions

When catching an exception e, is it better to rethrow the exception with 'throw;' rather than 'throw e;', because 'throw e' may throw away information if the exception was caught with a super class type. If the exception is caught by value, rethrowing the exception using the name of the exception will slice off any extra data, if the exception object is has a dynamic type more derived than the type in the catch specification. If the exception is caught by reference (using a reference (&) or pointer(*)), rethrowing the exception will not slice off the information. For the most part, it is better to re-throw without the variable name.

Reference: www.semantics.org

valarray

valarray does not have begin() and end() member functions.

The valarray is considered a "near-container" of the STL. There are three other "near-containers." They are:
    1) C-like array; 2) string; and 3) bitset
Reference: C++ How to Program (7th Edition) by H. M. Deitel, and P. J. Deitel. Prentice Hall, 1997, Section 20.11 Introduction to Containers.

Function Try-Catch Blocks

Both of the following function declarations compile:

void func1()
{
    try
    { }
    catch (...)
    {}
}

void func2()
try
{ }
catch (...)
{ }

The second one is called a function try/catch block. Here is an example in a constructor:

MyClass::MyClass()
try 
: d_mem1(0), d_mem2 
{ } 
catch (...) 
{ }

References:
Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library by Scott Meyers. Addison-Wesley, 2001.
C++ Templates by David Vandevoorde and Nicolai M. Josuttis. Addison-Wesley, 2003
http://www.gotw.ca

Exit Codes

EXIT_SUCCESS and EXIT_FAILURE are constants defined in the C++ language.

They are MACRO constants defined in cstdlib and stdlib.h

References:
Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library by Scott Meyers. Addison-Wesley, 2001.
C++ Templates by David Vandevoorde and Nicolai M. Josuttis. Addison-Wesley, 2003
http://www.gotw.ca