Dynamic allocation of arrays in cpp

The problems with fixed size arrays

Declaring an array with a fixed size like

int a[100000];

has two typical problems:

• Exceeding maximum. Choosing a real maximum is often impossible because the programmer has no control over the size of the data sets the user is interested in. Erroneous assumptions that a maximum will never be exceeded are the source of many programming bugs. Declaring very large arrays can be extremely wasteful of memory, and if there are many such arrays, may prevent the program from running in some systems.
• No expansion. Using a small size may be more efficient for the typical data set, but prevents the program from running with larger data sets. If array limits are not checked, large data sets will run over the end of an array with disastrous consequences. Fixed size arrays can not expand as needed.

These problems can be avoided by dynamically allocating an array of the right size, or reallocating an array when it needs to expand. Both of these are done by declaring an array as a pointer and using the new operator to allocate memory, and delete to free memory that is no longer needed.
This is exactly what is vector does, but let's see how it's done with an array.

Declare array as a pointer, allocate with new

To create a variable that will point to a dynamically allocated array, declare it as a pointer to the element type. For example,

int* a = NULL;  // pointer to an int, intiallly to nothing.

A dynamically allocated array is declared as a pointer, and must not use the fixed array size declaration. The above declaration creates a pointer, but doesn't yet allocate any memory to it.

Allocate an array with code>new

When the desired size of an array is known, allocate memory for it with the new operator and save the address of that memory in the pointer. Remember: Pointers may be subscripted just as arrays are. The example below reads in a number and allocates that size array.

int* a = NULL;   // Pointer to int, initialize to nothing.
int n;           // Size needed for array
cin >> n;        // Read in the size
a = new int[n];  // Allocate n ints and save ptr in a.
for (int i=0; i
    a[i] = 0;    // Initialize all elements to zero.
}
. . .  // Use a as a normal array
delete [] a;  // When done, free memory pointed to by a.
a = NULL;     // Clear a to prevent using invalid memory reference.

Freeing memory with delete

When you are finished with dynamically allocated memory, free it with the delete operator. After memory is freed, it can be reused by later new requests. Memory that your program didn't free will be freed when the program terminates. Never free memory that wasn't dynamically allocated - the results are unpredictable.

delete [] a;  // Free memory allocated for the a array.
a = NULL;     // Be sure the deallocated memory isn't used.

Use [] when deleting arrays

You must specify "[]" when deleting an array, but not for a single value. It isn't possible to delete only part of an array.

Do you have to reset a pointer after delete?

Following the delete in these examples, I reset the pointer to NULL. This isn't strictly necessary, but it's very good practice so that any use of the pointer will produce an error. Attempts to use memory location 0, which is the normal default value of NULL, will be blocked by the way most operating systems allocate memory.
Why doesn't delete reset the pointer? It does in some systems, but the language specification does not require it, so not all systems do it.

zero sized allocation using malloc

int main()
{
    int *p = 0;
    printf("before addr: %pn", p);
    p = (int *) malloc(0);
    printf("after addr: %pn", p);
    printf("sizeof: %un", sizeof(*p));
    *p = 1;
    printf("--- %d -- this is the last statment.n", *p);
    free(p);
}

Output
before addr: (nil)
after addr: 0x80496c8
sizeof: 4
--- 1 -- this is the last statment.

Note :
Linux

• allows a ‘read’ of the zero sized allocated memory
• allows a ‘write’ on the zero sized allocated memory
• sizeof shows an allocation of 4 bytes.

Memory Management In C and C + +

For simple applications, it's enough just to rely on automatic memory management through local variables. But once the data become larger, it is no longer imperative to request memory from the heap and manage.

Content

1. Function Families
2. Allocators
3. Toolbox
4. Smart Pointer
5. STL Containers

A function families

In principle, belong to the memory always two parts. First, an area of memory are requested, and second, the memory used at the end of the work be returned. For this reason, memory management functions normally exist in pairs, sharing the work.

When working with C + + objects is yet to fill the requested memory with sensible starting values or the data of the object at the end of the work to clean up again. For this purpose, there are constructors and destructors that are called automatically to suit the use or management must be handled manually.

Over time, various function pairs were developed, which can be requested and memory freed. It is particularly important to the different methods of memory management not to interfere with each other. In the simplest case, it is "just" a memory leak (if the sharing function "just forget" to call the Objektdestruktor or returns too little heap memory), in the worst case, can not be predicted what will make the program (for example, it can happen that the release function tries to interpret something in her memory structure unknown).

For this reason, libraries, heap areas and request the user to pass, always provide a compatible release function, which is suitable to its own working memory - or in the documentation at least set the method of the memory they use.

1.1 malloc () and free ()

This family dates back to C and has been for reasons of compatibility for C + +: Accepted

• malloc (s)
  allocates a memory area with (at least) s bytes in size and returns a pointer to the beginning of this area. The content of this field is undefined.
• calloc (n, s)
  enough allocates memory for n objects of size s and initialize it with zeros
• realloc (p, s)
  the amount of memory changes, the p shows on s bytes and returns the new address of the memory (realloc (NULL, s) "is equivalent to 'malloc (s)" and "realloc (p, 0)" corresponds "free (p)")
• free (p)
  there by the malloc () etc. requested memory range again free (p must be the NULL pointer, in which case nothing happens)

These functions do not care about the contents of the managed memory areas and therefore should only be used with POD (plain old data) types.

Note: The function realloc () can also single-handedly take over the entire memory of a program by its parameters are set appropriately:

Code:

char* str = realloc (NULL, 100);/ / memory allocation 
... 
realloc (str, 0);/ / Release memory

1.2 New and delete

For C + +, a new mechanism for memory management, which provides a better approach to the class. Unlike malloc () / free () the memory areas are regarded as objects of arbitrary classes, and now initialized with an appropriate constructor.

• new T (...)
  enough reserved memory for an object of type T, and calls its constructor according to the specified parameter list (the parameter list can be removed also, then the default constructor uses)
• delete p;
  calls the destructor of the object pointed to by p, and are then free the memory

Another advantage of new and delete is the fact that they can be overridden by the user. This requires either a global (for every new call) or static member function (for their own class, and all children) "operator new ()" or "operator delete ()", or the free memory can request. These operators work with unstructured data fields - the call to constructors and destructors are independently:

Code:

void* operator new(size_t s) 
( 
  void* p; 
  / / Reserve memory for at least s bytes 
  return p; 
) 

void operator delete(void* p) 
( 
  / / Give free hand p 
)

Both functions can obtain additional parameters of any type to implement the so-called "placement new". These parameters are by calling "new (values) T (ctor parameter) passed. The most common use cases of this are the specification of a destination address (an object to initialize in available memory) and the installation of debugging information (the MFC-operator DEBUG_NEW passes "as file name and program line to be able to track memory leaks).

Note: "operator new" and "operator delete" operate with bare areas of memory. The constructor and destructor of the object involved is called when operator new has come back before or operator delete is called.

Caution: Do not overcharge the global operators only if you are absolutely sure what you want to achieve. The global version of operator new and operator delete takes really ANY memory request within the program - and in contrast to klasseninternen operators can not here from the predefined memory access operators.

Another typical application for operator new and operator delete is to use a pool manager: in order to save computing time, the memory of precaution required in larger blocks, replaced and forwarded as needed to the program. From the program of shared memory is not returned to the system, but also for future requirements repealed.

1.3 New [] and delete []

In parallel with new and delete, playing with various objects, there are versions to manage whole object array:

• new T [n]
  enough reserved memory for n objects of type T, and calls for an object whose default constructor
  Note: It is not possible to specify parameters for the constructor invoked
• delete [] p;
  calls for all objects in the array after p destructor on the memory and are then free to
  Just like new / delete can be adapted to these functions by "be void * operator new [] (size_t s);" or "void operator delete [] (void * p); overwritten.

Note: new [] remember (just like malloc ()) internally the size of the allocated memory. However, there is no portable way to access this information.

Note: Despite the name similarity is not guaranteed that new / delete and new [] / delete [] are compatible with each other. So try NIE, the two mix with each other.

1.4 Other families

Many libraries define your own function pairs in order to request and release memory, eg VirtualAlloc () / manage Virtual Free () from the WinAPI, the memory in the "shared memory". All such families function in common is that they consist of at least two functions - one for requesting memory, one for release. Analogous to the malloc () family may be added other features that can reorganize the managed memory.

Because different memory strategies are not necessarily compatible with each other, you should always use the correct release function if you need more memory not yours. Therefore, it is usually a good idea to have a program on a strategy and set within this largely unsustainable. If that is not generally possible, should know where he is to his memory relate to each case are set for each pointer used.

Even in the standard library yet another function family is defined, which can be used to manage temporary storage:

• get_temporary_buffer (num)
  allocates a temporary buffer for a maximum of num objects of type T and is a couple with its address and available disk space back to the
• return_temporary_buffer (p)
  have requested a temporary buffer back to the system

These temporary buffer can be used within a function to provide large amounts of additional memory (eg, merge sort requires an auxiliary memory for its data). Make sure that the returned memory region may be less than requested.

Allocators

The containers of the STL default to new [] and delete [] to know the memory request for their elements. However, as it should be possible to switch to a different memory management, this behavior had been moved into so-called allocators - these can be interchanged, to use a different memory behavior. In addition, each container class as the last template parameter an indication of the allocator class. The default value for this is std:: allocator - this allocates memory using new [] and returns it with delete [] free again.

An allocator has to be used with the STL, provide some basic methods and definitions. If you write an allocator for its own purposes, the requirements may be lower.

2.1 management

The most important are the Allokatorklasse course, the functions that can manage the memory:

• allocate (n, h = 0)
  Reserved uninitialized memory for n elements and returns it (eg by: operator new () or malloc ()). The optionally specified pointer h can be used to influence the storage strategy.
• construct (p, val)
  Initializes the object pointed to by p, as a copy of val (usually via placement new)
• destroy (p)
  Destroy the object pointed to by p (usually by direct destructor call)
• deallocate (p, n)
  Is an area behind free p consisting of n elements (the parameter can be useful if the size of memory used can not be determined from the pointer itself) - The objects must first be destroyed

In addition, the allocator max_size the helper methods () that can specify the maximum size of a memory block (in elements) and address (ref) can be defined by the object at a given address.

Custom allocators are generally allocate the methods (), deallocate () and max_size () override to implement the storage strategy. construct () and destroy () are likely to differ only in the rarest cases, by the standard version:

Code:

template 
class Alloc 
( 
  ... 
public: 
  void construct (pointer p, const T & val) 
  ( New((void*) p) T val ();) 
  void destroy (pointer p) 
  (P-> ~ T ();) 
  ... 
);

2.2 rebind <>

In order to offer the ability to store various objects that contains a substructure Allokatorklasse called "Rebind. This is used as the associative container classes, which receive as an allocator template parameter , but need an internal TreeNode allocator <>.

This structure is pretty simple and serves only to "packaging" of the alternate type:

Code:

template 
class Alloc 
( 
  ... 
public: 
  template 
  struct rebind 
  ( typedef Alloc  other;); 
  ... 
);

In this way, one can easily allocator for any data obtained by inspecting the structure:

Code:

template> 
class mycont 
( 
public: 
  //... 
  typedef A allocator_type; 
  typedef typename A:: rebind :: other ptr_allocator,/ / Pointer to compatible allocator 
  //... 
);

2.3 Comparisons

Different allocators can be compared with the operators == and! =. These features will be released equality that two allocators are interchangeable - is requested by a memory on b again.

For example, building allocators, to delete the new /, are interchangeable, as is required for the delete-object call no tax. In contrast pool allocators are limited interchangeable because each allocator manages its own list of reserve memory.

Note: STL compatible allocators have to be interchangeable. reduce most of the comparison operators to a "return true reason," or return false; ".

2.4 Type definitions

Allocators also define some basic types used by the connected container classes continue:

• value_type (T)
  the underlying value type
• size_type (size_t) and difference_type (ptrdiff_t)
  two integer types for specifying memory sizes (unsigned) or "points-difference (signed)
• pointer (T *) and const_pointer (const T *)
  Pointer to variable or constant objects
• reference (T &) and const_reference (const T &)
  Reference to variable or constant objects

Note: STL compatible allocators is the award of these basic types defined (according to the above information).

Auxiliary functions for memory management

In addition to the standard library allocators defines some utility functions that can deal with non-uninitialized memory. These serve as a logical extension of memset () and memcpy ():

• uninitialized_fill (beg, end, val)
  initializes the field (in the sense STL) [beg, end [with the corresponding number of copies of 'val'
• (Uninitialized_fill_n beg, n, val)
  initializes the array behind 'beg' with n copies of 'val'
• uninitialized_copy (beg, end, nbeg)
  initializes the array behind 'nbeg' with copies of the range [beg, end [

These functions can be also referred to in section 1.3 restriction bypass that new [] can only call the default constructor:

Code:

T * data =::operator new[] (n *sizeof(T)); 
unitialized_fill_n (data, n, T (4711)); 
... 
delete[] data;

In an emergency, it is also possible to fill a new placement of uninitialized memory area with values:

Code:

* p myType = (myType *) malloc (sizeof(myType)); 
new(p) myType (params); 
... 
p-> ~ myType ();/ / direct call destructor 
free (p);

(Note: should normally take place this construction rather directly to new / delete be used)

3.1 Rohspeicher iterators

Full Name:

Code:

template 
class raw_storage_iterator;

This Hilfsiteratoren can be used to an uninitialized memory as a target STL algorithm indicated. They translate into calls on assignments of the copy constructor placement new.

The template parameter of this class are, first, an output iterator that is used as the basis for the iterator arithmetic (usually enough for this one 'T *') and second, the data type used.

3.2 Functions of the C library

Unlike C + + interprets the C library typically anything in the memory areas, which it manages. Logically, obtained from malloc () a bunch of bytes with no internal structure. Then it depends on the programmer, as he fills the memory and interpreted.

To process this naked memory areas can be either the malloc () pointer obtained in the "right" type casting and processing of hand or some ready-made functions of the C library (memcpy (), memset (), etc.), or (with restrictions ) the string processing functions (strcpy (), strcat () to take, etc.) to help.

Note: Try to be better not to interpret bare memory than C + + objects. Most methods expect an existing basic structure and lead to undefined behavior if they get junk data set before.

Smart Pointer

The management of heap memory (no matter how it was obtained) on bare hands always suffer the same problem - no one can verify when and by whom the memory must be freed. Forget the last owner of the release shows a memory leak, because no one knows more about the existence of the memory block. If the memory released too early, you get access violations and undefined behavior if other users want to access the shared memory.

A solution to this problem is to make the pointer itself to instruct the memory management, instead of bare hands by so-called "smart pointer" is used. These differ in principle three different approaches to control the access and control:

• Reference counting (boost:: shared_ptr, boost:: shared_array)
  The referenced object counts how many pointers point to it. And only when the last pointer from the object, separates the memory is freed.
• Exclusive access (boost:: scoped_ptr, boost:: scoped_array)
  The address may not be transferred. The owner of the pointer and puts him in the end is also responsible to release him again.
• Ownership transfer (std:: auto_ptr)
  There is always just a pointer that points to a memory (owner). When an assignment is the possession and passed the former owner loses access to the memory.

The operation and characteristics of the different smart pointer classes was some time ago in the article "Smart pointer" peter's declared.

Note: Normal smart pointer classes to a specific memory function (usually new / delete and new [] / delete []) defined and therefore expect that their managed storage "was created correctly."

The above smart pointer classes (except auto_ptr to find) into the Boost Library or TR1 extension of the standard. The auto_ptr class is part of the C + + Standard Library.

STL Container

Whom the whole burden of memory management is too complicated, it can also make it easier - and use the various classes of the STL containers. All the container take care of their own so to provide enough memory and to manage, so that the user no longer needs to worry about where their data is housed.

The usable container classes differ mainly from the perspective of memory in it, the strategy that they require memory and organize:

• vector <> and basic_string <>
  use a contiguous area of memory that grows as needed
• deque <>
  usually used a two-layered structure with multiple memory blocks hung together logically to be extended if needed or released
• list <>
  uses a linked list, where each element has a pointer to predecessor and successor
• set <>, multiset <>, map <> and multimap <>
  use a (balanced) binary tree of individually requested node into which they sort their elements

Note: This will of course depend on the type of allocator, where the containers maintain their memory.

Some udfs for arrays in c

1D arrays
Printing 1 D arrays
void printArray (int *array,int size)
{
int i;
for (i = 0; i < size; i++)
     printf("%d",array[i]);
printf("\n");
}
2 D arrays 
Printing 2D arrays
void printArray(int **array, int m, int n)
{
           for(i = 0; i < nrows; i++)  
              for(j= 0; j < nrows; i++)  
                         printf("%d",array[i][j]);
}

Allocating and Deallocating 2 D Arrays 

/*   allocate2D

/*   function to dynamically allocate 2-dimensional array using malloc.

/*

/*   accepts an int** as the "array" to be allocated, and the number of rows and

/*   columns.

*/

void allocate2D(int** array, int nrows, int ncols) {

     

     /*  allocate array of pointers  */

     array = ( int** )malloc( nrows*sizeof( int* ) );

     

     /*  allocate each row  */

     int i;

     for(i = 0; i < nrows; i++) {

          array[i] = ( int* )malloc( ncols*sizeof( int ) );

     }

}

/*   deallocate2D

/*   corresponding function to dynamically deallocate 2-dimensional array using

/*   malloc.

/*

/*   accepts an int** as the "array" to be allocated, and the number of rows. 

/*   as with all dynamic memory allocation, failure to free malloc'ed memory

/*   will result in memory leaks

*/

void deallocate2D(int** array, int nrows) {

     

     /*  deallocate each row  */

     int i;

     for(i = 0; i < nrows; i++) {

          free(array[i]);

     }

     

     /*  deallocate array of pointers  */

     free(array);

     

}

/*   EXAMPLE USAGE:   

int** array1;

allocate2D(array1,1000,1000); //allocates a 1000x1000 array of ints

deallocate2D(array1,1000);    //deallocates the same array

*/

Program to check if the stack grows up or down

#include 
#include 

void stack(int *local1);

int main()
{
  int local1;
  stack(&local1);
  exit(0);
}

void stack(int *local1)
{
   int local2;
   printf("\nAddress of first  local : [%u]", local1);
   printf("\nAddress of second local : [%u]", &local2);
   if(local1 < &local2)
   {
     printf("\nStack is growing downwards.\n");
   }
   else
   {
     printf("\nStack is growing upwards.\n");
   }
   printf("\n\n");
}

What is the difference between malloc() and calloc()?

#include 
  void *calloc(size_t n, size_t size);
  void *malloc(size_t size);


The two functions malloc() and calloc() are functionally same in that they both allocate memory from a storage pool (generally called heap). Actually, the right thing to say is that these two functions are memory managers and not memory allocators. Memory allocation is done by OS specific routines (like brk() and sbrk()).


Here are some differences between these two functions..

1. malloc() takes one argument, whereas calloc() takes two. 
2. calloc() initializes all the bits in the allocated space to zero (this is all-bits-zero!, where as malloc() does not do this. 
3. A call to calloc() is equivalent to a call to malloc() followed by one to memset(). 

calloc(m, n)   is essentially equivalent to

p = malloc(m * n);
memset(p, 0, m * n);

Using calloc(), we can carry out the functionality in a faster way than a combination of malloc() and memset() probably would. You will agree that one libray call is faster than two calls. Additionally, if provided by the native CPU, calloc() could be implementated by the CPU's "allocate-and-initialize-to-zero" instruction. 

        .4. The reason for providing the "n" argument is that sometimes it is required to allocate a number ("n") of uniform objects of a particular size ("size"). Database application, for instance, will have such requirements. Proper planning for the values of "n" and "size" can lead to good memory utilization.

C code to dynamically allocate one, two and three dimensional arrays (using malloc())

One Dimensional Array
int *myarray = malloc(no_of_elements * sizeof(int));

//Access elements as myarray[i]
2 Dimensional Array

Method1
int **myarray = (int **)malloc(nrows * sizeof(int *));
for(i = 0; i < nrows; i++)
{
 myarray[i] = malloc(ncolumns * sizeof(int));

//allocating 1 D array = number of elements in column
}

// Access elements as myarray[i][j]




Method 2 (Contagious Allocation)
int **myarray = (int **)malloc(nrows * sizeof(int *));
myarray[0] = malloc(nrows * ncolumns * sizeof(int));

for(i = 1; i < no_of_rows; i++)
  myarray[i] = myarray[0] + (i * ncolumns);

// Access elements as myarray[i][j]




In either case, the elements of the dynamic array can be accessed with normal-looking array subscripts: array[i][j]. 

Method 3
int *myarray = malloc(nrows * ncolumns * sizeof(int));

// Access elements using myarray[i * ncolumns + j].

i.e. you must now perform subscript calculations manually, accessing the i,jth element with array3[i * ncolumns + j].  (A macro can hide the explicit calculation, but invoking it then requires parentheses and commas which don't look exactly like multidimensional array subscripts.) 

Method4

Finally, you can use pointers-to-arrays:

 int (*array4)[NCOLUMNS] =
  (int (*)[NCOLUMNS])malloc(nrows * sizeof(*array4));

, but the syntax gets horrific and all but one dimension must be known at compile time.

Three Dimensional Array


#define MAXX 3
#define MAXY 4
#define MAXZ 5

main()
{
    int ***p,i,j;
     p=(int ***) malloc(MAXX * sizeof(int ***));

    for(i=0;i
    {
        p[i]=(int **)malloc(MAXY * sizeof(int *));
        for(j=0;j
            p[i][j]=(int *)malloc(MAXZ * sizeof(int));

//allocating 1D array of size = size of last dimensional...So we have to allocate

//n1*n2 such arrays...where n1 and n2 are 2 such dimensional.
    }
     
    for(k=0;k
        for(i=0;i
            for(j=0;j
                p[i][j][k]=;

}

Passing 2 D array to function

double f(double values[][4], int n);

int main() {
  double beans[3][4] = {
                         { 1.0,  2.0,  3.0,  4.0},
                         { 5.0,  6.0,  7.0,  8.0},
                         { 9.0, 10.0, 11.0, 12.0}
                       };

 printf(" %f\n",f(beans, sizeof beans/sizeof beans[0]));
 getch();
  return 0;
}

double f(double array[][4], int size) {
  double sum = 0.0;
  int i,j;
  for( i = 0 ; i < size ; i++)      
    for( j = 0 ; j < 4 ; j++)       
      sum += array[i][j];
     
  return sum;
}

Another method is you dynamically allocate array and than pass its pointer to the function.
#include
#include
#include
// Ref : http://www.eskimo.com/~scs/cclass/int/sx9b.html
void printArray(int **array, int m, int n)
{
     int i,j;
 for(i=0;i
   for( j=0;j
printf("%d\n",array[i][j]);

     printf("\n");
}
int main()
{
      int i,j,k=0, m=5, n=20;
      int **a=(int **)malloc(m*sizeof(int *));
      for(i=0;i
      for(i=0;i      //for(i=0;i
      printArray(a,m,n);
      system("PAUSE");
      return 0;
}