Problems concatenating strings

Discussion in 'C++' started by stroker_ace@hotmail.com, Apr 8, 2005.

  1. Guest

    Hi,

    I am working on a problem where I need to implement a string buffer
    that I can remove an arbitary length char* from one end and add them to
    the other.

    So far the only way I have thought of to accomplish this task involves
    creating using

    new char[length];

    and the strcopy,strcat functions to repopulate the char array with the
    required amount of data each time I add/remove bytes from the head/tail
    of the string.

    Is there a more efficient method of implementing my required behaviour?

    Many thanks

    Lawrie
    , Apr 8, 2005
    #1
    1. Advertising

  2. BigBrian Guest

    If you're always going to be removing from one end and adding from the
    other, then use std::queue<char>. If you need arbitrary access, use
    std::vector<char>.

    -Brian
    BigBrian, Apr 8, 2005
    #2
    1. Advertising

  3. Try ring buffer.

    #define BUFFER_SIZE 4096
    #define INDEX_MASK (BUFFER_SIZE-1)
    char buffer[BUFFER_SIZE];
    int head_index,tail_index;

    void push_front(char ch) {
    buffer[head_index]=ch;
    head_index=(head_index+1)&INDEX_MASK;
    }

    char pop_back() {
    char ch=buffer[tail_index];
    tail_index=(tail_index+1)&INDEX_MASK;
    }

    void copy_from_front_to_back(int n) {
    while(n-->0) {
    push_front(pop_back());
    }
    }
    Manvel Avetisian, Apr 8, 2005
    #3
  4. BigBrian Guest

    >>#define BUFFER_SIZE 4096

    The original post said nothing about how big the buffer needed to be,
    thus it's best to assume an arbitrary size, which your code does not.
    Since you're using the bitwize & to do the wrap around of your indices,
    your code will break if you change BUFFER_SIZE to anything other than a
    power of 2. It's also going to break if you push_front() more
    characters than BUFFER_SIZE ( which you're code doesn't check for. )
    This is exactly why its better to use the containers in the standard
    library.

    -Brian
    BigBrian, Apr 8, 2005
    #4
  5. But my solution will be much faster and efficent than yours ;)

    #define BUFFER_SIZE 100000
    char buffer[BUFFER_SIZE];
    int head_index,tail_index;

    void push_front(char ch) {
    buffer[head_index]=ch;
    head_index=(head_index+1)%BUFFER_SIZE;



    }


    char pop_back() {
    char ch=buffer[tail_index];
    tail_index=(tail_index+1)%BUFFER_SIZE;


    }


    void copy_from_front_to_back(int n) {
    while(n-->0) {
    push_front(pop_back());
    }
    }
    Manvel Avetisian, Apr 8, 2005
    #5
  6. Manvel Avetisian wrote:
    >
    > But my solution will be much faster and efficent than yours ;)


    Wow. I'm impressed.
    A programm that produces garbage more efficiently then
    any other program.

    Increasing a constant in some source code isn't going
    to help if the program is already running at the customers
    site.

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Apr 8, 2005
    #6
  7. Now compare speed of my ring_buffer with speed of std::queue<char>...

    struct ring_buffer {
    char *buffer;
    int length,head_offset,tail_offset;

    ring_buffer() {
    buffer=(char *) malloc(length=4096);
    if(!buffer) throw "out of memory";
    head_offset=tail_offset=0;
    }

    void resize() {
    int new_length=length*2;
    char *new_buffer=(char *) malloc(new_length);
    if(!new_buffer) throw "out of memory";
    memcpy(new_buffer,buffer,head_offset);
    memcpy(new_buffer+length+tail_offset,buffer+tail_offset,length-tail_offset);
    free(buffer);
    tail_offset+=length;
    }

    void push_front(char ch) {
    buffer[head_offset]=ch;
    head_offset=(head_offset+1)%length;
    if(head_offset==tail_offset) resize();
    }

    char pop_back() {
    char ch=buffer[tail_offset];
    tail_offset=(tail_offset+1)%length;
    if(tail_offset==head_offset) resize();
    return ch;
    }

    void copy_from_front_to_back(int n) {
    while(n--) push_front(pop_back());
    }
    };

    void main() {
    ring_buffer rb;

    rb.push_front('a');
    rb.push_front('b');
    rb.push_front('c');
    rb.push_front('d');

    std::cout<<rb.pop_back()<<rb.pop_back()<<rb.pop_back()<<rb.pop_back();
    }
    Manvel Avetisian, Apr 8, 2005
    #7
  8. Manvel Avetisian wrote:
    >
    > Now compare speed of my ring_buffer with speed of std::queue<char>...
    >


    To see, if the enlargement really works, you should start out
    with a ringbuffer size of eg. 2 in your test program.

    Hint: It doesn't work. It crashes.

    The point is not that it cannot be done your way.
    The point is that with deque you already would have
    a reliable, working solution.


    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Apr 8, 2005
    #8
  9. Now compare speed of my ring_buffer with speed of std::queue<char>...

    struct ring_buffer {
    char *buffer;
    int length,head_offset,tail_offset;

    ring_buffer() {
    buffer=(char *) malloc(length=4096);
    if(!buffer) throw "out of memory";
    head_offset=tail_offset=0;
    }

    void resize() {
    int new_length=length*2;
    char *new_buffer=(char *) malloc(new_length);
    if(!new_buffer) throw "out of memory";

    if(head_offset > tail_offset) {
    memcpy(new_buffer,buffer+tail_offset,head_offset-tail_offset);
    } else {
    memcpy(new_buffer,buffer,head_offset);
    memcpy(new_buffer+new_length-(length-tail_offset),buffer+tail_offset,tail_offset-head_offset);
    tail_offset=new_length-(length-tail_offset);
    }

    free(buffer);
    buffer=new_buffer;
    length=new_length;
    }

    void push_front(char ch) {
    int new_head_offset=(head_offset+1)%length;
    if(new_head_offset==tail_offset ||
    abs(new_head_offset-tail_offset)==length) resize();

    buffer[head_offset]=ch;
    head_offset=(head_offset+1)%length;
    }

    char pop_back() {
    char ch=buffer[tail_offset];
    tail_offset=(tail_offset+1)%length;
    if(tail_offset==head_offset) throw "no data in buffer";
    return ch;
    }

    void copy_from_front_to_back(int n) {
    while(n--) push_front(pop_back());
    }
    };

    void main() {
    try {
    ring_buffer rb;

    for(int i=0; i<100000; i++) rb.push_front('a'+i%10);
    for(int j=0; j<100000; j++) std::cout<<j<<rb.pop_back()<<std::endl;
    } catch(const char *str) {
    std::cerr<<str;
    }
    }
    Manvel Avetisian, Apr 8, 2005
    #9
  10. Manvel Avetisian wrote:
    >
    > Now compare speed of my ring_buffer with speed of std::queue<char>...
    >


    To see, if the enlargement really works, you should start out
    with a ringbuffer size of eg. 2 in your test program.

    Hint: It doesn't work. It crashes.

    The point is not that it cannot be done your way.
    The point is that with deque you already would have
    a reliable, working solution.

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Apr 8, 2005
    #10
  11. And the final (stable?) version of resize() specially for you:

    void resize() {
    int new_length=length*2;
    char *new_buffer=(char *) malloc(new_length);
    if(!new_buffer) throw "out of memory";

    if(head_offset > tail_offset) {
    memcpy(new_buffer,buffer+tail_offset,head_offset-tail_offset);
    tail_offset=0;
    head_offset-=tail_offset;
    } else {
    int n;
    memcpy(new_buffer,buffer+tail_offset,n=length-tail_offset);
    memcpy(new_buffer+n,buffer,head_offset);
    head_offset+=n;
    tail_offset=0;
    }

    free(buffer);
    buffer=new_buffer;
    length=new_length;
    }
    Manvel Avetisian, Apr 8, 2005
    #11
  12. Manvel Avetisian wrote:
    >
    > And the final (stable?) version of resize() specially for you:
    >
    > void resize() {
    > int new_length=length*2;
    > char *new_buffer=(char *) malloc(new_length);
    > if(!new_buffer) throw "out of memory";
    >
    > if(head_offset > tail_offset) {
    > memcpy(new_buffer,buffer+tail_offset,head_offset-tail_offset);
    > tail_offset=0;
    > head_offset-=tail_offset;
    > } else {
    > int n;
    > memcpy(new_buffer,buffer+tail_offset,n=length-tail_offset);
    > memcpy(new_buffer+n,buffer,head_offset);
    > head_offset+=n;
    > tail_offset=0;
    > }
    >
    > free(buffer);
    > buffer=new_buffer;
    > length=new_length;
    > }


    If I replace that in your class, the class still has the same problem:
    I put 5 characters in, I get 4 characters back :)

    So it still (after 2 hours?) is an efficient(*) but buggy solution.

    * nobody knows how efficient it really is. Up to now there is no
    working solution that can be timed against deque :)
    And I definitly will not time it.

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Apr 8, 2005
    #12
    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. Stan Horwitz
    Replies:
    2
    Views:
    2,729
    Stan Horwitz
    Feb 15, 2006
  2. John Henry

    Concatenating strings

    John Henry, Jul 1, 2006, in forum: Python
    Replies:
    1
    Views:
    300
    Steven Bethard
    Jul 1, 2006
  3. John Henry

    Concatenating strings

    John Henry, Jul 1, 2006, in forum: Python
    Replies:
    1
    Views:
    322
    Robert Kern
    Jul 1, 2006
  4. EHC

    concatenating strings

    EHC, Dec 15, 2006, in forum: Python
    Replies:
    3
    Views:
    315
    Caleb Hattingh
    Dec 16, 2006
  5. c

    Help me with Concatenating strings

    c, Sep 24, 2006, in forum: C Programming
    Replies:
    21
    Views:
    596
    Chris Torek
    Oct 15, 2006
Loading...

Share This Page