to insert() or to make new

Question

I'm writing some code that has a lot of substitution.

There's a list<char> productions which has a bunch of characters in it.

I repeatedly need to replace every character in productions with the rules corresponding to it in a map<char,char*> productionRules. So every character in productions might be replaced by zero or more characters as indicated by productionRules.

I'm thinking there's 2 ways to do it:

1. iterate over productions and .insert() all replacement characters in productions before .erase()'ing each element

2. Create a NEW list<char> newProductions then reassign productions to refer to newProductions.

Which is better? To .insert() and .erase() a whole lot or to just create a new one?

Answer 1

It depends on how likely it is that each character would be replaced by zero or >2 characters. If it's unlikely that any such replacement will take place, then you'll probably win by iterating over it. But if it's likely that you will often perform that operation you should almost certainly just create a new list.

You can have your algorithm try to iterate over the list, and if you find you have to do a zero or >2 replacement, then create a new list. Whether or not this wins or not again depends on how likely you are to run into a case where you have to do such a replacement.

Answer 2

Create one is always appending to the end which is more efficient and less complicated to implement.

Answer 3

I don't see how making a copy could possibly be faster. Just handle each case of the size of the replacement.

list<char>::iterator q;

for (list<char>::iterator p = productions.begin(); p != productions.end(); p = q)
{
    // save the next position since we might be deleting p
    q = p;
    ++q;

    char* p_rule = productionRules[*p];

    // if points to empty string, nuke
    if (!*p_rule)
        productions.erase(p);
    else
    {
        // if single char, replace
        *p = *p_rule;

        // insert all other chars
        ++p_rule;
        while (*p_rule)
        {
            // check me on this
            // I want to insert before q
            productions.insert(q, *p_rule);
            ++p_rule;
        }
    }
}