Delete matching characters

Question

Having some trouble with some code. The rule is that if two characters must match, the duplicated letter must be deleted. So for example "Usually" would be changed to "Usualy".

The code does work however it doesn't do what was mentioned above.

I will post the code below and comment put a comment above the problem spot.

#include <iostream>
#include <list>
#include <ctype.h>
#include <fstream>

using namespace std;

void printList(const list<char> &myList);
void fillList(list<char> &myList);
void change(list <char> &myList);

void printList(const list<char> &myList)
{
    list<char>::const_iterator itr;
    for (itr = myList.begin(); itr != myList.end(); itr++ )
    {
        cout <<*itr;
    }
    cout << '\n' << endl;
}

void fillList(list<char> &myList)
{
    ifstream file("test.txt");
    string print;
    while(file >> print)
    {
        for (int i = 0; i<=print.length(); i++)
        {
            myList.push_back(print[i]);
        }
        myList.push_back(' ');
    }
}

void change(list <char> &myList)
{
    list<char>::iterator itr;

    //rules are as follows

    //change w with v
    for (itr = myList.begin(); itr != myList.end(); itr++ )
    {
        if (*itr == 'w')
        {
            *itr = 'v';
        }
    }

    // double letter become single letter here
    //PROBLEM IS HERE!
    for (itr = myList.begin(); itr != myList.end(); itr++ )
    {
        std::list<char>::iterator itr2 = itr;
        if(*(++itr2) == *itr)
        {
            myList.remove(*itr);
        }
    }
}

int main ()
{
    list<char> myList;
    ifstream file("test.txt");
    const string print;
    fillList(myList);
    printList(myList);
    change(myList);
    printList(myList);

    return 0;
}

What trouble? What problem? Any particular error? Is this: http://stackoverflow.com/questions/596162/can-you-remove-elements-from-a-stdlist-while-iterating-through-it relevant? — TessellatingHeckler, May 04 '16 at 02:36

score -1 · Answer 1 · answered May 04 '16 at 02:39

-1

The problem is you are modifying a list while traversing it using the same iterator:

for (itr = myList.begin(); itr != myList.end(); itr++ )
{
    std::list<char>::iterator itr2 = itr;
    if(*(++itr2) == *itr)
    {
        myList.remove(*itr);
    }
}

You want to do something more like this:

for (itr = myList.begin(); itr != myList.end(); )
{
    std::list<char>::iterator before = itr++;
    if(*itr != myList.end() && *before == *itr)
    {
        myList.erase(before);
    }
}

answered May 04 '16 at 02:39

John Zwinck

239,568
38
324
436

your suggestion doesn't compile. I am getting an error, saying no match for operator= – TheByteMonster May 04 '16 at 02:42
`list::erase()` returns an iterator to the next item following the one being removed. – Remy Lebeau May 04 '16 at 02:42
@TheByteMonster: don't deference the `iterator` when comparing it to `end()`. – Remy Lebeau May 04 '16 at 02:42

score -1 · Answer 2 · answered May 04 '16 at 02:58

The second loop in change() is modifying the list while iterating through it, but you are not updating your loop iterator to account for that. list::erase() returns an iterator to the next item in the list after the specified item is removed.

You are also not taking into account that ++itr2 could produce the end() iterator, which is not safe to dereference.

Try this instead:

#include <algorithm>

void change(std::list<char> &myList)
{
    //rules are as follows

    //change w with v
    std::replace(myList.begin(), myList.begin(), 'w', 'v');

    // double letter become single letter here
    list<char>::iterator itr = myList.begin();
    while (itr != myList.end())
    {
        std::list<char>::iterator itr2 = itr++;
        if ((itr != myList.end()) && (*itr2 == *itr))
        {
            myList.erase(itr2);
            // or: itr = myList.erase(itr);
        }
    }
}

A simpler solution is to use std::unique() instead (if you don't mind allowing 3+ duplicates to be removed at a time):

Removes all consecutive duplicate elements from the range [first, last) and returns a past-the-end iterator for the new logical end of the range.

#include <algorithm>

void change(std::list<char> &myList)
{
    //rules are as follows

    //change w with v
    std::replace(myList.begin(), myList.begin(), 'w', 'v');

    // multiple letter become single letter here
    std::list<char>::iterator itr = std::unique(myList.begin(), myList.end());
    myList.erase(itr, myList.end()); 
}

Delete matching characters

2 Answers2