Sunday, July 12, 2009

C++: How to write a dynamic array?

Can you give an example on how to write a dynamic array in C++?





Just a small example.

C++: How to write a dynamic array?
If you mean a variable sized array, the best thing to do is use the standard containers. They automatically adjust their size as you add and remove elements. Vector is the most used container and you should use that unless you have specific needs for the others.





The standard containers are template classes, i.e. you have to indicate what type of element they will store.





#include %26lt;iostream%26gt;


#include %26lt;vector%26gt;





// Create a vector containing integers


std::vector%26lt;int%26gt; v_int;





v_int.push_back(36);


v_int.push_back(29);


v_int.push_back(312);


// at this point, v_int contains 3 items: 26, 29 %26amp; 312;





// output 29 to stdout


std::cout %26lt;%26lt; v_int[1] %26lt;%26lt; std::endl;





v_int.erase(v_int.begin() + 1); // erase the 29 element





If you need to do this yourself, it's a bit more work;





You use malloc and free to allocate and free the memory:





int *a_int; // declare a pointer to integer


int arraySize = //put array size calculation here;


a_int = (int*)malloc(sizeof(int) * arraySize);


for (i = 0; i != arraySize; ++i)


....a_int[i] = //put array element calculation here;


// use array here


// Now we are done, free array


free(a_int);


// After free, we can no longer use a_int. If we do an error will occur
Reply:Big answer: following is the contents of dbms.h on my machine. I use it whenever I need to create a variable list. It's slightly inefficient, especially during resizes, but it works for most tasks.


By the way, you'll need to find the line in your assert.h that says:


# define assert(p) ((p) ? (void)0 : (void) __assertfail( \


"Assertion failed: %s, file %s, line %d"##_ENDL, \


#p, __FILE__, __LINE__ ) )


and change it to:


# define assert(p, msg) ((p) ? (void)0 : (void) __assertfail( \


"Assertion failed: %s, file %s, line %d"##_ENDL msg _ENDL, \


#p, __FILE__, __LINE__ ) )


Tell me if there are any bugs! I need a beta tester.





//Begin of code segment


#ifndef LIST_H


#define LIST_H





#include %26lt;assert.h%26gt;





#define FIRST 1


#define LAST 2


#define ALL 3


#define POS(x) ((x)*-1)





template %26lt;class TS1%26gt;


int ASCENDING(TS1 %26amp;in1, TS1 %26amp;in2) {return in1%26gt;in2;}





template %26lt;class TS2%26gt;


int DESCENDING(TS2 %26amp;in1, TS2 %26amp;in2) {return in1%26lt;in2;}





template %26lt;class T1%26gt;


class List{


public:


List(int=0);


List(T1 *);


~List();


void Resize(int);


void Append(T1);


void Set(int, T1);


T1 Get(int);


int Search(T1, int);


int Remove(T1, int);


T1 %26amp;operator[](int);


void Swap(int, int);


int operator==(List%26lt;T1%26gt;);


int operator!=(List%26lt;T1%26gt;);


List%26lt;T1%26gt; %26amp;operator=(List%26lt;T1%26gt; %26amp;);


void Sort(int (*)(T1 %26amp;, T1 %26amp;));


int Size();


static int ID;


private:


T1 *l;


int size, myid;


};





template %26lt;class T1%26gt;


List%26lt;T1%26gt;::List(int s=0)


{


T1 def;


int j;


assert(s%26gt;=0, "Size cannot be less than 0 in 'List::List(int=0)'");


size=s;


l=new T1[size];


for(j=0; j%26lt;size; j++)


l[j]=def;


myid=ID++;


}





template %26lt;class T1%26gt;


List%26lt;T1%26gt;::List(T1 *a)


{


int j;


size=sizeof(a)/sizeof(T1);


l=new T1[size];


for(j=0; j%26lt;size; j++)


l[j]=a[j];


myid=ID++;


}





template %26lt;class T1%26gt;


List%26lt;T1%26gt;::~List()


{


delete [] l;


}





template %26lt;class T1%26gt;


void List%26lt;T1%26gt;::Resize(int s)


{


int j;


T1 *buf, def;


buf=new T1[size%26gt;s?s:size];


for(j=0; j%26lt;(size%26gt;s?s:size); j++)


buf[j]=l[j];


delete [] l;


l=new T1[s];


for(j=0; j%26lt;(size%26gt;s?s:size); j++)


l[j]=buf[j];


for(j=size; j%26lt;s; j++)


l[j]=def;


delete [] buf;


size=s;


}





template %26lt;class T1%26gt;


void List%26lt;T1%26gt;::Append(T1 item)


{


Resize(size+1);


Set(size-1, item);


}





template %26lt;class T1%26gt;


void List%26lt;T1%26gt;::Set(int indice, T1 val)


{


assert(indice%26gt;=0%26amp;%26amp;indice%26lt;size, "Indice out of range in 'void List%26lt;T1%26gt;::Set(int indice, T1 val)'");


l[indice]=val;


}





template %26lt;class T1%26gt;


T1 List%26lt;T1%26gt;::Get(int indice)


{


assert(indice%26gt;=0%26amp;%26amp;indice%26lt;size, "Indice out of range in 'T1 List%26lt;T1%26gt;::Get(int indice)'");


return l[indice];


}





template %26lt;class T1%26gt;


int List%26lt;T1%26gt;::Search(T1 val, int type)


{


int j, ct=0;


switch(type){


case FIRST:


for(j=0; j%26lt;size; j++)


if(l[j]==val)


return j;


return -1;


break;





case LAST:


for(j=size-1; j%26gt;=0; j++)


if(l[j]==val)


return j;


return -1;


break;





case ALL:


for(j=0; j%26lt;size; j++)


if(l[j]==val)


ct++;


return ct;


break;





default:


for(j=0; j%26lt;size; j++)


if(l[j]==val)


if(++ct==POS(type))


return j;


if(j%26gt;0)


return -1;


return -2;


break;}


}





template %26lt;class T1%26gt;


int List%26lt;T1%26gt;::Remove(T1 val, int type)


{


int i, j, ct=0;


switch(type){


case FIRST:


for(i=0; i%26lt;size; i++)


if(l[i]==val){


for(j=i; j%26lt;size; j++)


l[j]=l[j+1];


return 1;}


return 0;


break;





case LAST:


for(i=size-1; i%26gt;=0; i++)


if(l[i]==val){


for(j=i; j%26lt;size; j++)


l[j]=l[j+1];


return 1;}


return 0;


break;





case ALL:


for(i=0; i%26lt;size; i++)


if(l[i]==val){


for(j=i; j%26lt;size; j++)


l[j]=l[j+1];


ct++;}


return ct;


break;





default:


for(i=0; i%26lt;size; i++)


if(l[i]==val){


if(++ct==POS(type))


for(j=i; j%26lt;size; j++)


l[j]=l[j+1];


return 1;}


return 0;


break;}


}





template %26lt;class T1%26gt;


T1 %26amp;List%26lt;T1%26gt;::operator[](int indice)


{


assert(indice%26gt;=0%26amp;%26amp;indice%26lt;size, "Indice out of range in 'T1 %26amp;List%26lt;T1%26gt;::operator[](int indice)'");


return l[indice];


}





template %26lt;class T1%26gt;


void List%26lt;T1%26gt;::Swap(int id1, int id2)


{


T1 temp;


assert(id1%26gt;=0%26amp;%26amp;id1%26lt;size, "First indice is out of range in 'void List%26lt;T1%26gt;::Swap(int id1, int id2)'");


assert(id2%26gt;=0%26amp;%26amp;id2%26lt;size, "Second indice is out of range in 'void List%26lt;T1%26gt;::Swap(int id1, int id2)'");


temp=l[id1];


l[id1]=l[id2];


l[id2]=temp;


}





template %26lt;class T1%26gt;


int List%26lt;T1%26gt;::operator==(List%26lt;T1%26gt; cmp)


{


int j;


if(size!=cmp.size)


return 0;


for(j=0; j%26lt;size; j++)


if(l[j]!=cmp.l[j])


return 0;


return 1;


}





template %26lt;class T1%26gt;


int List%26lt;T1%26gt;::operator!=(List%26lt;T1%26gt; cmp)


{


return !operator==(cmp);


}





template %26lt;class T1%26gt;


List%26lt;T1%26gt; %26amp;List%26lt;T1%26gt;::operator=(List%26lt;T1%26gt; %26amp;asgn)


{


int j;


assert(l!=asgn.l, "Cannot self-assign in 'List%26lt;T1%26gt; List%26lt;T1%26gt;::operator=(List%26lt;T1%26gt; asgn)'");


Resize(asgn.size);


for(j=0; j%26lt;asgn.size; j++)


l[j]=asgn.l[j];


}





template %26lt;class T1%26gt;


void List%26lt;T1%26gt;::Sort(int (*func)(T1 %26amp;, T1 %26amp;))


{


int i, j;


for(i=0; i%26lt;size; i++)


for(j=0; j%26lt;size-1; j++)


if(func(l[j], l[j+1]))


Swap(j, j+1);


}





template %26lt;class T1%26gt;


int List%26lt;T1%26gt;::Size() {return size;}





template %26lt;class T1%26gt;


static int List%26lt;T1%26gt;::ID=1;





#endif





//End of code segment


No comments:

Post a Comment