Virtual Function

A virtual function is a member function of a class, whose functionality can be over-ridden in its derived classes. It is one that is declared as virtual in the base class using the virtual keyword. The virtual nature is inherited in the subsequent derived classes and the virtual keyword need not be re-stated there. The whole function body can be replaced with a new set of implementation in the derived class.

Late Binding

In some programs, it is not possible to know which function will be called until runtime (when the program is run). This is known as late binding (or dynamic binding).

In C++, one way to get late binding is to use function pointers. To review function pointers briefly, a function pointer is a type of pointer that points to a function instead of a variable.

The function that a function pointer points to can be called by using the function call operator (()) on the pointer.

int Add(int nX, int nY)

{return nX + nY;
}
int main()
{// Create a function pointer and make it point to the Add function
    int (*pFcn)(int, int) = Add;
   cout << pFcn(5, 3) << endl; // add 5 + 3
    return 0;
}

Calling a function via a function pointer is also known as an indirect function call.

The following calculator program is functionally identical to the calculator example above, except it uses a function pointer instead of a direct function call

#include <iostream>

using namespace std;
int Add(int nX, int nY)
{return nX + nY;
}
int Subtract(int nX, int nY)
{return nX - nY;
}
int Multiply(int nX, int nY)
{return nX * nY;
}
int main()
{int nX;
cout << "Enter a number: ";
cin >> nX;
int nY;
cout << "Enter another number: ";
cin >> nY;
int nOperation;
do
{
cout << "Enter an operation (0=add, 1=subtract, 2=multiply): ";
cin >> nOperation;
} while (nOperation < 0 ||nOperation > 2);

// Create a function pointer named pFcn (yes, the syntax is ugly)
int (*pFcn)(int, int);
// Set pFcn to point to the function the user chose
switch (nOperation)
{
case 0: pFcn = Add; break;
case 1: pFcn = Subtract; break;
case 2: pFcn = Multiply; break;
}
// Call the function that pFcn is pointing to with nX and nY as parameters

cout << "The answer is: " << pFcn(nX, nY) << endl;
return 0;
}

In this example, instead of calling the Add(), Subtract(), or Multiply() function directly, we’ve instead set pFcn to point at the function we wish to call. Then we call the function through the pointer. The compiler is unable to use early binding to resolve the function call pFcn(nX, nY) because it can not tell which function pFcn will be pointing to at compile time!

Late binding is slightly less efficient since it involves an extra level of indirection. With early binding, the compiler can tell the CPU to jump directly to the function’s address. With late binding, the program has to read the address held in the pointer and then jump to that address. This involves one extra step, making it slightly slower. However, the advantage of late binding is that it is more flexible than early binding, because decisions about what function to call do not need to be made until run time.

In Short
Whenever a program has a virtual function declared, a v - table is constructed for the class. The v-table consists of addresses to the virtual functions forclasses that contain one or more virtual functions.

The object of the class containing the virtual function contains a virtual pointer that points to the base address of the virtual table in memory. Whenever there is a virtual function call, the v-table is used to resolve to the function address.

An object of the class that contains one or more virtual functions contains a virtual pointer called the vptr at the very beginning of the object in the memory. Hence the size of the object in this case increases by the size of the pointer.

This vptr containsthe base address of the virtual table in memory. Note that virtual tables are class specific, i.e., there is only one virtual table for a class irrespective of the number of virtual functions it contains.

This virtual table in turn containsthe base addresses of one or more virtual functions of the class. At the time when a virtual function is called on an object, the vptr of that object provides the base address of the virtual table for that class in memory.

So complier generate the code to extract first two bytes of the object whose address is stored in the pointer
(i.e p =&d)  This gives the address of the VTABLE. The complier also adds a number to this address.

This number is actually an offset in VTABLE. we determine the call.

This table is used to resolve the function call as it contains the addresses of all the virtual functions of that class. This is how dynamic binding is resolved during a virtual function call.

In detail
The virtual table is actually quite simple, though it’s a little complex to describe in words. First, every class
that uses virtual functions (or is derived from a class that uses virtual functions) is given it’s own virtual table.

This table is simply a static array that the compiler sets up at compile time. A virtual table contains one entry for each virtual function that can be called by objects of the class. Each entry in this table is simply a function pointer that points to the most-derived function accessible by that class.

Second, the compiler also adds a hidden pointer to the base class, which we will call *__vptr. *__vptr is set (automatically) when a class instance is created so that it points to the virtual table for that class.

Unlike the *this pointer, which is actually a function parameter used by the compiler to resolve self-references, *__vptr is a real pointer. Consequently, it makes each class object allocated bigger by the size of one pointer.
It also means that *__vptr is inherited by derived classes, which is important.

Ex..

class Base

{
public:
virtual void function1() {};
virtual void function2() {};
};

class D1: public Base
{
public:
virtual void function1() {};
};

class D2: public Base
{
public:
virtual void function2() {};
};

Because there are 3 classes here, the compiler will set up 3 virtual tables: one for Base, one for D1, and one for D2
 
The compiler also adds a hidden pointer to the most base class that uses virtual functions. Although the compiler does this automatically, we’ll put it in the next example just to show where it’s added
 
class Base


{
public:
FunctionPointer *__vptr;
virtual void function1() {};
virtual void function2() {};
};

class D1: public Base
{
public:
virtual void function1() {};
};

class D2: public Base
{
public:
virtual void function2() {};
};

When a class object is created, *__vptr is set to point to the virtual table for that class. For example, when a object of type Base is created, *__vptr is set to point to the virtual table for Base. When objects of type D1 or D2 are constructed, *__vptr is set to point to the virtual table for D1 or D2 respectively.
 
Now, let’s talk about how these virtual tables are filled out. Because there are only two virtual functions here, each virtual table will have two entries (one for function1(), and one for function2()). Remember that when these virtual tables are filled out, each entry is filled out with the most-derived function an object of that class type can call.
 
Base’s virtual table is simple. An object of type Base can only access the members of Base. Base has no access to D1 or D2 functions. Consequently, the entry for function1 points to Base::function1(), and the entry for function2 points to Base::function2().
 
D1’s virtual table is slightly more complex. An object of type D1 can access members of both D1 and Base. However, D1 has overridden function1(), making D1::function1() more derived than Base::function1(). Consequently, the entry for function1 points to D1::function1(). D1 hasn’t overridden function2(), so the entry for function2 will point to Base::function2().
 
D2’s virtual table is similar to D1, except the entry for function1 points to Base::function1(), and the entry for function2 points to D2::function2().

  consider what happens when we create an object of type D1:

int main()

{
D1 cClass;
}

Because cClass is a D1 object, cClass has it’s *__vptr set to the D1 virtual table.

Now, let’s set a base pointer to D1:

int main()

{
D1 cClass;
Base *pClass = &cClass;
}

Note that because pClass is a base pointer, it only points to the Base portion of cClass. However, also note that *__vptr is in the Base portion of the class, so pClass has access to this pointer. Finally, note that pClass->__vptr points to the D1 virtual table! Consequently, even though pClass is of type Base, it still has access to D1’s virtual table.
 
So what happens when we try to call pClass->function1()?
 
int main()

{
D1 cClass;
Base *pClass = &cClass;
pClass->function1();
}

First, the program recognizes that function1() is a virtual function. Second, uses pClass->__vptr to get to D1’s virtual table. Third, it looks up which version of function1() to call in D1’s virtual table. This has been set to D1::function1(). Therefore, pClass->function1() resolves to D1::function1()!
 
Now, you might be saying, “But what if Base really pointed to a Base object instead of a D1 object. Would it still call D1::function1()?”. The answer is no.

int main()


{
Base cClass;
Base *pClass = &cClass;
pClass->function1();
}

In this case, when cClass is created, __vptr points to Base’s virtual table, not D1’s virtual table. Consequently, pClass->__vptr will also be pointing to Base’s virtual table. Base’s virtual table entry for function1() points to Base::function1(). Thus, pClass->function1() resolves to Base::function1(), which is the most-derived version of function1() that a Base object should be able to call.
 
By using these tables, the compiler and program are able to ensure function calls resolve to the appropriate virtual function, even if you’re only using a pointer or reference to a base class!
 
Calling a virtual function is slower than calling a non-virtual function for a couple of reasons: First, we have to use the *__vptr to get to the appropriate virtual table. Second, we have to index the virtual table to find the correct function to call. Only then can we call the function. As a result, we have to do 3 operations to find the function to call, as opposed to 2 operations for a normal indirect function call, or one operation for a direct function call. However, with modern computers, this added time is usually fairly insignificant

Function overloading

Function overloading is a feature of C++ that allows us to create multiple functions with the same name, so long as they have different parameters. Consider the following function:

int Add(int nX, int nY)
{
    return nX + nY;
} 

This trivial function adds two integers.  However, what if we also need 
to add two floating point numbers?  This function is not at all 
suitable, as any floating point parameters would be converted to 
integers, causing the floating point arguments to lose their fractional 
values.

 int AddI(int nX, int nY)
{
    return nX + nY;
}

double AddD(double dX, double dY)
{
    return dX + dY;
} 

However, for best effect, this requires that you define a consistent naming standard, remember the name of all the different flavors of the function, and call the correct one (calling AddD() with integer parameters may produce the wrong result due to precision issues).
Function overloading provides a better solution. Using function overloading, we can declare another Add() function that takes double parameters:

double Add(double dX, double dY)
{
    return dX + dY;
} 

We now have two version of Add():

int Add(int nX, int nY); // integer version
double Add(double dX, double dY); // floating point version 

Which version of Add() gets called depends on the arguments used in the call — if we provide two ints, C++ will know we mean to call Add(int, int). If we provide two floating point numbers, C++ will know we mean to call Add(double, double). In fact, we can define as many overloaded Add() functions as we want, so long as each Add() function has unique parameters.
Consequently, it’s also possible to define Add() functions with a differing number of parameters:

int Add(int nX, int nY, int nZ)
{
    return nX + nY + nZ;
} 

Even though this Add() function has 3 parameters instead of 2, because the parameters are different than any other version of Add(), this is valid.

Note that the function’s return type is NOT considered when overloading functions. Consider the case where you want to write a function that returns a random number, but you need a version that will return an int, and another version that will return a double. You might be tempted to do this:

int GetRandomValue();
double GetRandomValue();

But the compiler will flag this as an error. These two functions have the same parameters (none), and consequently, the second GetRandomValue() will be treated as an erroneous redeclaration of the first.

Consequently, these functions will need to be given different names.

Also keep in mind that declaring a typedef does not introduce a new type — consequently, the following the two declarations of Print() are considered identical:

typedef char *string;
void Print(string szValue);
void Print(char *szValue); 

How function calls are matched with overloaded functions

Making a call to an overloaded function results in one of three possible outcomes:

1) A match is found.  The call is resolved to a particular overloaded function.

2)No match is found. The arguments can not be matched to any overloaded function.

3)An ambiguous match is found. The arguments matched more than one overloaded function.

When an overloaded function is called, C++ goes through the following 
process to determine which version of the function will be called

1) First, C++ tries to find an exact match.  This is the case where the 
actual argument exactly matches the parameter type of one of the 
overloaded functions.  For example:

void Print(char *szValue);
void Print(int nValue);

Print(0); // exact match with Print(int) 

Although 0 could technically match Print(char*), it exactly matches Print(int). 

Thus Print(int) is the best match available.

2) If no exact match is found, C++ tries to find a match through promotion

   Char, unsigned char, and short is promoted to an int.

   Unsigned short can be promoted to int or unsigned int, depending on the size of an int

  Float is promoted to double

    Enum is promoted to int

    void Print(char *szValue);
    void Print(int nValue);
    Print('a'); // promoted to match Print(int)
   
   In this case, because there is no Print(char), the char ‘a’ is promoted to an integer, which then matches  Print(int).

3) If no promotion is found, C++ tries to find a match through standard conversion. Standard conversions include:
Any numeric type will match any other numeric type, including unsigned (eg. int to float)

Enum will match the formal type of a numeric type (eg. enum to float)

Zero will match a pointer type and numeric type (eg. 0 to char*, or 0 to float)

A pointer will match a void pointer


void Print(float fValue);
void Print(struct sValue);

Print('a'); // promoted to match Print(float)

Note that all standard conversions are considered equal.
No standard conversion is considered better than any of the others
 
Finally, C++ tries to find a match through user-defined conversion. Although we have not covered classes yet, classes (which are similar to structs) can define conversions to other types that can be implicitly applied to objects of that class. For example, we might define a class X and a user-defined conversion to int.

class X; // with user-defined conversion to int

void Print(float fValue);
void Print(int nValue);

X cValue; // declare a variable named cValue of type class X
Print(cValue); // cValue will be converted to an int and matched to Print(int)

  Function Pointer

• http://www.codeproject.com/KB/cpp/FastDelegate.aspx

 virtual table structure in pure virtual function case 

• http://social.msdn.microsoft.com/Forums/en-US/vcgeneral/thread/04f374ae-0b58-463c-a742-a2de02d4caa1

virtual function FAQ

• https://isocpp.org/wiki/faq/virtual-functions

some more FAQ about virtual

• http://social.msdn.microsoft.com/Forums/en-US/vclanguage/thread/7c20d210-d7ba-4362-9050-06f6e6e92093/

size of class object

• http://www.cprogramming.com/tutorial/size_of_class_object.html

1. Where the virtual table reside into memory

• http://stackoverflow.com/questions/10387691/where-is-the-virtual-function-table-for-c-class-stored
•  http://stackoverflow.com/questions/1905237/where-in-memory-is-vtable-stored

2. what will happen if we have virtual keyword in derived class

• if you not have define virtual function in base class and define into derive class than virtual functionality does not work
• http://stackoverflow.com/questions/4895294/c-virtual-keyword-for-functions-in-derived-classes-is-it-necessary

3. where vpointer will reside into memory/ vptr location

•  vpointer is part of object
• http://stackoverflow.com/questions/706861/where-does-intel-c-compiler-store-the-vptr-pointer-to-virtual-function-table
•  

 The precise location of the vptr (the pointer to the class's   
 table of virtual functions' addresses) is implementation-  
 dependent. Some compilers, e.g., Visual C++ and C++   
 Builder, place it offset 0, before the user-declared data   
 members. Other compilers, such as GCC and DEC   
 CXX, place the vptr at the end of the class,   
 after all the user-declared data members. Normally,   
 you wouldn't care about the vptr's position. However, under   
 certain conditions, for example, in applications that dump   
 an object's content to a file so that it can be retrieved   
 afterwards, the vptr's position matters.   
 To detect it, first take the address of an object that.   
 Then compare it to the address of the first data member of   
 that object. If the two addresses are identical, it's likely   
 that the vptr is located at the end. If, however, the   
 member's address is higher than the object's address,   
 this means that the vptr is located at the object's   
 beginning. To detect where your compiler places the vptr,   
 run the following program:  
 class A  
 {  
 public:  
  virtual void f() {}  
  int n;  
 };  
 int main()  
 {  
  A a;  
  char *p1=reinterpret_cast <char *> (&a);  
  char *p2=reinterpret_cast <char *> (&a.n);  
  if (p1==p2)  
  cout<<"vptr is located at the object's   
 end"<<endl;  
  else  
  cout<<"vptr is located at the object's   
 beginning"<<endl;  
 }  

5 . vpointer inherited into the inheritance

• http://stackoverflow.com/questions/7594593/resolving-of-vptr  

6. what  is pure virtual function/abstract class

• http://www.learncpp.com/cpp-tutorial/126-pure-virtual-functions-abstract-base-classes-and-interface-classes/
• http://www.learncpp.com/cpp-tutorial/126-pure-virtual-functions-abstract-base-classes-and-interface-classes/
•  http://www.gotw.ca/gotw/031.htm

8. if we create a object of abstract class will we get compile time error or run time error.

• compile time error

9. can we create a pointer of abstract class

• Yes

10.  static binding vs dynamic binding

• Refer 3 question

11. what is Vtable

• Refer 2 question 

12. Can you tell me where the V table reside into the compile.

• Refer above question 

13. Can you show the address of Vtable.

• Refer above question

 14. Can Pure virtual function contain the Vtable.

• Yes

15. how does Vtable contain the function order for the base and derived class.

• In base class, The function is defined in same way
• In derived class, derive class first and than base class

16. Vtable works

• Refer above question

17. what isVptr

• Refer above question

18. Does vptr depend  on the class /object

• each class contain vptr and inherited into derive class
• vptr is a part of object

19. How many vptr will create if you have three object of the class

• One vptr

20. Does vptr inherited into derive class

• Yes

21. what is virtual destructor/need of virtual destructor

• http://www.programmerinterview.com/index.php/c-cplusplus/virtual-destructors/
•  http://stackoverflow.com/questions/7750280/how-does-virtual-destructor-work-in-c
•  http://www.geeksforgeeks.org/pure-virtual-destructor-c/

22.  virtual destructor Example

 class sample  
 {  
   public:  
   virtual void fun();  
   virtual ~sample()  
 };  
 class der : public sample  
 {  
   public:  
   ~der();  
   void fun();  
 };  
 int main()  
 {  
    sample *p = new derived;  
    delete p;  
 }  
 so it is call the derived class destructor  

22. what is virtual base class/need of virtual class

• http://www.learncpp.com/cpp-tutorial/118-virtual-base-classes/
•  https://isocpp.org/wiki/faq/multiple-inheritance
• http://stackoverflow.com/questions/21558/in-c-what-is-a-virtual-base-class

23. what is memory layout of the virtual base class

• http://www.phpcompiler.org/articles/virtualinheritance.html (Need to look again).

24. what is diamond shape problem in case of virtual function.

• Refer above

25. what is object slicing/need of object slicing

• http://www.geeksforgeeks.org/object-slicing-in-c/
•  http://stackoverflow.com/questions/274626/what-is-object-slicing#274636
• http://www.bogotobogo.com/cplusplus/slicing.php

27. can we declare a static function as virtual

28. is it necessary that we should override virtual function

29. Pure virtual function can never a body

30. Does virtual function mechanism work in cosntructor

31, if we do not over ride virtual function in the derived class than will derived class become abstract class.

32. Does  derived class has access to private data member of base

33. Can you base class function from the derived class.

34. what is dreaded diamond

35.what are the access rule  in terms of inheritance. i mean in terms of accessing of variable.

36.  what is final class
       1) make a constructor as private (static function can create a object)

       2) make a destructor as private


      3) 
       class temp
       {
            private:
             ~temp();
             friend final_class;
         };
         class final_class : public virtual temp
         {
               
           }

37.  virtual table unresolved error.
       
       we should define the in the virtual class

38. Does vtable create in the case of pure  virtual function.


39. What is upcasting

40 . what is downcasting.

41. Display VTABLE

• how-to-display-the-vtable-of-a-c-class-through-gcc

C++ FAQ

1. Stack Memory Vs Heap Memory
The heap


The heap (also known as the “free store”) is a large pool of memory used for dynamic allocation. In C++, when you use the new operator to allocate memory, this memory is assigned from the heap.
view source
print?

int *pValue = new int; // pValue is assigned 4 bytes from the heap
int *pArray = new int[10]; // pArray is assigned 40 bytes from the heap

Because the precise location of the memory allocated is not known in advance, the memory allocated has to be accessed indirectly — which is why new returns a pointer.

You do not have to worry about the mechanics behind the process of how free memory is located and allocated to the user. However, it is worth knowing that sequential memory requests may not result in sequential memory addresses being allocated!
view source

int *pValue1 = new int;
int *pValue2 = new int;
// pValue1 and pValue2 may not have sequential addresses

When a dynamically allocated variable is deleted, the memory is “returned” to the heap and can then be reassigned as future allocation requests are received.

The heap has advantages and disadvantages:

1) Allocated memory stays allocated until it is specifically deallocated (beware memory leaks).
2) Dynamically allocated memory must be accessed through a pointer.
3) Because the heap is a big pool of memory, large arrays, structures, or classes should be allocated here.

The stack

The call stack (usually referred to as “the stack”) has a much more interesting role to play. Before we talk about the call stack, which refers to a particular portion of memory, let’s talk about what a stack is.

Consider a stack of plates in a cafeteria. Because each plate is heavy and they are stacked, you can really only do one of three things:

1) Look at the surface of the top plate

2) Take the top plate off the stack

3) Put a new plate on top of the stack

In computer programming, a stack is a container that holds other variables (much like an array).

However, whereas an array lets you access and modify elements in any order you wish, a stack is more limited. The operations that can be performed on a stack are identical to the ones above:

1) Look at the top item on the stack (usually done via a function called top())

2) Take the top item off of the stack (done via a function called pop())

3) Put a new item on top of the stack (done via a function called push())

A stack is a last-in, first-out (LIFO) structure. The last item pushed onto the stack will be the first item popped off. If you put a new plate on top of the stack,

anybody who takes a plate from the stack will take the plate you just pushed on first. Last on, first off. As items are pushed onto a stack, the stack grows larger — as items are popped off, the stack grows smaller.

The plate analogy is a pretty good analogy as to how the call stack works, but we can actually make an even better analogy. Consider a bunch of mailboxes, all stacked on top of each other.

Each mailbox can only hold one item, and all mailboxes start out empty. Furthermore, each mailbox is nailed to the mailbox below it, so the number of mailboxes can not be changed. If we can’t change the number of mailboxes, how do we get a stack-like behavior?

First, we use a marker (like a post-it note) to keep track of where the bottom-most empty mailbox is.

In the beginning, this will be the lowest mailbox. When we push an item onto our mailbox stack, we put it in the mailbox that is marked (which is the first empty mailbox), and move the marker up one mailbox. When we pop an item off the stack, we move the marker down one mailbox and remove the item from that mailbox. Anything below the marker is considered “on the stack”. Anything at the marker or above the marker is not on the stack.

This is almost exactly analogous to how the call stack works. The call stack is a fixed-size chunk of sequential memory addresses. The mailboxes are memory addresses, and the “items” are pieces of data (typically either variables or addreses).


The “marker” is a register (a small piece of memory) in the CPU known as the stack pointer. The stack pointer keeps track of where the top of the stack currently is.

The only difference between our hypothetical mailbox stack and the call stack is that when we pop an item off the call stack, we don’t have to erase the memory (the equivalent of emptying the mailbox). We can just leave it to be overwritten by the next item pushed to that piece of memory. Because the stack pointer will be below that memory location, we know that memory location is not on the stack.

So what do we push onto our call stack? Parameters, local variables, and… function calls.

The stack in action

Because parameters and local variables essentially belong to a function, we really only need to consider what happens on the stack when we call a function. Here is the sequence of steps that takes place when a function is called:

1. The address of the instruction beyond the function call is pushed onto the stack. This is how the CPU remembers where to go after the function returns.

2. Room is made on the stack for the function’s return type. This is just a placeholder for now.

3. The CPU jumps to the function’s code.

4. The current top of the stack is held in a special pointer called the stack frame. Everything added to the stack after this point is considered “local” to the function.

5. All function arguments are placed on the stack.

6. The instructions inside of the function begin executing.

7. Local variables are pushed onto the stack as they are defined.

When the function terminates, the following steps happen:

1. The function’s return value is copied into the placeholder that was put on the stack for this purpose.

2. Everything after the stack frame pointer is popped off. This destroys all local variables and arguments.

3. The return value is popped off the stack and is assigned as the value of the function. If the value of the function isn’t assigned to anything, no assignment takes place, and the value is lost.

4. The address of the next instruction to execute is popped off the stack, and the CPU resumes execution at that instruction.

Typically, it is not important to know all the details about how the call stack works. However, understanding that functions are effectively pushed on the stack when they are called and popped off when they return gives you the fundamentals needed to understand recursion, as well as some other concepts that are useful when debugging.

Stack overflow

The stack has a limited size, and consequently can only hold a limited amount of information. I

If the program tries to put too much information on the stack, stack overflow will result.

Stack overflow happens when all the memory in the stack has been allocated — in that case, further allocations begin overflowing into other sections of memory.

Stack overflow is generally the result of allocating too many variables on the stack, and/or making too many nested function calls (where function A calls function B calls function C calls function D etc…) Overflowing the stack generally causes the program to crash.

Here is an example program that causes a stack overflow. You can run it on your system and watch it crash:

int main()
{
int nStack[100000000];
return 0;
}

This program tries to allocate a huge array on the stack. Because the stack is not large enough to handle this array, the array allocation overflows into portions of memory the program is not allowed to use. Consequently, the program crashes.

The stack has advantages and disadvantages:

Memory allocated on the stack stays in scope as long as it is on the stack. It is destroyed when it is popped off the stack.

All memory allocated on the stack is known at compile time. Consequently, this memory can be accessed directly through a variable.

Because the stack is relatively small, it is generally not a good idea to do anything that eats up lots of stack space. This includes allocating large arrays, structures, and classes, as well as heavy recursion.


Stack:

Stored in computer RAM like the heap.
Variables created on the stack will go out of scope and automatically deallocate.

Much faster to allocate in comparison to variables on the heap.

Implemented with an actual stack data structure.

Stores local data, return addresses, used for parameter passing

Can have a stack overflow when too much of the stack is used. (mostly from inifinite (or too much) recursion, very large allocations)

Data created on the stack can be used without pointers.


You would use the stack if you know exactly how much data you need to allocate before compile time and it is not too big.

Usually has a maximum size already determined when your program starts

Heap:

Stored in computer RAM like the stack.

Variables on the heap must be destroyed manually and never fall out of scope. The data is freed with delete, delete[] or free

Slower to allocate in comparison to variables on the stack.

Used on demand to allocate a block of data for use by the program.

Can have fragmentation when there are a lot of allocations and deallocations

In C++ data created on the heap will be pointed to by pointers and allocated with new or malloc

Can have allocation failures if too big of a buffer is requested to be allocated.

You would use the heap if you don't know exactly how much data you will need at runtime or if you need to allocate a lot of data.

Responsible for memory leaks

Can you overload new operator

#include<iostream>
#include<malloc.h>

using namespace std;
class sample
{
 int i;
 char c;
 public:
 void* operator new(size_t s,int ii,char cc)
 {
  sample *q =(sample*) malloc(s);
 q->i =ii;
 q->c =cc;
 cout<<"Memory allocation"<<endl;
 return q;
 }
void operator delete(void *q)
 {
  free(q);
 }
 void display()
 {  cout<<i<<"   "<<c;
}
};

int main()
{
 sample *s =new (7,'a')sample;
 return 0;
}



when-do-you-overload-operator-new

What is mean of size_t and why we need it.

size_t is type of unsigned integer.which is the Return value of sizeof  operator.

`size_t' is a type suitable for representing the amount of memory a data object requires, expressed in units of `char'.
It is an integer type (C cannot keep track of fractions of a `char'), and it is unsigned (negative sizes make no sense). It is the type of the result of the `sizeof' operator. It is the type you pass to malloc() and friends to say how much memory you want. 

It is the type returned by strlen() to say how many "significant" characters are in a string.

Each implementation chooses a "real" type like `unsigned int' or `unsigned long' (or perhaps something else)

 to be its `size_t', depending on what makes the most sense. You don't  usually need to worry about what

`size_t' looks like "under the covers;" all you care about is that it is the "right" type for representing object sizes.

The implementation "publishes" its own choice of `size_t' in several of the Standard headers: <stdio.h>, <stdlib.h>, and some others. If you examine one of these headers (most implementations have some way of doing this), you are likely to find something like

#ifndef __SIZE_T
#define __SIZE_T
typedef unsigned int size_t;

#endif
.... meaning that on this particular implementation `size_t' is an `unsigned int'. Other implementations make other choices.

(The preprocessor stuff -- which needn't be in exactly the form  shown here -- ensures that your program will contain only one `typedef' for `size_t' even if it includes several of the headers that declare it)

The complexity of sorting algorithm

Pointers, arrays, and string literals



void strtoupper(char *str)



{


if (str) { // null ptr check, courtesy of Michael


while (*str != '\0') {


// destructively modify the contents at the current pointer location


// using the dereference operator to access the value at the current


// pointer address.


*str = toupper(*str);


++str;


}


}


}


my_str is actually a pointer to a block of memory holding chars. This allows us to use address math to access indices of the array and modify them using the dereference operator. In fact, an array index such as my_str[3] is identical to the expression *(my_str + 3).



char my_str[] = "hello world";

*my_str = toupper(*my_str);
*(my_str + 6) = toupper(*(my_str + 6));

printf("%s", my_str); // prints, "Hello World"



However, if my_str is declared as a char pointer to the string literal “hello world” rather than a char array, these operations fail:

char *my_str = "hello world";

*my_str = toupper(*my_str); // fails
*(my_str + 6) = toupper(*(my_str + 6)); // fails
printf("%s", my_str);


Let’s explore the difference between the two declarations.


char *a = "hello world";

char b[] = "hello world";
In the compiled program, it is likely that “hello world” is stored literally inside the executable. It is effectively an immutable, constant value. Pointing char *a to it provides the scope with read-only access to an immutable block of memory. Therefore, attempting to assign a value might cause other code that points to the same memory to behave erratically.

The declaration of char b[] instead declares a locally allocated block of memory that is then filled with the chars, “hello world”. b is now a pointer to the first address of that array. The complete statement, combining the declaration and assignment, is shorthand. Dispensing with the array size (e.g., char instead of char[12]) is permitted as the compiler is able to ascertain its size from the string literal it was assigned.


In both cases the pointer is used to access array indices:


int i;

for (i = 0; a[i] != '\0'; ++i)
printf("%c", toupper(a[i]));
However, only with b is the program able to modify the values in memory, since it is explicitly copied to a mutable location on the stack in its declaration:


int i;


for (i = 0; b[i] != '\0'; ++i)
b[i] = toupper(b[i]);
printf("%s", b);

Binary Search
A fast way to search a sorted array is to use a binary search. The idea is to look at the element in the middle. If the key is equal to that, the search is finished. If the key is less than the middle element, do a binary search on the first half. If it's greater, do a binary search of the second half.


Performance
The advantage of a binary search over a linear search is astounding for large numbers. For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element. Probably the only faster kind of search uses hashing, a topic that isn't covered in these notes.


This performance comes at a price - the array must be sorted first. Because sorting isn't a fast operation, it may not be worth the effort to sort when there are only a few searches.

int main()


{


char my_str[] = "hello world";


strtoupper(my_str);


printf("%s", my_str);


return 0;


}


Boost  Libraries

The name should already give it away

A Smart Pointer is a C++ object that acts like a pointer, but additionally deletes the object when it is no longer needed.

No longer needed" is hard to define, since resource management in C++ is very complex. 

Different smart pointer implementations cover the most common scenarios

Many libraries provide smart pointer implementations with different advantages and drawbacks. The samples here use the BOOST library, a high quality open source template library, with many submissions considered for inclusion in the next C++ standard.

Boost provides the following smart pointer implementations:

shared_ptr<T>	pointer to T" using a reference count to determine when the object is no longer needed. shared_ptr is the generic, most versatile smart pointer offered by boost.
scoped_ptr<T>	a pointer automatically deleted when it goes out of scope. No assignment possible, but no performance penalties compared to "raw" pointers
intrusive_ptr<T>	another reference counting pointer. It provides better performance than shared_ptr, but requires the type T to provide its own reference counting mechanism.
weak_ptr<T>	a weak pointer, working in conjunction with shared_ptr to avoid circular references
shared_array<T>	like shared_ptr, but access syntax is for an Array of T
scoped_array<T>	like scoped_ptr, but access syntax is for an Array of T

The first: boost::scoped_ptr<T>

 scoped_ptr is the simplest smart pointer provided by boost. It guarantees automatic deletion when the pointer goes out of scope.

The samples use a helper class, CSample, that prints diagnostic messages when it it constructed,assigned, or destroyed. 

Still it might be interesting to step through with the debugger

The following sample uses a scoped_ptr for automatic destruction

Using normal pointers	Using scoped_ptr
Collapse void Sample1_Plain() { CSample * pSample(new CSample); if (!pSample->Query() ) // just some function... { delete pSample; return; } pSample->Use(); delete pSample; }	Collapse #include "boost/smart_ptr.h" void Sample1_ScopedPtr() { boost::scoped_ptr<CSample> samplePtr(new CSample); if (!samplePtr->Query() ) // just some function... return; samplePtr->Use(); }

Using "normal" pointers, we must remember to delete it at every place we exit the function.

This is especially tiresome (and easily forgotten) when using exceptions.The second example uses a scoped_ptr for the same task.

It automatically deletes the pointer when the function eturns 8 even in the case of an exception thrown, which isn't even covered in the "raw pointer" sample!

The advantage is obvious: in a more complex function it's easy to forget to delete an object. 

scoped_ptr does it for you.Also, when dereferencing a NULL pointer, you get an assertion in debug mode.

use for	automatic deletion of local objects or class members1, Delayed Instantiation, implementing PIMPL and RAII (see below)
not good for	element in an STL container, multiple pointers to the same object
performance:	scoped_ptr adds little (if any) overhead to a "plain" pointer, it performs

shared_ptr<T>

Reference counting pointers track how many pointers are referring to an object.and when the last pointer to an object is destroyed, it deletes the object itself, too.

 The "normal" reference counted pointer provided by boost is shared_ptr (the name indicates that multiple pointers can share the same object).

Let's look at a few examples:

void Sample2_Shared()
{
  // (A) create a new CSample instance with one reference

  boost::shared_ptr<CSample> mySample(new CSample); 
  printf("The Sample now has %i references\n", mySample.use_count()); // should be 1


  // (B) assign a second pointer to it:

  boost::shared_ptr<CSample> mySample2 = mySample; // should be 2 refs by now

  printf("The Sample now has %i references\n", mySample.use_count());

  // (C) set the first pointer to NULL

  mySample.reset(); 
  printf("The Sample now has %i references\n", mySample2.use_count());  // 1


  // the object allocated in (1) is deleted automatically

  // when mySample2 goes out of scope

}

Line (A) creates a new CSample instance on the heap, 

and assigns the pointer to a shared_ptr, mySample. Things look like this 

Then, we assign it to a second pointer mySample2. Now, two pointers access the same data:

We reset the first pointer (equivalent to p=NULL for a raw pointer).

The CSample instance is still there, since mySample2 holds a reference to it

Only when the last reference, mySample2, goes out of scope, the CSample is destroyed with it:

Of course, this is not limited to a single CSample instance, or two pointers, or a single function.

Here are some use cases for a shared_ptr.

use in containers 
using the pointer-to-implementation idiom (PIMPL) 
Resource-Acquisition-Is-Initialization (RAII) idiom 
Separating Interface from Implementation 

Important Features

The boost::shared_ptr implementation has some important features.

that make it stand out from other implementations

shared_ptr<T> works with an incomplete type

When declaring or using a shared_ptr<T>, T may be an "incomplete type"  

E.g., you do only a forward declaration using class T;

But do not yet define how T really looks like. 

shared_ptr<T> works with any type:

There are virtually no requirements towards T (such as deriving from a base class)

shared_ptr<T> supports a custom deleter

So you can store objects that need a different cleanup than delete p.For more information, see the boost documentation.

Implicit conversion:

If a type U * can be implicitly converted to T * (e.g., because T is base class of U), a shared_ptr<U> can also be converted to shared_ptr<T> implicitly.

shared_ptr is thread safe

(This is a design choice rather than an advantage, however, it is a necessity in multithreaded programs, and the overhead is low.)

 Example: Using shared_ptr in containers

Many container classes, including the STL containers, require copy operations

e.g., when inserting an existing element into a list vector, or container). However,

when this copy operations are expensive (or are even unavailable),

the typical solution is to use a container of pointers

std::vector<CMyLargeClass *> vec;
vec.push_back( new CMyLargeClass("bigString") );

However, this throws the task of memory management back to the caller

We can, however, use a shared_ptr

typedef boost::shared_ptr<CMyLargeClass>  CMyLargeClassPtr;
std::vector<CMyLargeClassPtr> vec;
vec.push_back( CMyLargeClassPtr(new CMyLargeClass("bigString")) );

Very similar, but now, the elements get destroyed automatically when
the vector is destroyed

unless, of course, there's another smart pointer still holding a reference Let's have a look at sample

void Sample3_Container()
{
  typedef boost::shared_ptr<CSample> CSamplePtr;

  // (A) create a container of CSample pointers:  std::vector<CSamplePtr> vec;

  // (B) add three elements  vec.push_back(CSamplePtr(new CSample));
  vec.push_back(CSamplePtr(new CSample));
  vec.push_back(CSamplePtr(new CSample));

  // (C) "keep" a pointer to the second:   CSamplePtr anElement = vec[1];

  // (D) destroy the vector:  vec.clear();

  // (E) the second element still exists  anElement->Use();
  printf("done. cleanup is automatic\n");

  // (F) anElement goes out of scope, deleting the last CSample instance}

A few things can go wrong with smart pointers  most prominent is an invalid reference count
which deletes the object too early, or not at all

The boost implementation promotes safety, making all "potentially dangerous" operations explicit. So, with a few rules to remember, you are safe

Rule 1: Assign and keep

Assign a newly constructed instance to a smart pointer immediately and then keep it there The smart pointer(s) now own the object, you must not delete it manually, nor can you take it away again This helps to not accidentally delete an object that is still
 referenced by a smart pointer, or end up with an invalid reference count.

Rule 2 : 
a _ptr<T> is not a T * - more correctly, there are no implicit conversions between
 a T * and a smart pointer to type T

This means:

When creating a smart pointer, you explicitly have to write ..._ptr<T> myPtr(new T)

You cannot assign a T * to a smart pointer

You cannot even write ptr=NULL. Use ptr.reset() for that

To retrieve the raw pointer, use ptr.get(). Of course, you must not delete this pointer or use it after the smart pointer it comes from is destroyed
reset or reassigned
Use get() only when you have to pass the pointer to a function that expects a raw pointer

You cannot pass a T * to a function that expects a _ptr<T> directly.
You have to construct a smart pointer explicitly, which also makes it
clear that you transfer ownership of the raw pointer to the smart pointer. (See also Rule 3.)

Rule 2: No circular references
If you have two objects referencing each other through a reference counting pointer
they are never deleted. boost provides weak_ptr to break such cycles (see below).

Rule 3: no temporary shared_ptr
Do not construct temporary shared_ptr to pass them to functions,
always use a named (local) variable.


Cyclic References
Reference counting is a convenient resource management mechanism, it has one fundamental drawback though:

Reference counting is a convenient resource management mechanism, it has one fundamental drawback though:

struct CDad; struct CChild;

typedef boost::shared_ptr<CDad>   CDadPtr;
typedef boost::shared_ptr<CChild> CChildPtr;


struct CDad : public CSample
{
   CChildPtr myBoy;
};

struct CChild : public CSample
{
  CDadPtr myDad;
};
// a "thing" that holds a smart pointer to another "thing":
CDadPtr   parent(new CDadPtr);
CChildPtr child(new CChildPtr);

// deliberately create a circular reference:parent->myBoy = child;
child->myDad = dad;


Some Useful url related C++ FAQ

http://www.daniweb.com/forums/thread107723.html


// resetting one ptr...child.reset();

parent still references the CDad object, which itself references the CChild. The whole thing looks like this:

If we now call dad.reset(), we lose all "contact" with the two objects.
But this leaves both with exactly one reference, and the shared pointers 
see no reason to delete either of them! We have no access to them anymore but they mutually keep themselves "alive".

This is a memory leak at best; in the worst case, the objects hold even more critical resources
that are not released correctly.

The problem is not solvable with a "better" shared pointer implementation
or at least, only with unacceptable overhead and restrictions
So you have to break that cycle. There are two ways:

Manually break the cycle before you release your last reference to it
When the lifetime of Dad is known to exceed the lifetime of Child, the
child can use a normal (raw) pointer to Dad.

Use a boost::weak_ptr to break the cycle

Solutions (1) and (2) are no perfect solutions but they work with smart pointer libraries that do not offer a weak_ptr like boost does