Memory management(array of char arrays)

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Syntaxide
Posts: 3
Joined: Wed Feb 18, 2009 1:21 am UTC

Memory management(array of char arrays)

Postby Syntaxide » Wed Feb 18, 2009 1:35 am UTC

Alright, so I'm looking to make an array of the following structure:

Code: Select all

struct item{
  double price;
  char *name;
  char *url;
}


Unfortunately, reserving space is complicated, as I do not know in advance how long the names or urls will be. I realize I could declare my "strings" as arrays rather than pointers, but I'm looking to make a very efficient program. Reserving extra space isn't what I'm looking for.

Whats the best way to handle this situation? Please excuse my probably obvious problem; I've worked with c(++) for quite a while now, but I've not yet run into this.

User avatar
Xeio
Friends, Faidites, Countrymen
Posts: 5101
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

Re: Memory management(array of char arrays)

Postby Xeio » Wed Feb 18, 2009 1:51 am UTC

Well, assuming you still want constant time index-based lookup, you could allocate an array, and when you need more space, allocate a new, larger array, and copy everything in from the old one. It's a bit space expensive, and the add that causes the expansion would take longer than normal, but it works if you want to maintain a single array. I assume there is already an ArrayList of sorts for C++ in the standard library which does this.

I'm not sure what exactly you meant by 'reserving space is complicated' though. Does this mean you have a lack of space? Or that you don't want to have to allocate very often?

Karrion
Posts: 92
Joined: Fri Jun 22, 2007 12:14 am UTC
Location: Melbourne, AU

Re: Memory management(array of char arrays)

Postby Karrion » Wed Feb 18, 2009 2:05 am UTC

Syntaxide wrote:Unfortunately, reserving space is complicated, as I do not know in advance how long the names or urls will be. I realize I could declare my "strings" as arrays rather than pointers, but I'm looking to make a very efficient program. Reserving extra space isn't what I'm looking for.


Normally you would allocate your array of items (or a linked list or whatever), and then the char* values in each item would point to separately allocated memory holding the strings. So whenever you initialise an item, you would malloc() each of the string values with the correct length, and when you're done with any item, you would free() them.

boss_mc
Posts: 47
Joined: Thu Oct 04, 2007 12:03 am UTC

Re: Memory management(array of char arrays)

Postby boss_mc » Wed Feb 18, 2009 2:09 am UTC

It seems to me that the name/url of each item will only be set once. In which case, at that point, you know how long the strings need to be and can dynamically allocate the required amount of memory.

If on the other hand you want to be able to resize the strings later, you may wish to look at what the C++ string class does for memory management. As I recall the string is stored in an array and when that array is full a new array of twice the size is allocated and the contents of the first are copied to the second (as Xeio was suggesting). If you are worried about this wasting space, the string class also has a method which allows you to shrink the allocated space down to the size of the current contents.

You could use a string (or any other variable sized structure i.e. std::vector) which would handle this for you but if you roll your own you will have much better control over the memory micro management.

EDIT: Ninja'd my first point but the second still stands (even if you are working in pure C, but then it is a little more complex due to lack of classes...)
while ((*(iterator++) != (LExpression*)next) && (iterator != m_vector.end()){}

User avatar
Area Man
Posts: 256
Joined: Thu Dec 25, 2008 8:08 pm UTC
Location: Local

Re: Memory management(array of char arrays)

Postby Area Man » Wed Feb 18, 2009 2:11 am UTC

"Efficiency" is a choice between computation (time) vs. storage (space) resources.
Seems you are at the beginning of a project and may be prematurely concerned with optimization.

If this is C++ you could use <string>, which would manage itself; otherwise, if memory conservation is a serious concern already, you could count the chars in a temp string then malloc() the required space, at the price of going over the url twice (depending on where it's coming from; how many "items" does your program need to hold in core at once, anyway?)
Bisquick boxes are a dead medium.

User avatar
yy2bggggs
Posts: 1261
Joined: Tue Oct 17, 2006 6:42 am UTC

Re: Memory management(array of char arrays)

Postby yy2bggggs » Wed Feb 18, 2009 5:39 am UTC

Just use a std::string. If memory is as big of an issue as people here are supposing it might be, you would probably need to design your own memory manager anyway, and would need to custom fit it to your application; simply "mallocing what you need" won't accomplish much more than memory fragmentation otherwise.
Image

ThomasS
Posts: 585
Joined: Wed Dec 12, 2007 7:46 pm UTC

Re: Memory management(array of char arrays)

Postby ThomasS » Wed Feb 18, 2009 6:03 am UTC

"Premature optimization is the root of all evil (or at least most of it) in programming." - Knuth

That said, if you realy want to optimize a data structure, you have to consider how it will be used. Do the strings change? Often? Will the objects be thrown on the stack, allocated dynamically, or both? Will you be passing them around a lot, or will they sit in array and accessed from it without being copied? If not on the stack, will allocation and deallocation be interwoven, or will you allocate a bunch and then drop them all? There are lots of tricks that can be used to make things faster/smaller/better, but which you can use depends on the situation.

The problem, or at least a problem that Knuth is getting at is that you write assuming one way, spend time putting in tricks to improve your overall performance by a few percent, and then have to redo it when the situation changes. So the right thing probably is to use std::string, unless you A) have a pretty good sense of the answers to all those questions and B) know that you'll be creating a zillion of these things with short strings.
Last edited by ThomasS on Thu Feb 19, 2009 2:16 pm UTC, edited 1 time in total.

Grumpy Code Monkey
Posts: 99
Joined: Tue Feb 19, 2008 4:10 pm UTC
Location: Blue Texas

Re: Memory management(array of char arrays)

Postby Grumpy Code Monkey » Wed Feb 18, 2009 4:17 pm UTC

Is this C or C++? Several people have suggested the right C++ answer, but it would help to know what language you're really using.

If C++, the answer is as simple as this:

Code: Select all

#include <string>
#include <vector>

struct item {double price; std::string name; std::string url;};
std::vector<item> myItems;


The string and vector classes handle all the memory management for you. The vector will grow as you add items, and the strings will size themselves appropriately.

If C, the answer is a bit more complicated. I'd post an example, but I don't want to waste anyone's time if that's not the environment you're working in.

User avatar
yy2bggggs
Posts: 1261
Joined: Tue Oct 17, 2006 6:42 am UTC

Re: Memory management(array of char arrays)

Postby yy2bggggs » Thu Feb 19, 2009 7:06 am UTC

Grumpy Code Monkey wrote:...
The string and vector classes handle all the memory management for you. The vector will grow as you add items, and the strings will size themselves appropriately.

A deque may be preferred to a vector, depending on what you're doing. I can discuss it more, if I knew more of what you were doing :).
Image

User avatar
tetsujin
Posts: 426
Joined: Thu Nov 15, 2007 8:34 pm UTC
Location: Massachusetts
Contact:

Re: Memory management(array of char arrays)

Postby tetsujin » Thu Feb 19, 2009 5:14 pm UTC

Grumpy Code Monkey wrote:The string and vector classes handle all the memory management for you. The vector will grow as you add items, and the strings will size themselves appropriately.


Vector growth can be a bitch, though. When a vector automatically resizes itself, it doubles in size in order to delay the next time it has to resize - and each resize requires allocating the new buffer, copying all the elements, and then deallocating the old buffer... As the data gets larger or memory fragmentation increases, this can become a real problem - for instance, running out of space for a contiguous allocation large enough for the whole vector (enough free memory for the data, just not all in one place) - or having enough memory for the vector's new size, but not for both the old and new copies in memory at the same time...

I wouldn't worry about all that until it is clear that it really is a problem in the place where you're trying to use vector - which may be never... But it has been a periodic frustration for me in my work.


...So... Ignore everything I just said, and implement a std::vector of structs containing std::strings, like people have been saying. :D
Either that, or go the C route - in which case the important thing is to keep all the structure data in a manageable state (for instance, make sure the string pointers are 0 unless they are set to something - in which case they should probably point to their own private copy of the string data...) Writing accessor functions to manage your data can be helpful in this regard.
---GEC
I want to create a truly new command-line shell for Unix.
Anybody want to place bets on whether I ever get any code written?

Syntaxide
Posts: 3
Joined: Wed Feb 18, 2009 1:21 am UTC

Re: Memory management(array of char arrays)

Postby Syntaxide » Thu Feb 19, 2009 10:28 pm UTC

Ah, I probably should've posted more information. As of now I have a working program in C++ with memory leaks. I figured that if I went with pure C, I'd be restricted to malloc and would be easier to track my leaks.

Yes, I could use Strings in C++. What would be the alternative for C?

ThomasS
Posts: 585
Joined: Wed Dec 12, 2007 7:46 pm UTC

Re: Memory management(array of char arrays)

Postby ThomasS » Thu Feb 19, 2009 10:47 pm UTC

Syntaxide wrote:Ah, I probably should've posted more information. As of now I have a working program in C++ with memory leaks. I figured that if I went with pure C, I'd be restricted to malloc and would be easier to track my leaks.

Yes, I could use Strings in C++. What would be the alternative for C?


The equivalent of C is malloc, which means that you must know when to deallocate. You can do a lot with C++ constructors and destructors to help avoid memory leaks (often at some small performance cost). In fact, this is what std::string is doing under the covers. On a related note, check out the free boost smart pointer library. When used correctly these sorts of techniques make memory management easier in C++ than in C, though sometimes one does pine for garbage collecting systems.

Regarding memory leak hunting in general, have you ever used valgrind?

User avatar
tetsujin
Posts: 426
Joined: Thu Nov 15, 2007 8:34 pm UTC
Location: Massachusetts
Contact:

Re: Memory management(array of char arrays)

Postby tetsujin » Thu Feb 19, 2009 10:56 pm UTC

Syntaxide wrote:Ah, I probably should've posted more information. As of now I have a working program in C++ with memory leaks. I figured that if I went with pure C, I'd be restricted to malloc and would be easier to track my leaks.

Yes, I could use Strings in C++. What would be the alternative for C?


What C++ brings to the table here is the ability to manage the lifetime of an allocation according to the scope in which it appears. So, for instance, if your struct includes std::string fields, the memory allocated by those string objects will be cleaned up when the struct is destroyed...

If you destroy the struct improperly, however, the fields inside it won't be deallocated. It's hard to guess what's going wrong, but here are a couple possibilities:
  • You're deallocating a struct with "free" instead of "delete"
  • You're deallocating an array of structs with "delete" instead of "delete[]"

The other advantage provided by C++ is that it gives you organizational facilities (classes, etc.) to more logically organize your code - so if you did a more C-like approach to this thing, but in C++ (using char* in your struct, etc.), C++ would still give you a way to tie that code to the object it's supposed to operate upon, rather than cluttering up a single namespace with functions meant to deal with a single data type...


The alternative in C would be char* fields inside your struct - the allocations to which those char* fields point would have to be managed as part of your management of the structs. (So, for instance, if you initialized one with a literal string, or with a pointer into a buffer managed by someone else, you wouldn't want to try free()ing that... but if you initialized the text field by malloc()ing it and copying string data into the new buffer, that's a pointer you would want to free() when you're done with the struct... Keeping track of whether the pointer should be freed when the struct is destroyed is generally more effort than it's worth, however - generally I'd say it's better to just unconditionally make new copies of the string, unless there's a good reason not to...)

As an example (in C):

Code: Select all

typedef struct {
    double price;
    char *name;
    char *url;
} item;

typedef struct {
    item* items;
    unsigned int item_count;
    unsigned int item_capacity;
} item_list;


/* Initialized a new item list */
void item_list_init(item_list* items)
{
    items->items = 0;
    items->item_count = 0;
    items->item_capacity = 0;
}


void item_list_reserve(item_list* items, unsigned int count)
{
    items->items = realloc(items->items, (count * sizeof(item)));
    items->item_capacity = count;
}


/* Add an item to an item list */
void add_item(item_list* items, double price, char* name, char* url)
{
    if (items->item_count == items->item_capacity)
    {
        /* Need to make the item list bigger first... */
        item_list_reserve(items, items->item_capacity * 2);
    }

    item* new_item = &items->items[items->item_count];
    new_item->price = price;
    new_item->name = malloc(strlen(name) + 1);
    strcpy(new_item->name, name);
    new_item->url = malloc(strlen(url) + 1);
    strcpy(new_item->url, url);

    items->item_count++;
}


/* deallocate an item list */
void item_list_destroy(item_list* items)
{
    unsigned int cc;

    for (cc = 0; cc < items->item_count; cc++)
    {
        free(items->items[cc].name);
        free(items->items[cc].url);
    }
    free(items->items);
}


There, doesn't that look like fun? :D

Also note there's no error handling in the above code... it's just assumed the mallocs/reallocs will succeed.
---GEC
I want to create a truly new command-line shell for Unix.
Anybody want to place bets on whether I ever get any code written?


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 6 guests