• C

Dynamic Arrays in C programming

Hello!

I was just wondering about the use of dynamic arrays in the C programming language.
Someone has told me that it is possible to use the std::vector class but I am not sure how to go about it. Could you guys give me an example of how to use vectors in C, which header file to include, etc... Just a sample code to allow me to get an idea or some useful links to help me deepen the subject.

Smanyx
SmanyxAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Infinity08Commented:
>> Someone has told me that it is possible to use the std::vector class but I am not sure how to go about it.

std::vector is available in C++, but not in C.

If you meant to ask this for C++, then have a look at these reference pages for std::vector :

        http://www.cplusplus.com/reference/stl/vector/

You'll find plenty of documentation there, as well as code samples.



In case you DID intend to ask this for C, then you can't use std::vector. You can however still implement your own dynamic array (or use an existing implementation) by making good use of realloc for example :

        http://www.cplusplus.com/reference/clibrary/cstdlib/realloc/
0
phoffricCommented:
For C++ if it's really vectors that you are interested in ..
Here is some source code using vector:
    http://www.yolinux.com/TUTORIALS/LinuxTutorialC++STL.html#VECTOR

And here are 3 pages in a paper on vector:
   http://see.stanford.edu/materials/icsppcs107/03-Introducing-The-STL.pdf

For C, if it's just learning about Dynamic Arrays, here's an online book that may help:
   http://publications.gbdirect.co.uk/c_book/
Section 5.5 of this book begins discussion of dynamic allocation
   http://publications.gbdirect.co.uk/c_book/chapter5/sizeof_and_malloc.html
But before hitting that section, make sure you have mastered sections 5.1-5.4
   http://publications.gbdirect.co.uk/c_book/chapter5/


0
SmanyxAuthor Commented:
Thanks for the links provided, this should keep me busy in discovery land...

I had in mind dynamic arrays in C.
What I want to achieve is write a small program that prompts the user to enter for a name and store that name into an array of strings. Since we don't know how many names will be entered by the user, the array needs to be able to resize itself.

Below is the code I have written. But it's not working. I am getting two errors:

error C2133: 'Names' : unknown size
error C2440: '=' : cannot convert from 'char *' to 'char [][25]'

How can I improve it?


#include <stdio.h>
#include <stdlib.h>

int main ()
{
	int i = 0;
	char Names[][25];

	puts("\nEnter EOF (Ctrl + Z) to end Input");
	do
	{
		printf("\nPlease enter a name: ");
		gets(Names[i]);
		i++;
		Names = (char *) realloc (Names, i * sizeof (char));
		printf("\nPlease enter a name: ");
	}while(!feof(stdin));

	printf ("Names entered: ");
    for (int n = 0; n<i; n++) 
	{
		printf ("%s ",Names[n]);
	}
    free (Names);

	getchar();
	return 0;
}

Open in new window

0
Managing Security & Risk at the Speed of Business

Gartner Research VP, Neil McDonald & AlgoSec CTO, Prof. Avishai Wool, discuss the business-driven approach to automated security policy management, its benefits and how to align security policy management with business processes to address today's security challenges.

phoffricCommented:
The following will allow you to get 25 names of varying length. But then you should get your name in a temporary c-string, and then malloc the necessary size; and then copy the temp string into the malloc'd area.
char *Names[25];

Open in new window

0
SmanyxAuthor Commented:
>>>The following will allow you to get 25 names of varying length. But then you should get your name in >>>a temporary c-string, and then malloc the necessary size; and then copy the temp string into the >>>malloc'd area.

But what I want is unlimited number of names all being 25 char in Length. How do I get that?
0
phoffricCommented:
Then define Names as:
   char ** Names;
You can treat Names as an array of pointers of type char *
Start off by allocating room for a reasonable number of these pointers.
If you exceed this room, then is a good time to realloc to extend the number of pointers.
Are you planning on deleting names as well?
0
phoffricCommented:
Since you know the name length is exactly 25 chars, then after creating the pointer(s), you can immediately malloc 26 bytes (one extra for the terminating null byte). If you do it this way, you will not need a temporary name. The temp name was needed if you didn't know the size of the name. In that case you have what is sometimes known as a ragged array - it's a matrix whose rows have different lengths.
0
phoffricCommented:
The example here
      http://www.cplusplus.com/reference/clibrary/cstdlib/realloc/
does what you are doing, reallocating memory in every loop. That can lead to virtual memory fragmentation as well as excessive copying.

Alternatively, you could define chunks of pointers at a time, say 25 (or any other chunk that you decide):
     #define NUM_PTR_CHUNKS 25
Then you just keep track of how many pointers are already used, and when you run out, realloc a larger amount, not for one pointer but, say, for an additional NUM_PTR_CHUNKS.

In some applications, even this approach may be not resourceful enough. So, the new size may be instead something like 1.5 * (current number of pointers allocated). So, the first reallocation doesn't even double; but when you have say about 1000 pointers defined, now you are adding 500 for a total of 1500 pointers (and then you malloc the 26 chars for those 500 new pointers).

Even though you could still use your
     gets(Names[i]);
since the 26 chars are already allocated, for more robustness, it might be better to have a temporary variable of say, 256 bytes, for the gets, so that if someone falls on the keyboard too long, then there is less chance of overrunning the malloc memory. Then you check and truncate the size of the input.

But for that same reason, gets is not a good function. If you sleep too long on the keyboard, that too will cause an overrun. So, I would switch to fgets instead - it allows you to limit the max number of chars written to your buffer to prevent an overrun.
      http://www.cplusplus.com/reference/clibrary/cstdio/fgets/
Now, you don't need a temp buffer unless you want to detect that an overrun has occurred. In this case make your temp buffer a little bigger than the size of any name (say, 30), and then do a strlen on this temp string. If it is > 25, then report an error (and truncate, of course).

(Note, for Console input, the fgets 3rd argument is stdin.)
0
Infinity08Commented:
>> But what I want is unlimited number of names all being 25 char in Length. How do I get that?

Something like below. Note that the typedef was added for your convenience, so you don't have to mess with pointers too much.
The code allocates an initial size of the array using malloc (1 name in this case). If the array is full, realloc can be used to increase the size of the array, in order to be able to add more names.
Similarly, realloc can be used to decrease the size of the array when needed.

I also recommend using a struct like this to formalize a vector of names :

        typedef struct NameVector {
          Name* data;
          size_t allocated_size;
          size_t size;
        } NameVector;

That way, you can keep track of the allocated size of the array, as well as the currently used size. You can then write several functions that manipulate the contents of the vector (add a name, remove a name, etc.).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char Name[25];

int main(void) {
  Name* names = (Name*) malloc(1 * sizeof(Name));

  strncpy(names[0], "George", 25);

  { /* increase the size of the array : */
    Name* tmp = (Name*) realloc(names, 2 * sizeof(Name));
    if (!tmp) {
      /* re-allocation failed : handle this error !!!! eg. by : */
      exit(1);
    }
    names = tmp;
  }

  strncpy(names[1], "Michael", 25);

  /* ... */

  free(names);

  return 0;
}

Open in new window

0
SmanyxAuthor Commented:
Infinity08: I tried to run the program you have suggested but for some reasons it's not working.
But I went through it, trying to understand what it does and adapt it to my situation, given that I need to get input from the user.
Below is the code I have, unfortunaltely it's not also working ...
Could you guys  please check it and make suggestions, thanks.
#include <stdio.h>
#include <stdlib.h>

//create an array of type Name being 25 char in Length
typedef char Name[25];  

int main (void)
{
	//names is a ptr of type Name with an initial size allocate using malloc
	Name* names = (Name*) malloc(1 * sizeof(Name));  
	int i = 0;   //count of array index

	puts("To end, press EOF (Ctrl + Z)");
	printf("\nPlease enter a name: ");
	while (!feof(stdin))
	{
		gets(names[i]);
		{
			//increase the size of the array
			Name* tmp = (Name* )realloc(names, 2 * sizeof(Name));
			if (!tmp)
			{
				//check whether realloc did work and act accordingly
				exit(1);
			}
			names = tmp;
		}
		i++;
		printf("\nPlease enter a name: ");
	}

	printf ("\nList of names entered: \n\n");
	printf("====================\n");
    for (int n = 0; n<i; n++) 
	{
		printf ("%s ",names[n]);
	}
   	free(names);
	printf("\n\n\nJob done!");
	getchar();
	return 0;
}

Open in new window

0
Infinity08Commented:
>>                         //increase the size of the array
>>                         Name* tmp = (Name* )realloc(names, 2 * sizeof(Name));

This changes the size of the array to 2. Since you have this in a loop, for the next iteration, you'll obviously have to change it to 3, and then to 4, etc.
So, you have to keep track of the current size of the array (which is why I recommended using something like the NameVector struct from my previous post), so you know whether you need to increase the size, and by how much.

In your code sample (from your previous post), you are using i to track the size of the array, so make sure to also use i appropriately when realloc-ing the array.


>>                 gets(names[i]);

Be careful here not to enter a name longer than 24 characters !!! It's best to build in some security (by using strncpy eg.).
0
SmanyxAuthor Commented:
Am I getting any closer or just losing bearings ??

I still can't compile the code, I am getting the following error messages:

1>Linking...
1>MSVCRTD.lib(crtexew.obj) : error LNK2019: unresolved external symbol _WinMain@16 referenced in function ___tmainCRTStartup

...\dynamicArray2\Debug\dynamicArray2.exe : fatal error LNK1120: 1 unresolved externals

Which does not allow me to get a clue of what I am doing right or wrong...

Also,
>>>So, you have to keep track of the current size of the array (which is why I recommended using >>>something like the NameVector struct from my previous post), so you know whether you need to >>>increase the size, and by how much.

Can I use for example an expression like :
Name* names = (Name*) realloc (names, (NameVector.size + 1) * sizeof(Name)); ???


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include "NameVector.h"


//create an array of type Name being 25 char in Length
typedef char Name[25];  

typedef struct NameVector 
{
          Name* data;
          size_t allocated_size;
          size_t size;
} NameVector;


int main (void)
{
	//names is a ptr of type Name with an initial size allocate using malloc
	Name* names = (Name*) malloc(1 * sizeof(Name));  
	int i = 0;   //count of array index

	puts("To end, press EOF (Ctrl + Z)");
	printf("\nPlease enter a name: ");
	while (!feof(stdin))
	{
		strncpy(names[i],"%s",25);
		{
			//increase the size of the array
			Name* tmp = (Name* )realloc(names, (i + 2) * sizeof(Name));
			if (!tmp)
			{
				//check whether realloc did work and act accordingly
				exit(1);
			}
			names = tmp;
		}
		i++;
		printf("\nPlease enter a name: ");
	}

	printf ("\nList of names entered: \n\n");
	printf("====================\n");
    for (int n = 0; n<i; n++) 
	{
		printf ("%s ",names[n]);
	}
   	free(names);
	printf("\n\n\nJob done!");
	getchar();
	return 0;
}

Open in new window

0
Infinity08Commented:
>> 1>MSVCRTD.lib(crtexew.obj) : error LNK2019: unresolved external symbol _WinMain@16 referenced in function ___tmainCRTStartup

It seems your project settings are wrong. You need to create a console project, not a Windows application project.

>> Can I use for example an expression like :
>> Name* names = (Name*) realloc (names, (NameVector.size + 1) * sizeof(Name)); ???

Good start, but three remarks :

(a) the allocated_size keeps track of the currently allocated size of the array. When deciding to increase or decrease the size of the array, this is the value you should look at. Remember that the allocated size is not necessarily the same as the occupied size. For example, you could allocate enough memory for 10 names, but only use 5 of them (the other 5 are already allocated, in case they're needed in the future - allocation is costly, so you want to limit the amount of allocation requests as much as possible).

(b) don't forget to also modify the size and allocated_size fields to reflect the reality.

(c) NameVector is a type, so you cannot use it as if it were an instance. You need to use the instance of the type when accessing its members. This might be a good time to read up on structs :

        http://www.cplusplus.com/doc/tutorial/structures/
0
SmanyxAuthor Commented:
At this stage, the program is running and I have attached the sample screen output. But, the problem is, like you said, with names that are longer than 25 char. You suggested I use strncpy.
Looking at the second code, I have submitted, I am trying that store the name first in a variable, then call strncpy. I am not sure in it's the right approach.Also, since strncpy does not add automatically the '\0' char, how do I deal with that?

>>>NameVector is a type, so you cannot use it as if it were an instance. You need to use the instance >>>of the type when accessing its members.
I am still confused about how to implement the NameVector in my example code.
In the second code, I am trying to use that, but I am not sure whether I am in the right path or losing the point... If NameVector is a type, I need to have a variable of NameVector type, right!?
In declaring NameVector myNames;  myNames.data should be where I will store the name entered from the keyboard...
Please have a look at the code and let me know.

>>>don't forget to also modify the size and allocated_size fields to reflect the reality.
how?
FIRST CODE:
===========
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include "NameVector.h"


//create an array of type Name being 25 char in Length
typedef char Name[25];  

typedef struct NameVector 
{
          Name* data;
          size_t allocated_size;
          size_t size;
} NameVector;


int main (void)
{
	//names is a ptr of type Name with an initial size allocate using malloc
	Name* names = (Name*) malloc(1 * sizeof(Name));  
	int i = 0;   //count of array index

	puts("To end, press EOF (Ctrl + Z)");
	printf("\nPlease enter a name: ");
	gets(names[i]);
	while (!feof(stdin))
	{
		//increase the size of the array
		Name* tmp = (Name* )realloc(names, (i + 2) * sizeof(Name));
		if (!tmp)
		{
			//check whether realloc did work and act accordingly
			exit(1);
		}
		names = tmp;
		i++;
		printf("\nPlease enter a name: ");
		gets(names[i]);
	}

	printf ("\nList of names entered: \n\n");
	printf("====================\n");
    for (int n = 0; n<i; n++) 
	{
		printf ("\n%s ",names[n]);
	}
   	free(names);
	printf("\n\n\nJob done!");
	getchar();
	return 0;
}

/*
SAMPLE PROGRAM OUTPUT:
======================

To end, press EOF (Ctrl + Z)

Please enter a name: Africa

Please enter a name: America

Please enter a name: Asia

Please enter a name: Europe

Please enter a name: Oceania

Please enter a name: ^Z

List of names entered:

====================

Africa
America
Asia
Europe
Oceania


Job done!
*/


SECOND CODE:
============
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include "NameVector.h"


//create an array of type Name being 25 char in Length
typedef char Name[25];  

struct NameVector 
{
          Name* data;
          size_t allocated_size;
          size_t size;
};


int main (void)
{
	NameVector myNames;
	myNames.allocated_size = 1;
	//names is a ptr of type Name with an initial size allocate using malloc
	Name* names = (Name*) malloc(myNames.allocated_size * sizeof(Name));  
	int i = 0;   //count of array index
	char A_name[100];

	puts("To end, press EOF (Ctrl + Z)");
	printf("\nPlease enter a name: ");
	gets(A_name);
	while (!feof(stdin))
	{
		strncpy(names[i], A_name, 25);
		//increase the size of the array
		Name* tmp = (Name* )realloc(names, (myNames.allocated_size + 2) * sizeof(Name));
		if (!tmp)
		{
			//check whether realloc did work and act accordingly
			exit(1);
		}
		names = tmp;
		
		strncpy(myNames.data, names[i],25);
		i++;
		printf("\nPlease enter a name: ");
		gets(A_name);
	}
	

	printf ("\nList of names entered: \n\n");
	printf("=====================\n");
    for (int n = 0; n<i; n++) 
	{
		printf ("\n%s ",names[n]);
	}
   	free(names);
	printf("\n\n\nJob done!");
	getchar();
	return 0;
}

Open in new window

0
Infinity08Commented:
>> Looking at the second code, I have submitted, I am trying that store the name first in a variable, then call strncpy.

That looks ok. Keep in mind that the limit is now 99 characters for a name !!

Note also that an array of 25 char's can only hold a string of 24 characters, not 25. So, when using the strncp, use 24 as the size, not 25.


>> Also, since strncpy does not add automatically the '\0' char, how do I deal with that?

You add it yourself :)

        strncpy(names[i], A_name, 24);
        names[i][24] = '\0';


>> I am still confused about how to implement the NameVector in my example code.

The NameVector type simply groups all information related to a dynamic array of names. It has a pointer to the array, as well as the allocated and used sizes.
The idea is to use this NameVector whenever you need a dynamic array of names, and to write some functions that manipulate it (addName, getName, etc.). You can then call those functions to operate on the dynamic array.


>>       NameVector myNames;
>>       myNames.allocated_size = 1;

Make sure to also initialize the size to 0.

>>       Name* names = (Name*) malloc(myNames.allocated_size * sizeof(Name));

Make that :

        myNames.data = (Name*) malloc(myNames.allocated_size * sizeof(Name));

We no longer use the names array.

>>             strncpy(names[i], A_name, 25);

Make that :

        strncpy(myNames.data[i], A_name, 24);

Before copying anything into a position in the array, you need to check whether there is room enough in the array, and if not, increase the size of the array (check the allocated_size variable for that).
After copying, you need to set the size variable to the currently used size.

>>             Name* tmp = (Name* )realloc(names, (myNames.allocated_size + 2) * sizeof(Name));

Make that :

        Name* tmp = (Name* )realloc(myNames.data, (myNames.allocated_size + 1) * sizeof(Name));

followed by :

        myNames.data = tmp;

if tmp was not NULL.

After the realloc, you need to modify the allocated_size variable to the currently allocated size.

>>             strncpy(myNames.data, names[i],25);

This is wrong, so it shouldn't be there. See above.

>>             i++;

You don't need to use i any more, since you keep track of the array's size in the size variable.

>>             printf ("\n%s ",names[n]);

Here also, you need to use myNames.data instead of names.

>>          free(names);

Here also, you need to use myNames.data instead of names.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
SmanyxAuthor Commented:
This question is definitely worth more points...

Okay, the program I have now is not allowing to enter more than two names. I don't understand why!?
If more than 2 names are entered, the following error message pops up:

"Windows has triggered a breakpoint in dynamicArray5.exe.

This may be due to a corruption of the heap, and indicates a bug in dynamicArray5.exe or any of the DLLs it has loaded.

The output window may have more diagnostic information"

What could possibly be going wrong here?

Please look at the code below. I have also attached the output for up to two names. If the name is longer than 25 char, it truncates it.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include "NameVector.h"


//create an array of type Name being 25 char in Length
typedef char Name[25];  

struct NameVector 
{
          Name* data;
          size_t allocated_size;
          size_t size;
};


int main (void)
{
	NameVector myNames;
	myNames.allocated_size = 1;
	myNames.size = 0;
	
	myNames.data = (Name*) malloc(myNames.allocated_size * sizeof(Name));
	int i = 0;   //count of array index
	char A_name[100];

	puts("To end, press EOF (Ctrl + Z)");
	printf("\nPlease enter a name: ");
	gets(A_name);
	while (!feof(stdin))
	{
		strncpy(myNames.data[i], A_name, 24);
		myNames.data[i][24] = '\0';
		//increase the size of the array
		Name* tmp = (Name* )realloc(myNames.data, (myNames.allocated_size + 1) * sizeof(Name));
		
		if (!tmp)
		{
			//check whether realloc did work and act accordingly
			exit(1);
		}
		myNames.data = tmp;
		myNames.size += 1;
		i++;
						
		printf("\nPlease enter a name: ");
		gets(A_name);
	}
	

	printf ("\nList of names entered: \n\n");
	printf("=====================\n");
    for (int n = 0; n < myNames.size; n++) 
	{
		printf ("\n%d. %s ",n +1, myNames.data[n]);
	}
   	free(myNames.data);
	printf("\n\n\nJob done!");
	getchar();
	return 0;
}
/*SAMPLE SCREEN OUTPUT:
=======================
To end, press EOF (Ctrl + Z)

Please enter a name: Priscillia Martha Des Bellanges

Please enter a name: El Placido Fiore Dell'Acqua

Please enter a name: ^Z

List of names entered:

=====================

1. Priscillia Martha Des Be
2. El Placido Fiore Dell'Ac


Job done!

*/

Open in new window

0
Infinity08Commented:
>> Okay, the program I have now is not allowing to enter more than two names. I don't understand why!?

That's because you haven't incremented allocated_size after the realloc. At all times, allocated_size should contain the exact size of the array. So, when you increase its size by 1, you also need to adjust allocated_size accordingly.

The rest looks pretty good. We can talk about improvements (I have a few in mind) after it's working ;)
0
phoffricCommented:
>> But what I want is unlimited number of names all being 25 char in Length. How do I get that?
>> If the name is longer than 25 char, it truncates it.
Haven't looked at this in much detail, but your above two remarks seems consistent to me.

If you want names of variable lengths that can be any length, then consider the ragged array approach mentioned in http:#29614067 and you can use char ** mentioned earlier.
Or, you can
    typedef char * Name;
if you prefer and then create
   Name * Name_List;
and follow similar patterns as noted above.
0
SmanyxAuthor Commented:
I have added this line:
myNames.allocated_size += 1;
and it working just fine now.
I am going to close this question now, even though I will be looking at getting unlimited number of names of different length very shortly.
Thank you to all of you for your help and input.

Smanyx.
0
SmanyxAuthor Commented:
>>>>>             i++;

>>>You don't need to use i any more, since you keep track of the array's size in the size variable.

Infinity08, I looked very carefully at my code, the program is running fine, but I noticed that I am still using the variable i. I replace every occurence of i by myNames.size and it's working too.

In terms of efficiency, how would that be any better using myNames.size rather than i?
0
Infinity08Commented:
>> In terms of efficiency, how would that be any better using myNames.size rather than i?

Don't worry about efficiency. The compiler takes care of that ;)

The idea is to have a self-contained type. All the functionality you now have in main, should be split up in separate functions that perform certain operations on the NameVector struct (like adding a new name, retrieving a name, etc.). Your main code will then simply call these functions, and the implementation details (like the allocated_size and the reallocs) will be hidden from view (they become an implementation detail).

Finally, you can then bundle the NameVector struct and all its functions in a separate compilation unit with its own header file. You now have a new type, that can easily be used and re-used.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.