C++ Notes: Pointer Members vs. Default Constructor

It appears that sometimes it is a good idea to keep pointer-to-object members rather than object members in a class. Three good occasions when we would want to do that are:

1. When working with incomplete types. Classic example is when implementing the Pimpl idiom.
2. When we want our class to be copyable and the member object is of a non-copyable class.
3. When making a member out of a class that does not have a default constructor.

To elaborate on the second point, the copy construction and copy assignment of a class usually involves copying/assigning the parent classes and then the members. This is what the compiler would do with the implicit copy constructor and copy assignment operator. But even if we implement it ourselves, it should almost always be constructing/assigning parents and members, and in that order. If the members are of a non-copyable class, then this means that the class that we define also becomes non-copyable.

To elaborate on the third point, if we make use of an object member out of a class that does not have a default constructor, then, while constructing our class, we have to make sure that we call the appropriate constructor for the member with appropriate arguments. This can get a bit restrictive especially with templates:

template <typename T>
class CustomClass1 {
private:
    T data_;
...
};

CustomClass1 can only be specialized with types that have default constructors. Instead, CustomClass2 below can be specialized for any type:

template <typename T>
class CustomClass2 {
private:
    T* pData_;
...
};

As an aside, two things to keep in mind when defining classes with pointer-to-object members:

• It is probably a good idea to make use of boost::scoped_ptr or boost::shared_ptr instead of raw pointers, so that deletion is handled automatically.
• Always remember to provide one’s own declarations (with or without definitions) of the copy constructor and copy assignment operator for the class that has pointer-to-object members, as, the implicitly generated ones almost certainly will not be what we want (and can very likely be dangerous). Note that if we used a scoped_ptr, this is automatically taken care of, because, as indicated in point 2 above, since scoped_ptr is a non-copyable class, the enclosing class itself becomes non-copyable (unless you intentionally make it copyable and deal with non-copyable members somehow).

Now, I guess the other way to look at point 3 is to always provide a default constructor for a class unless it absolutely does not make sense. It helps in many ways:

1. It alleviates the restriction of having to keep pointer members (if this were the only reason, like in point 3 above).
2. You can create dynamic arrays as follows, only if there is a default constructor:

CustomClass* dynamic_array = new CustomClass[20]; //only possible if CustomClass has a default constructor.

//For static arrays you could invoke parametrized constructors using the initialization syntax, provided there is an accessible copy constructor:
CustomClass static_array[20]; //only possible with default constructors.
CustomClass static_array_param[2] = { CustomClass(...), CustomClass(...) }; //parametrized constructors invoked.

//Similarly for container classes. Following vector works with parametrized constructors provided there is an accessible copy constructor (which is a must for elements in a vector anyway):
std::vector<CustomClass> v(10, CustomClass(...));

// But notice that, strictly speaking, you are creating temporary object(s) with the parametrized constructor and then copy-constructing the elements in the static array or vector using the temporaries.

Interestingly, many standard library classes provide default constructors although it might appear to not make much sense.

#include <fstream>

ofstream file1("/tmp/tempfile"); //parametrized constructor makes sense.

//However, we can achieve the same effect with the following:
ofstream file2; //default constructor.
//Nothing constructive you can do with file2 until you call the open method:
file2.open("/tmp/tempfile");
...

Updates:
1. Corrections in the section about default constructors, with regard to static arrays and vectors.

2. Reference: http://www.parashift.com/c++-faq-lite/ctors.html#faq-10.5

3. Reference: http://www.acm.org/crossroads/xrds1-4/ovp.html

A slip in swap()

What’s the bug in the C++ function swap1() below, a function that intends to swap two integers…

void swap1(int& a, int& b)
{
    a = a^b;
    b = a^b;
    a = a^b;
}

… that is not there in swap2() below?

void swap2(int& a, int& b)
{
    int t = a;
    a = b;
    b = t;
}

Learned it the hard way. My Quicksort program was misbehaving and it was a bit puzzling until I figured out that the bug was in my swap function. The bug surfaces when you try to swap a variable with itself – you’d want it to remain unchanged, but swap1() will zero it out.

In a related note, Bjarne Stroustrup wrote (and I quote from here):

if (this == &a) return;  		// beware of s=s;

:)

No matter how well you think you know something…

… nothing like getting it wrong to start wondering and appreciating the point.

Recently, faced with a decision problem, I started off with an approach that used Dynamic Programming (DP, here onwards) – because it appeared deceivingly similar to those classic DP problems, you know, matrices and all, and I was a bit over-enthusiastic. The problem basically turned out to be the decision version of the Pathfinding problem – to determine whether there exists a path between given two nodes u,v .

Although I switched to a ‘better’ algorithm, which still solved the optimization problem (Dijkstra’s shortest path algorithm) and therefore did feel like an overkill, I realized later that all I needed to do was determine whether u and v belonged to the same connected component of the graph, and thus a simple Depth First Search would have sufficed.

In retrospect, my first thought was that I had made the mistake of trying to solve a decision problem using dynamic programming, that I had overlooked the fact that DP should be applied only to optimization problems. But then it got me wondering – how come finding the n^th Fibonacci number, which is not an optimization problem, is something you can solve effectively using DP? (On a side note, this also brought my attention to the type of computational problems – decision, search, optimization, counting, promise. I guess Fibonacci would be a search problem?)

So the whole thing got me asking myself two questions:

1. Do the problems for which DP is applicable, necessarily be optimization problems? The requirements for DP are that the problem exhibit optimal substructure and subproblem overlap. Fibonacci is big on overlap, and exhibits optimal substructure trivially (later Fibonacci numbers are based on previous ones). But does that make Fibonacci an optimization problem in some twisted way?
2. Can a decision problem be converted to an optimization problem of equal hardness? Every optimization problem has an associated decision problem, which is usually easier, so I’m talking about whether there is one of equal hardness – meaning solving one is equivalent to solving the other). Or does it even not make sense? In my first approach of trying to solve the problem using DP, I was in some way trying to convert the decision problem into an optimization problem (marking distances as ∞ if no edge existed between two nodes and thus trying to see if my dynamic programming ‘equation’ that tries to optimize something, would trivially avoid those edges and so on). Question is, could I have succeeded by taking that route at all?

 

“”"Finds the sublist in a given list of integers that has the max sum
among all such sublists. Uses dynamic programming to find the solution
in O(n) time thus:
v(i) = max( v(i-1) + a[i], a[i] ),
where v(i) denotes the max sublist ending at i. So the max sublist’s
sum would be the max of all v(i)s and the corresponding sublist will be
returned.
“”"
def maxsublist(a):
“”"Finds the sublist of maximum sum, in a given list,
and returns a tuple (max_sum, max_sublist)
“”"
try:
if len(a) == 0: raise Exception
except Exception:
print “List is empty!\n”
else:
l = 0 #left index.
r = 0 #right index.
v = a[0] #v stores the optimal for i, from i = 0 to n-1
max = v
for i in range(1, len(a)):
v,lt,rt = v + a[i] > a[i] and (v + a[i], l, i) or (a[i], i, i)
if v > max:
max, l, r = (v, lt, rt)
return (max, a[l:r+1]) #[l, r)#Unit tests:
if __name__ == "__main__":
li = [-1,4,-3,3,-2,4,-1]
print li
y = maxsublist(li)
print y
if y == (6, [4,-3,3,-2,4]):
print “Pass”
else:
print “Fail”

C++ Notes: Myths about Constructors

Some facts about Constructors in C++ that I came to understand only eventually:

1. The ‘Default’ in a ‘Default Constructor’, refers to the parameter list, and that too in the call. Basically, a default constructor is a constructor that can be called with no arguments. So a constructor is a default constructor if it does not take any arguments or it takes default values for all its parameters – irrespective of whether you’ve explicitly defined one or the compiler generated one for you.

2. … which is why there is no such thing as a Default Copy Constructor. I believe there are mainly two kinds of C++ folks out there – those that use the term ‘default copy constructor’, and those that used to use this term and now refrain from it. The whole problem is one tends to think of ‘Default’ in this context to refer to ‘one that compiler generates by default if you don’t provide one’. It naturally follows from point #1 above that one can’t have the copy constructor called without any arguments, so there is no such thing. Unfortunately, this has become sort of a standard usage, even in some books (just do a google search and you’ll know). But you wouldn’t see Stroustrup or Meyers use this term, so that should be enough reason to refrain from it. I prefer the term ‘compiler-generated’ instead – ‘Compiler-generated copy constructors’ and ‘Compiler-generated default constructors’.

3. Another mistake we all make at some point or the other, and we hear others make almost all the time, is the following innocuous looking statement: ‘the compiler-generated copy constructor does a bit-wise copy of its members’. Correct? No! And it’s one of those things that you quickly realize is wrong when you are made to think of it, but you learned it wrong because it was passed on to you and you never paused to think about it. The compiler-generated copy constructor does the following:

• Calls the copy constructor of any and all base classes with its input argument, the RHS object reference (so that the base parts are copy-constructed by the base itself).
• Constructs the non-static members by ‘copying’ from the respective members of the RHS object – meaning, for those members that have a copy constructor, the copy constructor is called, and for others, a ‘regular’ copy assignment is done.

4. A copy constructor does not necessarily have to take a const RHS. The signature one usually sees for a copy constructor is the following:

T::T(const T& rhs);

But the following is perfectly valid as well:

T::T(T& rhs);

Of course, it makes sense once you think about it. A classic use of this is in the implementation of std::auto_ptr. The smart pointer philosophy for auto_ptr is to transfer ownership and nullify the RHS in a copy. That is, if you do the following:

...
std::auto_ptr<int> ptr1 = new int;
std::auto_ptr<int> ptr2 = ptr1;
...

the statement at line 03 results in ptr1′s member primitive pointer to int getting set to 0. In order to facilitate this, the copy constructor has to take a non-const reference to the RHS.

5. Copy Constructors need not always be present. This might be a compiler specific thing, but one thing I noticed while experimenting with gcc is that the compiler does not always generate a copy constructor for your class, even when you don’t provide one. I think the compiler ‘optimizes’ it away if it figures that it can do without it – after all, structs could be copied in C without any ‘functions’, and the same is built into C++ as well, so I guess you fall back to it.

–

Updates:

(7th Aug 09): Reg point# 3, check out this entry on Herb Sutter’s GOTW about the order in which subobjects are constructed.

Heap’s the man

I’d always wondered one thing about the heap data structure. Wherever I’d seen it being used in an algorithm, all it ever did was give the min or max in O(log n) time – in other words, it was always used to implement a priority queue. But I always always had the feeling that a heap is capable of a little more, you know. I mean, agreed that the heap is much more relaxed in its relational property than a BST, but surely, it kept more information than what was required to find the min? Surely, there is more likelihood of finding the smaller elements at the top than at the bottom? Surely, there is more use of the property that every element is the smallest in the subtree rooted at it?

And so it was that, when I read about a certain use of heap in this article on wikipedia, I was enlightened. In particular, it talked about doing a traversal of a heap.

Now, heap traversal is not something you see everyday. How is it interesting? How does it even make sense? Well, imagine the following problem: Given a heap containing n elements, return the k smallest elements from it (not in any specific order).

One way to do it, the first thing that usually comes to mind is to do a removeMin() on the heap k times, which would return the k smallest elements (and in order), in O(k log n) time.

But imagine instead, and herein lies the rub, using the Breadth First Traversal on the heap – but with the exception that, instead of picking an element from the front of the queue that stores the children of elements that we visit, pick the min element and recursively visit that child. In other words, instead of using a queue to store the children of a node when we visit it, use a priority queue.

One can see that using this approach, the BFS traversal turns into a traversal that visits the elements in order of their ‘weights’. Then, coming back to our problem, to get the k smallest elements, we will have to ‘visit’ k times in the traversal, and the priority queue would therefore contain at most k elements (a visit results in 1 element being deleted from and 2 children being added to the priority queue).

If we implement this priority queue, in turn, using another heap, we can then find the k smallest elements in O(k log k) time, as the second heap would contain at most k elements at any time. With an additional space requirement of O(k), of course.

So, for instance, to find the top log n elements from a heap containing n elements, one could do it in O(log²n) time using the first approach, but in O(log n log log n) time using the second.

Now, is that awesome or what? :)

Why isn’t there an asymptotic notation for a tight bound?

For instance, we know that comparison based sorting takes Ω(n) time definitely, for the trivial reason that any algorithm will need to ‘consider’ the entire input. But we know that Ω(n) is not a tight lower bound. Comparison based sorting will take, in the worst case, Ω(n log n) time (to decide on one of the n! permutations of the input). This bound, we know is tight.

Was just thinking it would have been convenient if there was a way to express the ‘tightness’ using another one of those characters from the Greek alphabet, instead of having to say that so and so bound is tight every time. None of the existing asymptotic notations I know of (O, o, Ω, ω, Θ) help achieve this.

Perhaps just as well, we probably have enough notations already…

PRIMES and NONPRIMES

The other day, I happened to go through a simple but excellent lecture on the background of the P vs. NP problem. I really recommend it for brushing up, if it has been a while.

Among other things, I found a particular remark interesting. In 1972, when Richard Karp, in his famous paper, showed that many naturally occurring problems for which we didn’t know of a polynomial time algorithm, are in fact NP-complete, he also listed a few other such problems that couldn’t be proven to be NP-complete. The latter included NONPRIMES, which is the following problem:

“Given a number, is it composite?”

Interestingly, he listed this problem instead of PRIMES itself, which is:

“Given a number, is it prime?”

What got me wondering was why he chose to list NONPRIMES instead of PRIMES itself. (Not that it makes much of a difference, but, surely, PRIMES is much more impressive and prettier?)

So why did he? And what’s the difference at all, aren’t they complements of each other?

To understand that, let’s reformulate the questions as follows:

NONPRIMES: Are there two numbers less than n whose product is n?

PRIMES: Is the product of every possible pair of numbers less than n not equal to n?

First, remember that the input size is not the value of n but the length of its encoding which would be the number of bits in n which is logn. (For more info on this, visit this wikipedia link on pseudo-polynomial algorithms).

So here’s the thing: According to the lecture, the reason PRIMES wasn’t listed is that, at that time, it wasn’t clear whether PRIMES is in NP at all. On the other hand, it was easy to show that NONPRIMES is in NP: Given a “yes” instance of the problem (which would be a pair of numbers whose product is n), one could easily verify that it is indeed right by just multiplying and checking. Multiplication will take O(log²n) time.

Interesting history, wouldn’t you say?

But let’s talk about the other question: What’s the difference really between the two problems? Aren’t they complements of each other?

Well, the answer to that gives us some insight into complexity classes. If a problem is in NP, then it’s complement need not be in NP. The problems which are complements of the problems in NP form the class co-NP. NP and co-NP are thought to be not equal.

But, aren’t they effectively the same questions? Can’t I just say “yes” for PRIMES if I get a “no” for NONPRIMES and vice versa?

Yes, you can! But that doesn’t necessarily mean that the running time of ‘verifying that a “yes” instance is indeed right’, is the same for both NONPRIMES and PRIMES – and therein lies the rub. For NONPRIMES, as we saw above, the verification can be done in polynomial time. But for PRIMES, if the question we consider is the above (“whether the product of every possible pair of numbers less than n is not equal to n“), then a “yes” instance itself would be the set of all pairs of numbers less than n. That’s ⁿC₂ pairs. To verify that that they all multiply to a different number will take O(n² log ²n) time which is exponential to the input size, the number of bits.

How about that!

Of course, PRIMES need not be formulated as “whether the product of every pair is less than n“. There could be a better way to formulate the problem so that the “yes” instance is small enough and its verification also takes polynomial time. In 1972 nobody knew of such a way. Indeed, a few years later, someone did and it was proven that PRIMES is in NP.

And in 2002, it was proven that PRIMES and therefore NONPRIMES are in fact in P.

Understanding what the classes really stand for is therefore fundamental. I kinda wonder now if this whole thing should be thought of as a limitation of the way the complexity classes are defined.

p.s: Another interesting fact is that for all problems in P, the complements are also in P. Also, if a problem and its complement are both in NP (which is equivalent to saying that the problem is in both NP and co-NP), then I think it is believed that the problem is likely not NP-complete.