Thread: dynamically creating an array of pointers

1. dynamically creating an array of pointers

Suppose I have a string that is defined at runtime. I want to create an array of pointers that points to the first character of each word in the string (assume a word is a series of characters delimited by whitespace). Is there a way to determine how big this array will need to be, so I can allocate the appropriate amount of memory for the pointers, without knowing exactly how many words there are in the string? If not, how would one go about creating this array?

2. Originally Posted by cs32
Suppose I have a string that is defined at runtime. I want to create an array of pointers that points to the first character of each word in the string (assume a word is a series of characters delimited by whitespace). Is there a way to determine how big this array will need to be, so I can allocate the appropriate amount of memory for the pointers, without knowing exactly how many words there are in the string? If not, how would one go about creating this array?

several approaches:
- If you are not limited with the space - there is not more words in a string then characters, use strlen() as a size for your array of pointers
- implement your own function that works like strlen but counts only spaces
- write function that counts words in string
- use some reasonable number to allocate the array at the beggining, use realloc to increase the array if it is not big enough

3. Originally Posted by vart
several approaches:
- If you are not limited with the space - there is not more words in a string then characters, use strlen() as a size for your array of pointers
- implement your own function that works like strlen but counts only spaces
- write function that counts words in string
- use some reasonable number to allocate the array at the beggining, use realloc to increase the array if it is not big enough
Thanks, Vart. Some follow up thoughts:

1. Does it make sense to create an array of pointers that might be bigger than what you actually need, but keep track of how much space you're actually using and free the rest when you've reached the end of the string? This might work with a small string, but I doubt this would be something I'd want to do when optimizing for space.

2. I was thinking that I'd optimize for time. Even though I'd be getting constant running time by reading the string multiple times to do the various calculations (i.e. determining the number of words/white-spaces/etc), would it make more sense to read the string only once, especially given the scenario where I could be reading a long string? What would you do? When would you choose differently? I guess benchmarking would provide the answers..

3. If I use realloc, and I declare/push additional variables onto the stack after the array has initially been declared, what happens? The array is no longer a contiguous block of memory, is it? How is this tracked internally?

Thanks!

4. Originally Posted by cs32
Thanks, Vart. Some follow up thoughts:

1. Does it make sense to create an array of pointers that might be bigger than what you actually need, but keep track of how much space you're actually using and free the rest when you've reached the end of the string? This might work with a small string, but I doubt this would be something I'd want to do when optimizing for space.
No it does not. You cannot free only part of allocated memory without moving the needed part to the new location. So it's of no use with such approach. Finish you business and free all the memory at once

Originally Posted by cs32
2. I was thinking that I'd optimize for time. Even though I'd be getting constant running time by reading the string multiple times to do the various calculations (i.e. determining the number of words/white-spaces/etc), would it make more sense to read the string only once, especially given the scenario where I could be reading a long string? What would you do? When would you choose differently? I guess benchmarking would provide the answers..
Depends what you mean by reading. General approach - read string onces into buffer, after that - work with the buffer. Too long is bigger than BUF_SIZ? If not - it's short enough

Originally Posted by cs32
3. If I use realloc, and I declare/push additional variables onto the stack after the array has initially been declared, what happens? The array is no longer a contiguous block of memory, is it? How is this tracked internally?

Thanks!
alloc/realloc work not with stack. but with heap.
if realloc cannot increase the current regeon - it will allocate the new regeon big enough and copy the old data to the new regeon, freeing the old regeon, so the data still be continuous (but from time to time realloc will include moving of long blocks of data - so it should not be called too often)

5. Another thing, if you don't care whether the original string is modified, you can use strtok().