Thread: dynamically creating an array of pointers

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    69

    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?

    Thanks in advance.

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by cs32 View Post
    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?

    Thanks in advance.
    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
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    69
    Quote Originally Posted by vart View Post
    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. #4
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by cs32 View Post
    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

    Quote Originally Posted by cs32 View Post
    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

    Quote Originally Posted by cs32 View Post
    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)
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  5. #5
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Another thing, if you don't care whether the original string is modified, you can use strtok().

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. MergeSort with array of pointers
    By lionheart in forum C Programming
    Replies: 18
    Last Post: 08-01-2008, 10:23 AM
  2. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  3. Replies: 5
    Last Post: 11-20-2001, 12:48 PM
  4. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM
  5. Creating an array of object pointers
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 10-08-2001, 10:01 PM