insert a char in the middle of a string

Discussion in 'C Programming' started by tano, Aug 9, 2004.

  1. tano

    tano Guest

    Hello,
    I have to insert a char in the middle of a string, I have written two functions
    but I don't know what is the better? The problem is: if I use malloc() I copy
    all the string with the new char in the middle every time, with realloc() the
    part of the string before the position where the char has to be inserted is not
    changed if realloc returns the same pointer is passed, but if not the
    string is copied at all the first time, and then the part after the char has to
    be shifted to right.. Perhaps it could be possible to make another function
    using the system call of the os (brk, sbrk)?
    Can anybody give me suggestions or clarify my ideas?
    Thanks,
    tano

    /* Code: the len is in memory, incremented after every insertion, so it
    doesn't need to compute it using strlen() */

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

    char* insert_char_malloc (char *str, int len, char c, int pos)
    {
    char *p;
    int i;

    p = malloc(len + 2);
    for (i = 0 ; i < pos ; ++i)
    p = str;
    p[i++] = c;
    for ( ; i < len + 2 ; ++i)
    p = str[i - 1];
    free(str);
    return p;
    }

    char* insert_char_realloc (char *str, int len, char c, int pos)
    {
    int i;

    str = realloc(str, len + 2);
    for (i = len + 1 ; i > pos ; --i)
    str = str[i - 1];
    str = c;
    return str;
    }
    tano, Aug 9, 2004
    #1
    1. Advertising

  2. On 2004-08-09, tano <> wrote:
    >
    > I have to insert a char in the middle of a string, I have written
    > two functions but I don't know what is the better?
    >


    Both have their pros and cons, as you said yourself. I would
    personally choose the "malloc" version, because it has a more
    "constant" behavior. In any case it all depends on how often you have
    to perform the operation: If not very often then you functions are
    ok. If, though, you have to do it every once in a while (e.g. you 're
    writing an editor), then you should probably choose a whole different
    *representation* for your strings: Instead of having them be arrays of
    chars you could implement them as lists of characters, or as lists of
    arrays (substrings) that are broken and re-combined, and so on. The
    possibilities are endless.

    /npat

    P.S. The system calls you mentioned cannot help you with this (they
    are irrelevant).
    Nick Patavalis, Aug 9, 2004
    #2
    1. Advertising

  3. tano <> spoke thus:

    > char* insert_char_malloc (char *str, int len, char c, int pos)
    > {
    > char *p;
    > int i;


    > p = malloc(len + 2);


    You should check whether malloc() succeeded, if you were not aware of
    that.

    > for (i = 0 ; i < pos ; ++i)
    > p = str;
    > p[i++] = c;
    > for ( ; i < len + 2 ; ++i)
    > p = str[i - 1];
    > free(str);


    The caller has to be aware that str was freed, which IMHO is an
    unnecessary burden.

    > return p;
    > }


    I suggest (untested):

    char *insert_char_realloc( char **str, int len, char c, int pos )
    {
    char *tmp=realloc( *str, len+2 );
    if( !tmp ) { /* failed */
    return NULL;
    }
    sprintf( tmp, "%.*s%c%s", pos, *str, c, *str+pos );
    *str=tmp;
    return *str;
    }

    I don't remember whether realloc( ptr, n ) == ptr; the double pointer
    may be unnecessary. Of course, pos must be less than len or things
    will break.

    --
    Christopher Benson-Manica | I *should* know what I'm talking about - if I
    ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
    Christopher Benson-Manica, Aug 9, 2004
    #3
  4. tano

    Malcolm Guest

    "tano" <> wrote
    >
    > I have to insert a char in the middle of a string, I have written two

    functions
    > but I don't know what is the better?
    >
    > /* Code: the len is in memory, incremented after every insertion, so it
    > doesn't need to compute it using strlen() */
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    >
    > char* insert_char_malloc (char *str, int len, char c, int pos)
    > {
    > char *p;
    > int i;
    >
    > p = malloc(len + 2);
    >

    You need to check p is non-null.
    >
    > for (i = 0 ; i < pos ; ++i)
    > p = str;
    > p[i++] = c;
    > for ( ; i < len + 2 ; ++i)
    > p = str[i - 1];
    > free(str);
    > return p;
    > }
    >

    Consider carefully whether you want to free str, and whether you want to
    insist that the length is passed in. Both these things may give you a speed
    advantage, but make the function less generally useful.
    >
    >
    > char* insert_char_realloc (char *str, int len, char c, int pos)
    > {
    > int i;
    >
    > str = realloc(str, len + 2);
    >

    You need to assign to a temporary and test str for null.
    >
    > for (i = len + 1 ; i > pos ; --i)
    > str = str[i - 1];
    > str = c;
    > return str;
    > }
    >

    The realloc() version may well be faster, since realloc() doesn't always
    perform a copy. Howver it suffers from the same problem that the interface
    isn't clean - you must pass a pointer allocated with malloc and then
    remember that it is invalidated by the call.
    Malcolm, Aug 9, 2004
    #4
  5. tano

    SM Ryan Guest

    # all the string with the new char in the middle every time, with realloc() the
    # part of the string before the position where the char has to be inserted is not
    # changed if realloc returns the same pointer is passed, but if not the
    # string is copied at all the first time, and then the part after the char has to

    realloc has a potential performance problem that you may not be aware of.
    realloc can copy the string everytime; if the string is length n, that
    is O(n) time. If you insert every character starting from an empty
    string, that is n inserts or a total time of O(n^2).

    If instead of copying each time 1, 2, 3, 4, 5, 6, 7, 8, ... , n = n(n+1)/2,
    or O(n^2), you double the length only when necessary, 1, 2, 4, 4, 8, 8, 8,
    8, ... , 2n, the number of copies is 1 + 2 + 4 + 8 +...
    approx= 2^(log n) - 1, or O(n).

    Bad news is that with C strings, you cannot deduce the allocated block
    size from string length, and it is not portably available from the block
    address, so you need to pass the allocated block size in and out.

    If you do n mallocs of size 1, 2, 3, ..., n, you get this same quadratic
    worst case performance.

    --
    SM Ryan http://www.rawbw.com/~wyrmwif/
    I think that's kinda of personal; I don't think I should answer that.
    SM Ryan, Aug 9, 2004
    #5
  6. tano

    Stan Milam Guest

    tano wrote:
    > Hello,
    > I have to insert a char in the middle of a string, I have written two functions
    > but I don't know what is the better? The problem is: if I use malloc() I copy
    > all the string with the new char in the middle every time, with realloc() the
    > part of the string before the position where the char has to be inserted is not
    > changed if realloc returns the same pointer is passed, but if not the
    > string is copied at all the first time, and then the part after the char has to
    > be shifted to right.. Perhaps it could be possible to make another function
    > using the system call of the os (brk, sbrk)?
    > Can anybody give me suggestions or clarify my ideas?
    > Thanks,


    This is some code I have saved away. It inserts one string of
    characters into another, so I can be used to insert a single character too.

    /**FILE****************************************************************/
    /* File Id: STRINS.C. */
    /* Author: William Smith. */
    /* Date Written: 23 Dec. 92. */
    /* */
    /* This function inserts a string (ins) into a target string */
    /* (str) at a specified position (pos) in the target string. */
    /* The position for the insert must fall within the boundries */
    /* of the target string. */
    /* */
    /* The inspiration of this code came from an article that ap- */
    /* peared in the Jan. 93 issue of "The C Users Journal" called */
    /* an "Essential String Library". I wrote this code without the */
    /* benefit of the code listing in the magazine. */
    /* */
    /* Arguments: */
    /* char *str - The address of the string to insert into. */
    /* char *pos - Position in the string where the insert will */
    /* be done. */
    /* char *ins - The address of a string to insert into the */
    /* target string. */
    /* */
    /* Returns: The address of the target string after the */
    /* insert. */
    /* */
    /* NOTE: It is the programmer's responsiblity to ensure there */
    /* is enough space in the target string to insert. */
    /* */
    /****************************************************************FILE**/

    #include <stddef.h>
    #include <string.h>

    char *str_insert(char *str, char *pos, char *ins) {

    size_t inslen, poslen, lenstr;

    lenstr = strlen(str); /* Get lengths */
    inslen = strlen(ins);
    if (inslen && pos >= str && pos <= &str[lenstr]) { /* Minimum edits */
    poslen = strlen(pos); /* Adjusted
    length */
    memmove(pos + inslen, pos, poslen); /* Make room in
    str */
    memmove(pos, ins, inslen); /* Now copy in
    ins */
    }
    return str; /* Return entire
    str */
    }

    --
    Regards,
    Stan Milam.
    -------------------------------------------------------
    Spiritual people inspire me. Religeous people scare me.
    -------------------------------------------------------
    Stan Milam, Aug 10, 2004
    #6
  7. tano

    Chris Torek Guest

    Since no one else has pointed this out yet, I will:

    In article <news:cf86f5$bav$>
    Christopher Benson-Manica <> wrote:
    >char *insert_char_realloc( char **str, int len, char c, int pos )
    >{
    > char *tmp=realloc( *str, len+2 );
    > if( !tmp ) { /* failed */
    > return NULL;
    > }
    > sprintf( tmp, "%.*s%c%s", pos, *str, c, *str+pos );
    > *str=tmp;
    > return *str;
    >}
    >
    >I don't remember whether realloc( ptr, n ) == ptr; the double pointer
    >may be unnecessary. Of course, pos must be less than len or things
    >will break.


    There are two problems here: (A) realloc() may move the data, and
    in the process invalidate the old data, so that the call to sprintf()
    passes the wrong values. This can be fixed, and in some cases
    realloc() does not actually move the data, but then: (B) The
    behavior of sprintf() is undefined if the output region (tmp)
    overlaps the input (*str, or after fixing the bug, tmp again).

    The memmove()-and-insert solution is probably the best to the
    problem as stated, but in general, inserting one character at a
    time into a potentially-long string is not a great strategy.
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
    Chris Torek, Aug 10, 2004
    #7
  8. Chris Torek <> spoke thus:

    > There are two problems here: (A) realloc() may move the data, and
    > in the process invalidate the old data, so that the call to sprintf()
    > passes the wrong values. This can be fixed, and in some cases
    > realloc() does not actually move the data, but then: (B) The
    > behavior of sprintf() is undefined if the output region (tmp)
    > overlaps the input (*str, or after fixing the bug, tmp again).


    I wasn't sure I remembered A, but it figures. B, however, is an
    embarassing gaffe on my part, and I'm grateful that you didn't let me
    get away with it :)

    --
    Christopher Benson-Manica | I *should* know what I'm talking about - if I
    ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
    Christopher Benson-Manica, Aug 11, 2004
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sean Bartholomew

    insert a char in a char array

    Sean Bartholomew, Nov 16, 2003, in forum: C++
    Replies:
    6
    Views:
    443
    Alex Lyman
    Nov 16, 2003
  2. lovecreatesbeauty
    Replies:
    1
    Views:
    1,015
    Ian Collins
    May 9, 2006
  3. Mr. Ken
    Replies:
    1
    Views:
    285
    Kai-Uwe Bux
    Jun 2, 2006
  4. Rick Csucsai

    how to insert text into middle of textarea

    Rick Csucsai, Jun 21, 2005, in forum: ASP .Net Web Controls
    Replies:
    1
    Views:
    261
    Harolds
    Jun 24, 2005
  5. michael
    Replies:
    1
    Views:
    114
    Jonas Raoni
    Jan 5, 2006
Loading...

Share This Page