By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,419 Members | 1,124 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,419 IT Pros & Developers. It's quick & easy.

Problems concatenating strings

P: n/a
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

Jul 23 '05 #1
Share this Question
Share on Google+
11 Replies


P: n/a
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

Jul 23 '05 #2

P: n/a
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());
}
}

Jul 23 '05 #3

P: n/a
>>#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

Jul 23 '05 #4

P: n/a
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());
}
}

Jul 23 '05 #5

P: n/a
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
kb******@gascad.at
Jul 23 '05 #6

P: n/a
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_o ffset,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_ba ck()<<rb.pop_back();
}

Jul 23 '05 #7

P: n/a
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
kb******@gascad.at
Jul 23 '05 #8

P: n/a
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;
}
}

Jul 23 '05 #9

P: n/a
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
kb******@gascad.at
Jul 23 '05 #10

P: n/a
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;
}

Jul 23 '05 #11

P: n/a
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
kb******@gascad.at
Jul 23 '05 #12

This discussion thread is closed

Replies have been disabled for this discussion.