Thursday, May 29, 2008

C++ puzzles and interview questions

After having a lot of requests from the readers, I finally made on concise effort to get one C++ puzzle blog on.

I have not been actively blogging for the last few days and was not able to find time to even compile the C thing,

I will try to post the C puzzles thing tomorrow or sometime tonight.

 

Here are the C++ puzzles, They come in very handy in your day to day software work ( naah joking )

Only if you have to clear and interview and ask for good CTC you better be good with your answers

 

Advantages of automatic storage vs. heap storage

Using operator new (or malloc() in C) to create objects on the heap is expensive in terms of performance (allocating heap memory usually involves a long negotiation with the OS), maintenance (dynamic allocation may fail; extra code to handle such exception is required) and safety (object may be deleted more than once or not deleted at all) as demonstrated in the following example:

 
void f() {
 
string *p = new string(2000);  //initial size of 2000 chars
                                                                                            
//...meddle with p
 
if (condition) 
{
               cout<< “condition is true”;                    
               return;     //oops! memory leak: p has not been deleted
}
else 
{
               delete p;
               cout <<“condition is false”;
}
delete p; //oops! undefined behavior: p deleted twice if condition                    //is false
 
return;
 
}//end f()

So before you create an object using new (or malloc() in C), try to see whether it can be created on the stack instead:

 
void f() {  //safer, faster and easier to maintain version
 
string p(2000);  //initial size of 2000 chars
                                                                                            
//...meddle with p
 
if (condition) 
{
               cout<< “condition is true”;                    
               return;     //OK, p’s memory is automatically reclaimed
}
else 
{
               cout <<“condition is false”;
}
 
return;
 
}//end f()

Dynamic Memory Allocations and Thread Safety

In general, the global new and delete operators are implemented in a thread-safe manner: each invocation of either operator locks the heap before performing the allocation/deallocation of memory and when the action is completed, the heap is unlocked. Thus, you can use new and delete safely in multithreaded applications. However, the thread-safety of new and delete imposes an unnecessary runtime overhead for single-threaded applications. Therefore, in time-critical single-threaded application, you may consider using alternative memory management schemes such as overloading new and delete for particular classes or using a custom memory pool.

Preventing Memory Fragmentation

Applications that are free from memory leaks but perform dynamic memory allocation and deallocation frequently tend to show gradual performance degradation if they are kept running for long periods. Finally, they crash. Why is this? Recurrent allocation and deallocation of dynamic memory causes the heap to become fragmented, especially if the application allocates small memory chunks (int, an 8 byte object etc.). A fragmented heap can have many free blocks, but these blocks are small and non-contiguous. To demonstrate this, look at the following scheme that represents the system's heap. Zeros indicate free memory blocks and ones indicate memory blocks that are in use:

 
100101010000101010110

The above heap is highly fragmented. Allocating a memory block that contains 5 units (i.e., 5 zeros) will fail, although the systems has 12 free units in total. This is because the free memory isn't contiguous. On the other hand, the following heap has less free memory but it's not fragmented:

 
1111111111000000

What can you do to avoid heap fragmentation? First of all, use dynamic memory as little as possible. In most cases, you can use static or automatic storage instead of allocating objects dynamically. Secondly, try to allocate large chunks rather than small ones. For example, instead of allocating a single object, allocate an array of objects at once, and use these objects when they are needed. If all these tips don't solve the fragmentation problem, you should consider building a custom memory pool.

Understanding What Memory Alignment Means

Most CPUs require that objects and variables reside at particular offsets in the system's memory. For example, 32-bit processors require a 4-byte integer to reside at a memory address that is evenly divisible by 4. This requirement is called "memory alignment". Thus, a 4-byte int can be located at memory address 0x2000 or 0x2004, but not at 0x2001. On most Unix systems, an attempt to use misaligned data results in a bus error, which terminates the program altogether. On Intel processors, the use of misaligned data is supported but at a substantial performance penalty. Therefore, most compilers automatically align data variables according to their type and the particular processor being used. This is why the size that structs and classes occupy is often larger than the sum of their members' size:

 
struct Employee
{
  int ID;
  char state[3]; //CA, NY etc. + terminating null
  int salary;
};

Apparently, Employee should occupy 11 bytes (4+3+4). However, most compilers add an unused padding byte after the field 'state' so that it aligns on a 4 byte boundary. Consequently, Employee occupies 12 bytes rather than 11. You can examine the actual size of an aggregate by using the expression sizeof(Employee).

:: Operator Should not be Used to Designate a Global Function

In some frameworks (MFC, for instance), it's customary to add the scope resolution operator :: before a global function's name to mark it explicitly as a function that is not a class member.

 
void String::operator = (const String& other) 
{
 ::strcpy (this->buffer, &other); // strcpy is preceded by :: operator, not a good idea
}

This practice is not recommended anymore. Many of the standard functions that used to be global are now grouped under namespaces. For example, strcpy() now belongs to namespace std, and so are most of the Standard Library's functions. Putting the scope resolution operator before them will stymie the lookup algorithm of the compiler, resulting in compilation errors. Therefore, it's advisable to leave the function's name without the scope resolution operator.

A const member function

Whenever you define a class member function which does not (and should not) change its object, it's a good idea to define it as a const member function. There are two advantages to that: One, you guarantee that this member function is safe to use, because it does not change the state of its objects (i.e, it may not assign new values to members, reallocate memory or activate the object’s destructor. Two, you improve readability: even without browsing the source code the user can get a clearer idea of the implementor’s intention. For example (one declaration and one definition of const member function shown):

 class Person {
               int age;
               long social_security_n;
               ...
               //mutators a.k.a “setters” change their object’s state
 
               void setAge (int Age);
               void setID(long ssn) { social_security_n = ssn; }
 
               //accessors a.k.a “getters” may not change their object
 
               int getAge () const; //does not modify its object
               long getSocial_security_n () const {return social_security_n;}
};

Inheritance and a Reference to a Base Pointer

A reader posted this question on one of the C++ newsgroups. Assuming B is a base class for D, his program looks like this:

 
  void g (B* p) ;
  void f (B*& p); // modifies p
 
  int main ()
  {
    D* p = NULL ;
    g (p) ;  // fine
    f (p) ;  /* error: "cannot convert parameter 1 from 'class D *' to 
                   'class B *& ' a reference that is not to 'const' cannot 
                   be bound to a non-lvalue" */
  }

Function g() works as expected, but f() causes a compilation error. The reader wondered what was wrong with the invocation of f() in main(). Can you see what is wrong with it? p is a D*, not a B*, and to convert it to a B*, the implementation creates a temporary pointer (recall that a reference must be bound to a valid object; in this case, a pointer). Now because temporaries are rvalues, and you can't bind an rvalue to a non-const reference, the compiler complains. Declaring f() as follows:

 
  void f (D* & p) { /* modifies p */ }

solves this problem.

 

No comments: