Geoffrey Zheng\’s Bloh Bloh Bloh

Mostly from Stroustrup 3rd Ed and Effective C++/STL.

Inheritance

Virtual base class: further derived class will have only one copy of the virtual base class: class C -> class A, B : virtual public Base -> Base

Default destructor of a derived class is virtual if the base class destructor is virtual.

Implicit inheritance (class A : B) means public if B is struct, private if B is class.

Suppose class A -> class B:

Derived class members hide base class members on a per-name basis:

class Base {
public:
virtual void f(int x);
};

class Derived: public Base {
public:
virtual void f(double *pd);
};

Derived *pd = new Derived;
pd->f(10);                            // error!

Correction:

class Derived: public Base {
public:
using Base::f;                   // import Base::f into Derived's scope
virtual void f(double *pd);
};

Derived *pd = new Derived;
pd->f(10);                         // fine, calls Base::f

A derived class can access a base class’ protected members only for objects of its own type… This prevents subtle errors that would otherwise occur when one derived class corrupts data
belonging to other derived classes.

Exception

Anything can be thrown, including primitive types. Exceptions are copied when thrown.

catch(…) cathes all exception.

Constructor can throw exception. It can enclose member initializer in try block:
X::X(int s) try : m_data(s) { … } catch() { … }. Destructor should handle any possible exception that may be thrown within itself, otherwise if the destructor is called during stack unwinding for exception handling, the exception handler doesn’t know in what order it should handle the destructor exception and the original exception.

Smart pointer

From Stroustrup’s C++ book:

Resource Acquisition is Initialization: put resource in member objects and initialize them in constructor initializer list, so that if constructor fails at any point the destructor of those member objects that have been successfully constructed will be called and release the resource. Example: file pointer in File object, int array in vector, etc.

auto_ptr in std <memory> supports RAI: auto_ptr<MyClass> p(new MyClass) automatically destruct the MyClass object when p goes out of scope, and p is used just as MyClass* because -> is overridden: X* operator->() { return ptr; }. After one auto_ptr is copied to another, the source does not point to anything (destructive copy) so that the same resource won’t be deleted twice. Therefore it cannot be put into a std container and algorithms like sort(). Note that auto_ptr’s constructor is explicit:
explicit auto_ptr(X* p = 0) throw() /* throws nothing */ { ptr = p; }
which means that the constructor must be explicited invoked to avoid implicit conversion (e.g. through copy constructor like auto_ptr<Class> p = pClass).

auto_ptr can serve the purpose of Java’s finally() clause, such that allocated resource will always be deleted no matter if a function exits normally or through exceptions. If common code block needs to be executed in both paths, it can be put into the destructor of a local object:

void function()
{
CCleanUp cleanUp;
try
{
}
catch(ex&)
{
throw;
}
}

Here’s a nice article on auto_ptr and stl container.

Smart pointer in Boost

The “History and Acknowledgements” section is very interesting. It talks about how auto_ptr started and the boost smart pointers evolved. Smart pointers in boost 1.32:

• scoped_ptr: same as auto_ptr but noncopyable. No overhead. Use scoped_array for dynamically allocated array. Can be used for handle/body idiom (pimpl) to not expose anything about a class in header file (use incomplete type):
  … class CMyClass; scoped_ptr<CMyClass> p; …
• shared_ptr: has reference count, can be shared (will be deleted when last reference goes out of scope). Can use in std containers. Cannot deal with cyclic reference–use weak_ptr. Use shared_array for array. Do not use unnamed temporary. For example f(shared_ptr<int>(new int(2)), g()) is bad because function argument evaluation order is unspecified, if g() is called after new int(2) and before shared_ptr constructor and g() throws exception, the shared_ptr hasn’t been constructed and thus new int(2) is leaked.
• weak_ptr: stores a “weak reference” to an object that’s already managed by a shared_ptr for a non-owning observer
• intrusive_ptr: use embedded reference count

Cast

• static_cast: like C-style cast. Can’t remove constness from an expression
• const_cast: only to cast away the constness or volatileness of an expression
• dynamic_cast: perform safe casts down or across an inheritance hierarchy. Can only cast class with virtual function, i.e. polymorphic type (it’s a requirement for RTTI). Returns 0 if failed on pointer cast, throws bad_cast on reference cast. Cannot cast void*.
• reinterpret_cast: perform type conversions whose result is nearly always implementation-defined. As a result, reinterpret_casts are rarely portable

Operators

Conversion operator X::operator T() converts an object of type X to type T. Note that the method has no return type, like a ctor.

operator[] can only be a member function.

operator= should check for self assignment (this==&rhs), copy base class members (static_cast<Base&>(*this)=rhs;) deallocate pointer, reallocate, then copy pointer content.

const

C doesn’t have const, surprise.

const char* p (or char const * p) is a pointer to a const, so “*p = 0” is error but “p = p2” is ok.
char* const p is a const pointer to a char, so the example results are reversed.

A string class may provide operator* that converts string to char*:
operator const char*() const { return data; }
Without the first const, the returned pointer can be used to change string.data.
Be aware, though, if a function returns a string like:

string dummy() { return "string"; }
const char* p = dummy();

It compiles but p points to garbage because the memory is gone with the temp string object. That’s why std::string has c_str() instead of operator*.

A “mutable” member variable can be modified in const member function.

operator* should return const to avoid stupid thing like “(a*b)=c”.

Reference

Reference always refers to the same object.

int i = 1, j = 2;
int& r = i; // &r = &i so r is just a symbol and doesn't take any extra memory
r = j; // now i = r = 2, same as i = j
j++;

Child class object passed by value as parent class object in function argument will be sliced–losing all child’s stuff and become only a parent object. Pass by reference doesn’t have this problem.

NEVER returns a reference to a local object.

const reference can be initialized by a non-lvalue, e.g. const myClass& inst = 1 is ok if myClass has a ctor myClass(int 1). dtor will be called when inst goes out of scope.

Compiler

Compiler generates default ctor, copy ctor, dtor, assignment op, and & op:

class Empty {
public:
  Empty();                        // default constructor
  Empty(const Empty& rhs);        // copy constructor
  ~Empty();                       // destructor
  Empty& operator=(const Empty& rhs);    // assignment operator
  Empty* operator&();             // address-of operators
  const Empty* operator&() const;
};

Compiler won’t compile, though, a class with a reference type member because per member assignment doesn’t make sense for a reference type.

From now on it’s all STL stuff.

Container

• Sequence
  • vector: 1D array for efficient access to element in any order. at() checks range while [] doesn’t.
  • list: doubly-linked list optimized for insertion and deletion of elements
  • deque: double-ended queue for addition/deletion at the ends (as efficient as list), and subscripting as efficient as vector.
• Sequence adapters: stack, queue (insert at back and extract at front), priority_queue
• Associative: map, multimap (allow duplicate keys), set (only keys, no value), multiset
• Almost containers: built-in array, string, valarray (vector optimized for numeric computation), bitset

Stream

istream

get(Ch* p, streamsize n, Ch term = ‘\n’) puts 0 at the end. It does NOT remove the terminator char from the stream, whereas getline(…) does.

read(Ch* p, streamsize n) reads at most n chars. It does NOT put 0 at the end.

ignore(streamsize n = 1, int_type t = eof) throws away at most n chars from the stream, including the terminator.

Whitespace: blank, \t, \v, \f, \n, \r (test by isspace(int) in <cctype>). By default >> skip whitespace (override by is.unsetf(ios_base::skipws)). is >> ws eats one whitespace.

Exception

Stream has 4 state flags: good, eof, fail, bad. Stream can have exception set for them: stream.exceptions( ios::failbit | ios::badbit | ios::eofbit ), then catch ios::failure.

iomanip

Can be inserted into iostream: boolalpha/no~, show/noshow base/point/pos, skipws/no, uppercase/no, internal/left/right, dec/hex/oct, fixed/scientific, endl (also flush), ends = , flush, ws, set base/fill/precision/setw.

Sort

• sort: nlog(n) on average
• stable_sort: In a stable sort, if two elements in a range have equivalent values, their relative positions are unchanged after sorting.
• partial_sort: only sort the first n elements
• nth_element: only find the first n elements without sorting them
• partition and stable_partition: separate the elements of a standard sequence container or an array into those that do and do not satisfy some criterion

Some algorithms (binary_search, set_union, merge, etc.) require data range to be sorted.

Find

Algorithms

Nonmodifying

• for_each
• count, count_if
• min_element, max_element
• find, find_if, find_end, find_first_of, adjacent_find
• search, search_n
• equal
• mismatch
• lexicographical_compare

Modifying

• for_each
• copy, copy_backward
• transform
• merge
• swap_ranges
• fill, fill_n
• generate, generate_n
• replace, replace_if, replace_copy, replace_copy_if

Removing

• remove, remove_if, remove_copy, remove_copy_if
• unique, unique_copy

Mutating

• reverse, reverse_copy
• rotate, rotate_copy
• next_permutation, prev_permutation
• random_shuffle
• partition, stable_partition

Sorting

• sort, stable_sort, partial_sort, partial_sort_copy
• nth_element
• partition, stable_partition
• make_heap, push_heap, pop_heap, sort_heap

Algorithms for Sorted Ranges

• binary_search
• includes
• lower_bound, upper_bound
• equal_range
• merge
• set_union, set_intersection, set_difference, set_symmetric_difference
• inplace_merge

Numeric

#include <numeric>

• accumulate
• inner_product
• adjacent_difference
• partial_sum