Replace each item in list with new list of items in one pass

Alec Jacobson

September 02, 2013

weblog/

Here's a little proof of concept that you can iterate over an std::list and replace each item with a list of items in just one pass. In this self-compiling example I have a list of words and I replace each word by a list of its characters:

#!/bin/bash
/*/../bin/ls > /dev/null
# BEGIN BASH SCRIPT
printf "//" | cat - $0 | g++ -g -o .main -x c++ - && ./.main $@
rm -f .main
# END BASH SCRIPT
exit
*/

#include <list>
#include <string>
#include <iostream>

void print(const std::list<std::string > L)
{
  using namespace std;
  cout<<"{ ";
  for(list<string>::const_iterator cit = L.begin();cit != L.end();cit++)
  {
    cout<<*cit<<" ";
  }
  cout<<"}";
}

int main(int argc, char * argv[])
{
  using namespace std;

  // Initialize list of strings
  list<string> L;
  L.push_back("thing");
  L.push_back("ball");
  L.push_back("kitty");
  L.push_back("gaol");

  // Loop over list (notice for loop does not increment lit)
  for(list<string>::iterator lit = L.begin();lit != L.end();)
  {
    print(L);
    cout<<endl;
    // Build list of replacements
    list<string> replacement;
    for(int c = 0;c<lit->length();c++)
    {
      replacement.push_back(string()+lit->at(c));
    }
    // Insert list of replacements before this item
    L.insert(lit,replacement.begin(),replacement.end());
    // Delete this item and "increment" iterator
    lit = L.erase(lit);
  }
  print(L);
  cout<<endl;
}

This outputs the current list as it iterates through:

{ thing ball kitty gaol }
{ t h i n g ball kitty gaol }
{ t h i n g b a l l kitty gaol }
{ t h i n g b a l l k i t t y gaol }
{ t h i n g b a l l k i t t y g a o l }