Monday, October 31, 2011

Quiz Time: X-Y Path Permutations

Q: In an x-y coordinate system (or Cartesian coordinate system), how many paths are there from the point of origin to a point with coordinates ⟨x, y⟩, where
  • x ∧ y ∈ Z + (x and y are positive integers),
  • a path is built up from exactly x + y segments, each with a length of one (1), and
  • a line segment must be either horizontal or vertical?

See below for answer.

Tuesday, October 25, 2011

Behind the Scenes: Name Hiding in C++

Name hiding happens when an overloaded member function is declared in the scope of a derived class. Here is an example:
class Base
    virtual ~Base() {}

    virtual void someFunction() const;
    virtual void someFunction(int x) const;

void Base::someFunction() const {}
void Base::someFunction(int x) const {}

class Derived : public Base
    void someFunction() const;

void Derived::someFunction() const {}

int main(int argc, char **argv)
    Derived d;

    return 0;
This, in fact, will not compile and gcc reports the following error:
error: no matching function for call to 'Derived::someFunction(int)'
While if we remove Derived::someFunction(), the code compiles without errors. First of all, note that there are two orthogonal language features involved here: function overloading and inheritance (overloading vs. overriding).

The scope of Derived becomes nested within the scope of its base class, however, introducing a name in the derived class obscures all overloaded versions of the same function in the Base class, hence the compiler error. This is actually standard behavior, for reasons which will be discussed below.

Thursday, October 6, 2011

Lambdas in C++0x, Part II

Let's recall the syntax of a lambda expression, from the first part of this post:
  [C](P) M -> R { body }(Q)
  C = capture specification
  P = parameter specification
  M = mutable specification
  R = return type specification
  Q = actual call parameters
Lambda expressions are locally defined functions, also known as anonymous functions. A minimal example could look something like this:
int main()
    auto f = []() { std::cout << "hello"; };
    return 0;
The lambda can also be invoked as it is defined, on-the-fly:
[]() { std::cout << "hello"; }();
Here is a lambda that takes an int as argument:
auto fn = [](int x) { std::cout << "x = " << x << "\n"; };
Side note: I tend to use the terms parameter and argument more or less interchangeably. To make things clear, we should, however, make a distinction between the two:
  • A parameter is a variable declared in the prototype or declaration of a function.
  • The argument is the value that is actually passed to the function.

A return value can be specified, using the trailing return type specification (→ R):
auto fn = [](int x) -> int { return x + 1; };
int n = fn(1);
std::cout << "->" << n << "\n";
The auto keyword saves us some work when the compiler is able to infer the type of an expression automatically. Alternatively, we could write:
std::tr1::function<int(int)> fn = [](int x) -> int { return x + 1; };
In this post, I will continue to examine the capture specification and mutable keyword.