small string challenge

hi /prog/

I need to make a function that takes two strings, and removes all characters from the first string that are in the second string; we get marked on how efficient our code is. This is what I got so far, it's pretty shit and apparently theres a much better way to do it.


#include <iostream>
#include <string.h>

void rmFromString(std::string & toBeProcessed, const std::string & toBeIgnored)
{
        size_t found;
      std::string newString;

      found = toBeProcessed.find_first_not_of(toBeIgnored);

      while (found != std::string::npos)
      {
            newString += toBeProcessed[found];
            found = toBeProcessed.find_first_not_of(toBeIgnored, found + 1);
      }

    toBeProcessed = newString;

}

int main()
{
    std::string toBeProcessed = "she sells sea shells on the sea shore",
        toBeIgnored = "se";

    rmFromString(toBeProcessed, toBeIgnored);

    std::cout << toBeProcessed << std::endl;
}

anyone want to point me in the right direction?

>>10
Are there any single-bit ASCII extensions still in common use?)
ISO-8859-1 and Windows-1252. C'est utilisé pour écrire le français.

In fixing >>9's bug and removing the first loop, you've introduced another operation inside the loop; one extra add ain't too bad (probably becomes a LEA) but since the first loop. For short strings getting rid of the first loop might be faster, but since this is O(1) and the second loop is O(n) the second loop time will dominate for n >>> 256.

Asm attempt using dord table. Main loop is only 5 instructions.


 xor eax, eax
 mov ecx, 256
 mov edi, table
 inc eax
 mov edx, argv
 push edi
 rep stosd
 pop edi
 push edx
 mov esi, [edx+8]
 cdq
 jmps loop1t
loop1c:
 mov [edi+eax*4], edx
loop1t:
 lodsb
 or al, al
 jnz loop1c
 pop edx
 mov esi, [edx+4]
 mov ebx, pout
 jmps loop2t
loop2
 mov [ebx], al
 add ebx, [edi+eax*4]
loop2t:
 lodsb
 or al, al
 jnz loop2
 mov [ebx], al

I don't know if using byte table would be faster/shorter. There's no addsx but xlatb might be useful in some way...