Hello Vivayan!
Its taken me this long to understand your sophisticated program you gave me using STL (Standard Template Library) iterators, container classes, algorithms, and the works! I’m truly grateful for the time you took to develop this program for me, and it inspired me so much I’ve decided to finally tackle learning some STL and such. I can see you are a master at this! I just bought Bruce Eckel’s “Thinking In C++”, Volume 2, because in it he covers String Classes, STL, templates, and so forth. Anyway, to refresh your memory, here are the original requirements again…
'1) Create a 2000000 character string of dashes or spaces;
'2) Change every 7th dash or space to a "P";
'3) Replace every "P" with a "PU" (hehehe);
'4) Replace every dash or space with an "8";
'5) Put in a carriage return & line feed every 90 characters;
'6) Output last 4000 characters.
…and here is the program you developed for me (I made a few minor changes, i.e., GetTickCount(), printf instead of iostream)…
#include "Windows.h"
#include "stdio.h"
#include <string>
#include <algorithm>
int main()
{
enum { K = 7, N = 2*1024*1024, N1 = N + N/7, BLOCKSZ = 90, M = N1 + 2*N1/BLOCKSZ, TAIL = 4000 } ;
const char* const crnl = "\r\n" ;
typedef std::string::size_type size_type ;
typedef std::string::iterator iterator ;
int tick;
tick=GetTickCount();
// create a string containing N ' '
std::string str( N, ' ' ) ;
// replace every Kth ' ' with a 'P'
for( size_type i = K-1 ; i < N ; i += K ) str[i] = 'P' ;
// replace every 'P' with a 'PU'
// we could do this in quadratic time by:
// for( size_type i = K ; i < N1 ; i += K+1 ) str.insert( str.begin()+i, 'U' ) ;
// however, by using some temporary memory, we can do it in linear time by:
{
std::string temp ;
temp.reserve(N1) ;
iterator i = str.begin() + K ;
const iterator end = str.end() - K ;
for( ; i < end ; i += K )
{
temp.insert( temp.end(), i, i+K ) ;
temp += 'U' ;
}
temp.insert( temp.end(), i, str.end() ) ; // copy the tail fragment
str = temp ; // and finally modify the original str with a single assignment
} // this is presumably what PowerBASIC would have done for: Replace "P" With "PU" In s
// replace every ' ' with an '8'
std::replace_copy( str.begin(), str.end(), str.begin(), ' ', '8' ) ;
std::string dest ;
dest.reserve(M) ;
// copy blocks of BLOCKSZ chars to dest, appending a cr-nl to each copied block
iterator i = str.begin() ;
const iterator last = str.end() - BLOCKSZ ;
for( ; i < last ; i += BLOCKSZ )
{
dest.insert( dest.end(), i, i+BLOCKSZ ) ;
dest += crnl ;
}
dest.insert( dest.end(), i, str.end() ) ; // copy what is left
// using stdout in place of MessageBox()
std::string s;
s=dest.substr(dest.size() - TAIL);
//std::cout << dest.substr( dest.size() - TAIL ) ;
printf("%s\n",s.c_str());
tick=GetTickCount()-tick;
printf("\n\ntick count = %d\n",tick);
getchar();
return 0;
}However, after great study of your code and a good deal of playing with it I have to say it doesn’t do what I at first thought, and the fault isn’t all yours. What its lacking, and perhaps the reason it executes so fast, is that it is not doing a search for each ‘P’ in your std::string str variable, but rather it is relying on the repeating pattern of a ‘P’ every 7th character, and simply adding the ‘U’ as the next or ‘eighth’. So a more precise description of the problem would be this…
'1) Create a 2000000 character string of dashes or spaces;
'2) Change every 7th dash or space to a "P";
'3) SEARCH FOR AND Replace every "P" with a "PU";
'4) Replace every dash or space with an "8";
'5) Put in a carriage return & line feed every 90 characters;
'6) Output last 4000 characters.
Here is part of your algorithm again in slightly altered form where we’re just working with one ninety character line of characters with no set pattern to the Ps in the line (I used dashes instead of blanks so they are easier to see and count) The output shows how it fails…
#include "Windows.h"
#include "stdio.h"
#include <string>
#include <algorithm>
int main()
{
enum {K=7, N=90, N1=N+N/7, BLOCKSZ=90, M=N1+2*N1/BLOCKSZ, TAIL=90};
typedef std::string::size_type size_type ;
typedef std::string::iterator iterator ;
printf("K = %u\n",K);
printf("N = %u\n",N);
printf("N1 = %u\n",N1);
printf("BLOCKSZ = %u\n",BLOCKSZ);
printf("M = %u\n",M);
printf("TAIL = %u\n\n",TAIL);
std::string str("---P------P----------P--P-P--------------------------P--P---------P-----P------------P----");
printf("str.size() = %u\n",str.size());
{
std::string temp ;
temp.reserve(N1) ;
iterator i = str.begin() + K ;
const iterator end = str.end() - K ;
for( ; i < end ; i += K )
{
temp.insert( temp.end(), i, i+K ) ;
temp += 'U' ;
}
temp.insert( temp.end(), i, str.end() ) ; // copy the tail fragment
str = temp ; // and finally modify the original str with a single assignment
} // this is presumably what PowerBASIC would have done for: Replace "P" With "PU" In s
std::replace_copy( str.begin(), str.end(), str.begin(), '-', '8' ); //replace every '-' with an '8'
std::string dest ;
dest.reserve(M) ;
printf("%s\n",str.c_str());
getchar();
return 0;
}
/*
Output:
K = 7
N = 90
N1 = 102
BLOCKSZ = 90
M = 104
TAIL = 90
str.size() = 90
888P888U8888888UP88P8P8U8888888U8888888U8888888U8888P88UP888888U888P888U88P8888U8888888U8P8888
*/Here is a PowerBASIC program with the same input string showing how its Replace statement works, which as I mentioned, first locates the ‘match’ string, then replaces it with the replacement string. I used printf from msvcrt.dll (Microsoft C Runtime) for output (after all, this is a C/C++ forum)…
#Compile Exe
#Dim All
Declare Function printf CDecl Lib "msvcrt.dll" Alias "printf" (szFmtStr As Asciiz, lpVar1 As Any) As Long
Function PBMain() As Long
Local str As String
str="---P------P----------P--P-P--------------------------P--P---------P-----P------------P----" & $CrLf
printf("%s", Byval Strptr(str))
Replace "P" With "PU" In str
printf("%s", Byval Strptr(str))
Replace "-" With "8" In str
printf("%s", Byval Strptr(str))
Waitkey$
PBMain=0
End Function
'Output:
'---P------P----------P--P-P--------------------------P--P---------P-----P------------P----
'---PU------PU----------PU--PU-PU--------------------------PU--PU---------PU-----PU------------PU----
'888PU888888PU8888888888PU88PU8PU88888888888888888888888888PU88PU888888888PU88888PU888888888888PU8888As can be seen, it isn’t relying on any set pattern of the Ps, but rather is searching for and replacing any it finds, managing underlying string buffer memory as it goes. That is also hom my String::Replace() member function works. First I scan through the entire string counting the number of matches of the first parameter of the function; then I allocate a second string taking account of the different length needed (if indeed it is needed, and in this case it is), then I replace characters on the second pass making sure none of the other characters are affected.
I almost feel like a heel for asking, considering the work you’ve already put into this for me, and further considering that the fault of your program was more my poor specifications which allowed you to misinterpret it the way you did, but would it be possible for you to modify your program to do a search for the Ps before replacing them instead? If you can’t find the time I certainly understand. Up until I saw your program and what it did, I was never really interested much in what was in the Standard C++ Library, or in STL for that matter, but you changed my mind on that, and I’m taking a fresh look at it.