Disadvantage of C++ Templates

What is the disadvantage of a template function?

A template function cannot be distributed in the obj form. This is because, the parameters with which the template function is going to be called is decided at the run time only. Therefore an obj form of a template function cannot be made by merely compiling it.

But templates have a few negative aspects that are not widely explored. First, since C++ does not have binary run-time extensibility, templates can't be linked and distributed as a library. They must be compiled at compile time, and, therefore, all implementations of a template algorithm must be included in the header files in their entirety. You can easily see this by analyzing the STL standard header files.

----
Both macros and templates are expanded at compile time. Macros are always expanded inline; templates can also be expanded as inline functions when the compiler deems it appropriate. Thus both function-like macros and function templates have no run-time overhead.
However, templates are generally considered an improvement over macros for these purposes. Templates are type-safe. Templates avoid some of the common errors found in code that makes heavy use of function-like macros. Perhaps most importantly, templates were designed to be applicable to much larger problems than macros. The definition of a function-like macro must fit on a single logical line of code.
There are three primary drawbacks to the use of templates. First, many compilers historically have very poor support for templates, so the use of templates can make code somewhat less portable. Second, almost all compilers produce confusing, unhelpful error messages when errors are detected in template code. This can make templates difficult to develop. Third, each use of a template may cause the compiler to generate extra code (an instantiation of the template), so the indiscriminate use of templates can lead to code bloat, resulting in excessively large executables.
The other big disadvantage of templates is that to replace a #define like max which acts identically with dissimilar types or function calls is impossible. Templates have replaced using #defines for complex functions but not for simple stuff like max(a,b). For a full discussion on trying to create a template for the #define max, see the paper "Min, Max and More" that Scott Meyer wrote for C++ Report in January 1995.
The biggest advantage of using templates, is that a complex algorithm can have a simple interface that the compiler then uses to choose the correct implementation based on the type of the arguments. For instance, a searching algorithm can take advantage of the properties of the container being searched. This technique is used throughout the C++ standard library.

----

The biggest advantage of using templates, is that a complex algorithm can have a simple interface that the compiler then uses to choose the correct implementation based on the type of the arguments.

inline virtual function?

http://msdn.microsoft.com/en-us/magazine/cc301407.aspx

Inline Virtual Functions, AVI Files in EXEs, and the DynPrompt Sample App
Paul DiLascia
Code for this article: CQA0600.exe (47KB)
Q How does C++ handle inline virtual functions? When a function is inline and virtual, will code substitution take place or is the call resolved using the vtable?
G.N. Rajagopal
A The answer is, it depends. To see why, let's consider each caseâ€"inline and virtualâ€"separately. Normally, an inline function is expanded, well, inline.
class CFoo {
private:
int val;
public:
int GetVal() { return val; }
int SetVal(int v) { return val=v; }
};
In this situation, if you write
CFoo x;
x.SetVal(17);
int y = x.GetVal();
then the compiler generates the code as if you'd written:
CFoo x;
x.val = 17;
int y = x.val;
Of course you can't do this because val is private. Inline functions give you the advantage of data hiding without paying the price of a function call. So much for inline functions. Virtual functions give you polymorphism, which means derived classes can implement the same function differently. Suppose GetVal is now declared virtual and you have a second class, CFoo2, with a different implementation:
class CFoo2 : public CFoo {
public:
// virtual in base class too!
virtual int CFoo2::GetVal() {
return someOtherVal;
}
};
If pFoo is a pointer to a CFoo or CFoo2, then pFoo->GetVal will call the member function for whichever class pFoo really points toâ€"CFoo or CFoo2. This is C++ 101, and you should know it like the back of your hand. But what happens if a function is both virtual and inline? Remember, there are two ways to make a function inline: by using the inline keyword in the function definition, as in
inline CFoo::GetVal() { return val; }
or by coding the function body inline within the class declaration, as in the previous CFoo2::GetVal example. So if you include the body of your virtual function within the class declaration
class CFoo {
public:
virtual int GetVal() { return val; }
};
then you are telling the compiler you want GetVal to be both inline and virtual. This doesn't seem to make sense, for how can polymorphism work if the function is expanded inline? The answer, of course, is that it can't. Or can it? The first rule the compiler follows when it encounters such a beast is this: whatever happens, polymorphism must work. If you have a pointer to a CFoo object, then pFoo->GetVal is guaranteed to call the right function. In general, this means the GetVal functions will be instantiated as real (noninline) functions, with vtable entries pointing to them. But that doesn't mean the function can't ever be expanded! Consider this code again:
CFoo x;
x.SetVal(17);
int y = x.GetVal();
The compiler knows that x is really a CFoo, not a CFoo2, since the stack object is explicitly declared. There's no way x could really be a CFoo2. So it's safe to expand SetVal/GetVal inline. If you write this more complex code
CFoo x;
CFoo* pfoo=&x;
pfoo->SetVal(17);
int y = pfoo->GetVal();
���
CFoo2 x2;
pfoo = &x2;
pfoo->SetVal(17); //etc.
the compiler knows that pfoo points to x the first time and x2 the second time, so again it's safe to expand the virtual functions. You can dream up ever more complex examples, where the type of object pfoo points to is always known, but most compilers won't do any heavy analysis. Even in the preceding example, some compilers will do the safe thing, which is to instantiate the function and call through a vtable. Indeed, the compiler is free to ignore the inline requirement and always use the vtable. The only absolute rule is that the code must work; that is, virtual functions must behave polymorphically. In general, inlineâ€"whether explicit or implicitâ€"is a hint, not a mandate, just like register. (Does anyone remember register? It asks the compiler to use a machine register for a variable if it can.) The compiler can refuse to expand even a nonvirtual inline function if it wants to, and the first C++ compilers often complained, "inline abortedâ€"function too big." Certainly if an inline function calls itself, or if you pass its address somewhere, the compiler must generate a normal (outline?) function. And, of course, inline functions are not expanded in debug builds, or if you set a compiler option preventing it. The only way to really know what your compiler is doing is to look at the code it generates. For the Microsoft® compiler, you can compile with -FA to generate an assembly listing. You don't need to be an assembler jock to know what's going on. I encourage you to perform this experiment; it's good for the soul to see what the machine is actually doing, and you can learn a lot poking around assembly listings. For now, I'll spare you that agony. The topic of inline functions is more complex than you might think at first. There are many circumstances that force the compiler to generate a normal function: recursion, taking the address of your function, functions that are too big, and virtual functions.

Here's another consideration: if the compiler decides to instantiate your inline function, where does it put the function? Which module does it go into? Usually, classes are declared in header (.h) files. So if mumble.cpp includes foo.h and the compiler decides it has to instantiate CFoo:: GetVal, it will instantiate it as a static function in mumble.cpp. If 10 modules include foo.h, the compiler could generate up to 10 copies of your virtual function. In fact, you could end up with objects of the same type with vtables pointing to different copies of GetVal. Yuk! Some linkers are smart enough to eliminate the redundancies at link time, but in general you can't be sure. So the bottom line is: it's best not to use inline virtual functions, since they're almost never expanded anyway. Even if your function is just one line, you're better off putting it in the module (.cpp file) along with the other class functions. Of course, programmers often put short virtual functions in the class declarationâ€"not because they expect the function to be expanded inline, but because it's more convenient and readable.

http://www.parashift.com/c++-faq-lite/value-vs-ref-semantics.html#faq-31.6

[31.6] Are "inline virtual" member functions ever actually "inlined"?
Occasionally...
When the object is referenced via a pointer or a reference, a call to a virtual function cannot be inlined, since the call must be resolved dynamically. Reason: the compiler can't know which actual code to call until run-time (i.e., dynamically), since the code may be from a derived class that was created after the caller was compiled.
Therefore the only time an inline virtual call can be inlined is when the compiler knows the "exact class" of the object which is the target of the virtual function call. This can happen only when the compiler has an actual object rather than a pointer or reference to an object. I.e., either with a local object, a global/static object, or a fully contained object inside a composite.
Note that the difference between inlining and non-inlining is normally much more significant than the difference between a regular function call and a virtual function call. For example, the difference between a regular function call and a virtual function call is often just two extra memory references, but the difference between an inline function and a non-inline function can be as much as an order of magnitude (for zillions of calls to insignificant member functions, loss of inlining virtual functions can result in 25X speed degradation! [Doug Lea, "Customization in C++," proc Usenix C++ 1990]).
A practical consequence of this insight: don't get bogged down in the endless debates (or sales tactics!) of compiler/language vendors who compare the cost of a virtual function call on their language/compiler with the same on another language/compiler. Such comparisons are largely meaningless when compared with the ability of the language/compiler to "inline expand" member function calls. I.e., many language implementation vendors make a big stink about how good their dispatch strategy is, but if these implementations don't inline member function calls, the overall system performance would be poor, since it is inlining —not dispatching— that has the greatest performance impact.

virtual constructor

An idiom that allows you to do something that C++ doesn't directly support.

You can get the effect of a virtual constructor by a virtual clone() member function (for copy constructing), or a virtual create() member function (for the default constructor).

class Shape {
public:
virtual ~Shape() { } // A virtual destructor
virtual void draw() = 0; // A pure virtual function
virtual void move() = 0;
...
virtual Shape* clone() const = 0; // Uses the copy constructor
virtual Shape* create() const = 0; // Uses the default constructor
};

class Circle : public Shape {
public:
Circle* clone() const; // Covariant Return Types; see below
Circle* create() const; // Covariant Return Types; see below
...
};

Circle* Circle::clone() const { return new Circle(*this); }
Circle* Circle::create() const { return new Circle(); }

In the clone() member function, the new Circle(*this) code calls Circle's copy constructor to copy the state of this into the newly created Circle object. (Note: unless Circle is known to be final (AKA a leaf), you can reduce the chance of slicing by making its copy constructor protected.) In the create() member function, the new Circle() code calls Circle's default constructor.

Users use these as if they were "virtual constructors":

void userCode(Shape& s)
{
Shape* s2 = s.clone();
Shape* s3 = s.create();
...
delete s2; // You need a virtual destructor here
delete s3;
}

This function will work correctly regardless of whether the Shape is a Circle, Square, or some other kind-of Shape that doesn't even exist yet.

Note: The return type of Circle's clone() member function is intentionally different from the return type of Shape's clone() member function. This is called Covariant Return Types, a feature that was not originally part of the language. If your compiler complains at the declaration of Circle* clone() const within class Circle (e.g., saying "The return type is different" or "The member function's type differs from the base class virtual function by return type alone"), you have an old compiler and you'll have to change the return type to Shape*.

Note: If you are using Microsoft Visual C++ 6.0, you need to change the return types in the derived classes to Shape*. This is because MS VC++ 6.0 does not support this feature of the language. Please do not write me about this; the above code is correct with respect to the C++ Standard (see 10.3p5); the problem is with MS VC++ 6.0. Fortunately covariant return types are properly supported by MS VC++ 7.0.

Reference:

http://www.parashift.com/c++-faq-lite/virtual-functions.html#faq-20.8

Factory Pattern (a.k.a. virtual constructor)

Factory Method helps to model an interface for creating an object which at creation time can let its subclasses decide which class to instantiate. We call this a Factory Pattern since it is responsible for "Manufacturing" an Object. It helps instantiate the appropriate Subclass by creating the right Object from a group of related classes. The Factory Pattern promotes loose coupling by eliminating the need to bind application-specific classes into the code.

The Factory Pattern is all about "Define an interface for creating an object, but let the subclasses decide which class to instantiate. The Factory method lets a class defer instantiation to subclasses" Thus, as defined by Gamma et al, "The Factory Method lets a class defer instantiation to subclasses".

This pattern is used when a class (the Creator) does not know beforehand all the subclasses that it will create.

* Factory methods are common in toolkits and frameworks where library code needs to create objects of types which may be subclassed by applications using the framework.
* Parallel class hierarchies often require objects from one hierarchy to be able to create appropriate objects from another.

Example: (http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Virtual_Constructor)

class Employee
{
public:
  virtual ~Employee () {}                 // Native support for polymorphic destruction.
  virtual Employee * create () const = 0; // Virtual constructor (creation) 
  virtual Employee * clone () const = 0;  // Virtual constructor (copying) 
};
class Manager : public Employee     // "is-a" relationship
{
public:
  Manager ();                     // Default constructor
  Manager (Manager const &);      // Copy constructor
  ~Manager () {}                  // Destructor
  Manager * create () const       // Virtual constructor (creation) 
  {
    return new Manager();
  }
  Manager * clone () const        // Virtual constructor (copying) 
  {
    return new Manager (*this);
  }
};
class Programmer : public Employee { /* Very similar to the Manager class */ };
Employee * duplicate (Employee const & e)
{
 return e.clone();  // Using virtual constructor idiom.
}

More effective c++ Item 25

Because the function creates new objects, it acts much like a constructor, but because it can create different types of objects, we call it a virtual constructor. A virtual constructor is a function that creates different types of objects depending on the input it is given. Virtual constructors are useful in many contexts, only one of which is reading object information from disk (or off a network connection or from a tape).

A particular kind of virtual constructor — the virtual copy constructor — is also widely useful. A virtual copy constructor returns a pointer to a new copy of the object invoking the function.

etc.).

References:

http://gsraj.tripod.com/design/creational/factory/factory.html
http://en.wikipedia.org/wiki/Factory_method_pattern

C++ Concepts

Abstract classes v.s Interfaces
1. Abstract classes CANNOT be instantiated and only instances of concrete subclasses can be created.
2. An interface has no data members and no method definitions (only pure virtual functions)


C++ v.s Java v.s C#
1. C++ has no garbage collection and supports multiple inheritance
2. Default C++ & C# methods are nonvirtual, Nonstatic Java methods are virtual

system call

Abbreviations

PTO: Paid Time Off

OOTO: Out Of The Office

Binary Search Tree

1. Design an algorithm and write code to find the common ancestor of two nodes in a tree

Linked list

1. Check if there is a common node in 2 linked lists.

Solution: All we need to do is to first calculate len=len1-len2 (len1>len2, as discussed above). Point p1 and p2 to list1 (the longer one) and list2 respectively. Then step only p1 for "len" no. of nodes. After this we are guaranteed that p1 and p2 are equidistant from the common node. So now start stepping p1 and p2 simultaneously until p1==p2. This will the common node. This is a simple O(n) solution.

private destructor, virtual constructor