Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Problems concatenating strings

Reply
Thread Tools

Problems concatenating strings

 
 
stroker_ace@hotmail.com
Guest
Posts: n/a
 
      04-08-2005
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

 
Reply With Quote
 
 
 
 
BigBrian
Guest
Posts: n/a
 
      04-08-2005
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

 
Reply With Quote
 
 
 
 
Manvel Avetisian
Guest
Posts: n/a
 
      04-08-2005
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());
}
}

 
Reply With Quote
 
BigBrian
Guest
Posts: n/a
 
      04-08-2005
>>#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

 
Reply With Quote
 
Manvel Avetisian
Guest
Posts: n/a
 
      04-08-2005
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());
}
}

 
Reply With Quote
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      04-08-2005
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
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
Manvel Avetisian
Guest
Posts: n/a
 
      04-08-2005
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();
}

 
Reply With Quote
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      04-08-2005
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
(E-Mail Removed)
 
Reply With Quote
 
Manvel Avetisian
Guest
Posts: n/a
 
      04-08-2005
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;
}
}

 
Reply With Quote
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      04-08-2005
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
(E-Mail Removed)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
concatenating strings EHC Python 3 12-16-2006 12:07 AM
Help me with Concatenating strings c C Programming 21 10-15-2006 07:28 AM
Concatenating strings John Henry Python 1 07-01-2006 03:38 AM
Concatenating strings John Henry Python 1 07-01-2006 03:36 AM
adding strings, not concatenating them Stan Horwitz Perl 2 02-15-2006 08:38 PM



Advertisments