• Advertisement

Archived

This topic is now archived and is closed to further replies.

Dynamically allocated arrays

This topic is 6059 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Is there any other way to do dynamically allocated arrays than to do those link-list (each entity contains pointer to the next one)? How do you solve such problems in your applications? Thanks a lot

Share this post


Link to post
Share on other sites
Advertisement
I think I know what you mean. What I would do if I wanted a dynamically created array is write code like this:

int *newArrayInt;

newArrayInt = (int *)malloc(array_size * sizeof(int));

then you will be able to use this array of memory decalred for use and free it by doing this

free (newArrayInt);

Simple.. But what is more simple.. if the array you intend on using is local in a function and at the time of execution you want a new array then if you know the size then you can just do this

size=574776;

int newArrayInt[size];

which would do the same as above.

I am not sure If I answered your question properly... I hope I did

Dark Star
UK

Share this post


Link to post
Share on other sites
No, this is not my problem. Assume you have a structure containing some information. And I need to have an array containing any amount of these structure (that''s what you''ve explained) but I also need to add new entities to it anytime. I may also create a new array of the desired size and copy the previous to it and then add the new entities, but that''s not an exellent solution anyway.

Share this post


Link to post
Share on other sites
I think I understand what you want. You could use the realloc function. Just pass the pointer to the memory you allocated and the new size, and it will just allocate more memory in the same space, or if it can''t it will find a new area of memory and copy the old data into it. That way you can change the size of your array at any time and keep all the contents of it intact so you can add more data to it.

I hope this is what you were asking for, if not explain it again.

Share this post


Link to post
Share on other sites
Hi Caesar...

Well noparity had a good idea about using the vector. And a linked list probably wouldn''t be too bad either.

But basically there is no way to dynamically grow an actual array without reallocating and copying. That is basically what realloc does and you could probably do it more efficiently yourself.

Personally I would use a vector, or if the information needed to be accessed faster than a vector would allow I would just make my initial array as big as I will ever need it and just keep adding to it. As long as I don''t expect it to be too horrendously big. A few hundred-thousand elements would probably be my limit. Memory is cheap these days. Reallocating and copying on the fly everytime you needed to add an element would murder your performance. There aren''t alot of operations that are slower than memory allocation

Another option would be that when you reallocate don''t just reallocate for a single new element. Set your array at a reasonable size at first, if you reach that limit reallocate enough memory to store maybe 100 or 1000 more elements. This way you only have to reallocate once in a while. But if you start getting a large number of elements, copying to the new memory will still be slow.

Seeya
Krippy

Share this post


Link to post
Share on other sites
I think I''ll stay with my linked list. Thanks. But I''m still interested what are those vectors. Can someone explain that to me? Again, thanks to anyone who have answered...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
To use integer STL vectors:

#include

std::vectorintvector;

intvector.pushback(5);

// Now you have placed a new int value of 5 last in the list.

// You can also use the vector like a ordinary array
intvector[0] = 2;

// And you can get the last element in the list very easy and doesn´t need to have a variable that tells you how big the array is.
int lastvalue = intvector.front();

Share this post


Link to post
Share on other sites
STL's vector or list is the way you want to go. I know you're hung up on using a linked list, but my impression is that it doesn't matter how your items are all collected and handled, as long as you can access them similarly to a regular array but with the ability to add items dynamically.

Both vector and list have the same basic functions. For example, to find out how many items the object is holding, call size. To add an item to the end, call push_back. vector allows access with an array-style index, while list requires that you use iterators.

Internally, vector usually uses the realloc approach Midnight Coder mentioned. So, random access is extremely fast--as fast as with a regular array--but resizing is slow. If you know how many elements you'll need (like, say you have 5 now, and you know you're going to add 3 more), you can use the reserve function to reserve the necessary space to avoid the internal reallocation (you'd reserve space for 8 items in this case)--what this does is to grow the container, preserving all current items.

On the other hand, list is usually implemented as a linked list (relax about the linked lists, okay? ). This means that resizing is extremely fast, but random access isn't and there's nothing that can be done about that.

If I were you, I'd use vector--it's exactly a dynamic array...and much more.

Edited by - merlin9x9 on July 18, 2001 5:23:29 AM

Share this post


Link to post
Share on other sites
Fine, I''ll try both linked lists and vectors.

Btw. If I remember right, I may overload the [] to make the linked list accesable like an array, or not?

Share this post


Link to post
Share on other sites
Are you talking about linked lists or the STL''s list class? I assume you mean the latter (but don''t forget that because list is an abstract data type, there''s no guarantee that it''s implementation is a linked list). Since list has no operator[], there''s nothing to overload. You can''t derive a class from it because its data members are all private so you wouldn''t be able to access its data members from the derived class. Friend functions are out of the question as well for the aforementioned reason and that you can''t (shouldn''t) add the necessary prototypes to list''s definition. The only option if you absolutely must use list and refuse to use vector is something like this:

  
template<class T>
class mylist
{
typedef std::list<T>::size_type size_type;

std::list<T> m_list;

public:
size_type size() const {return m_list.size();}
void push_back(const T& item) {m_list.push_back[item]);
void clear() {m_list.clear();}

// decide how you''d want to implement these

T& operator[](size_type index); // for stuff like a[n] = x (assigning to an index)

const T& operator[](size_type index) const; // for stuff like x = a[n] (retrieving the value at an index)

}

// maybe add some more functions



But, please, use vector. I promise that it''s exactly what you want.

Share this post


Link to post
Share on other sites
Yeah, it''s strange, isn''t it?
STL is a part of the ISO-C++ standard but hardly anyone really knows how to use it or even that it exists. That''s weird!
And STL has got many advantages:
- it''s fast
- it''s comfortable
- it''s "memory safe" (it causes almost no memory leaks)
- you don''t have to reinvent the wheel

So why not use it????

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You can just add a funtion to your linked list class that
will create an array for you. i did this for various loaders.
Dynamic resizable arrays are possible with new and free also.
just a little tricky. if you want the snippet write to
Violent1

cu

Share this post


Link to post
Share on other sites
If you want a dynamic array, use vector.
If you want to waste lots of time, implement your own linked list.

Why write and debug code when you don''t have to?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I had to use a dynamically allocated array to create a triangle list loaded from a file - possibly make my own character model format. What I did is run through the file once using a blank while loop with a counter variable like this:

while( !filestream.eof() )
{
filestream >> temp;
counter++;
}

And then the counter variable(which should be initialized) hold the size of the array needed.

And you should allocate the memory to something simliary to this

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

Note I had to rush off this computer so there are probably errors in there...

Share this post


Link to post
Share on other sites
If you''re going to try STL, you should make a clear decision on what container to use--not just arbitrarily try vector and list.

If you need to pass array data to a C function, you must use a vector. Nothing else in STL guarantees contiguous memory.

If this is not an issue, the only remaining issue is efficiency. vector gives you efficient random access (operator [ ]). list does not. list gives you efficient insertions and deletions at any point in the sequence. vector does not. Hoever, vector is the fastest container with the least overhead if the data is only written once (i.e. at startup) or insertions and deletions only occur at the end of the sequence.

Share this post


Link to post
Share on other sites
Or if you feel like getting involved you could create your own Vector class which uses a combination linked-list and hash array with a background-thread for managing memory. This will give you a pretty good medium between a list and vector. It will not be as fast as vector for hardcore reading and writing of linear arrays, but if you play a little trickery it can become pretty close. And you maintain pretty much the same efficiency as a list for insertions.

A tip is to have your memory manager anticipate necessary memory loads by a little adjusted averaging so that when it is time to actually grow your array you don''t have to wait for reallocation, and you do not hog immense chunks of unnecessary memory in the meantime.

It loses a little bit of the general-purpose nature of vector and list, but it''s fairly trivial to tweak the averaging algorithms for different implementations to maintain constant efficiency.

Just a little nugget to think about in the future

Seeya
Krippy

Share this post


Link to post
Share on other sites
Even that I''m not decided what to use yet, I tried to write the linked list code, but I have a problem I cannot figure out. So, here it is. I know it could be written better, any suggestions are welcome...
  

typedef struct EXPRESSION{
char *string[2];
EXPRESSION *next;
}

class CDictonary{
protected:
EXPRESSION *first;
public:
first=new EXPRESSION;

void AddEx...
};

void CDictonary::AddExpression(char *string1,char *string2)
{
EXPRESSION *temp_expression;

temp_expression=first;

while(temp_expression->next!=NULL)
temp_expression=temp_expression->next;

temp_expression->next=new EXPRESSION;

if(temp_expression->next->next!=NULL)
delete temp_expression->next->next;
if(temp_expression->next->string[0]!=NULL)
delete temp_expression->next->string[0];
if(temp_expression->next->string[1]!=NULL)
delete temp_expression->next->string[1];

temp_expression->next->string[0]=new char[strlen(string1)];
temp_expression->next->string[1]=new char[strlen(string2)];

strcpy(temp_expression->next->string[0],string1);
strcpy(temp_expression->next->string[1],string2);
}


the code ussualy fails by the line chcecking if the string[0] is really NULL...

Share this post


Link to post
Share on other sites
I think your problem probably lies here:

temp_expression->next=new EXPRESSION;
if(temp_expression->next->next!=NULL)
delete temp_expression->next->next;


when you initialize temp_expression->next with new, it is not initializing temp_expression->next->next to anything. So the next line you are checking to see if temp_expression->next->next is NULL. More than likely it will not be NULL because it is not initialized yet. A pointer declaration does not start out as NULL, it starts out as whatever happens to be in memory at the time of creation.

Then you try to delete a memory allocation that doesn''t exist = crash. The same goes for the lines checking string[0] and string[1]. Those pointers are never initialized so they will not be equal to null nor will they point to valid data.

My suggestion is: since you are already using classes you should make EXPRESSION a class and add a default constructor which sets those pointers to NULL when it is created. And since you are creating temp_expression->next right there you don''t really need to do those checks that you are doing. There is no way they could be allocated if you just created the structure that holds them.

  
class EXPRESSION
{
public:
char* string[2];
EXPRESSION* next;

EXPRESSION(){ string[0] = NULL; string[1] = NULL; next = NULL; }
}


Hope this helps.

Seeya
Krippy

Share this post


Link to post
Share on other sites
Linked lists are not that bad.. if you need for control over the lists.. keep tabs of the various memory locations on where they are in the list.. that way you are not searching from the front of the list (or the back for a double linked list) to find your desired data. Yes, the code is ugly, but just use a couple of wrappers and don''t worry about it.

Share this post


Link to post
Share on other sites
Thanks Krippy, that''s probably the problem... To GoofProg, i do not claim my code is wonderful but I wonder what I should improve (I really wonder, I do not want to be ironic)

Share this post


Link to post
Share on other sites

  • Advertisement