Question For Vivayan And Feedback On His STL String Program He Did For Me

Question

Frederick2 189 Posting Whiz

13 Years Ago

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----
'888PU888888PU8888888888PU88PU8PU88888888888888888888888888PU88PU888888888PU88888PU888888888888PU8888

As 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.

c++

Edited 13 Years Ago by Frederick2 because: I Posted The Wrong Code!

2 Contributors
2 Replies
166 Views
11 Hours Discussion Span
Latest Post 13 Years Ago Latest Post by Frederick2

All 2 Replies

vijayan121 1,152 Posting Virtuoso

13 Years Ago

but would it be possible for you to modify your program to do a search for the Ps before replacing them instead?

If you had really understood the program, you would have been able to make such a trivial modification yourself.

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,

The reason it executes faster is because an algorithm which took quadratic time was replaced by an algorithm which takes linear time. This was clearly indicated in the comments in the original code. Even if you have to search for the 'P' in the string, the time taken remains linear and would not lead to an order of magnitude change in speed. It also doesn't matter what programming language you write this in; all that is being done is iterating through a sequence of bytes and moving chunks of bytes around in memory. It will take roughly the same time when compiled to native code.

#include <iostream>
#include <string>
#include <algorithm>

int main()
{
    enum { MAXP = 100, BLOCKSZ = 50, TAIL=40 } ;
    const char* const crnl = "\r\n" ;
    typedef std::string::size_type size_type ;
    typedef std::string::iterator iterator ;

    std::string str( "---P------P----------P--P-P--------------------------P--P--"
                     "-------P-----P------------P----P------P-------P-----P------"
                     "--PPP---PP------P------P-P-------P------P----P--P----P-----" ) ;
    {
        std::string temp ;
        temp.reserve( str.size() + MAXP ) ;
        iterator begin = str.begin() ;

        size_type a = 0, b ;  ;
        while( ( b = str.find( 'P', a ) ) != std::string::npos )
        {
           ++b ;
           temp.insert( temp.end(), begin+a, begin+b ) ;
           temp += 'U' ;
           a = b ;
        }

        temp.insert( temp.end(), begin+a, str.end() ) ; // copy the tail fragment
        str = temp ;
    } // 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( str.size() + 2 * str.size()/BLOCKSZ ) ;
    // 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::cout << str << "\ntail: " << dest.substr( dest.size() - TAIL ) << '\n' ;
}

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Frederick2 189 Posting Whiz · Answer 1 · 2011-01-18T01:00:21+00:00

That did it Vijayan! You are a master! That code beats everything I've tried so far! I won't be pestering you again. I guess I need to learn STL.

Question For Vivayan And Feedback On His STL String Program He Did For Me

Recommended Answers Collapse Answers

All 2 Replies

Recommended Answers