c++stringvector

Segfault while removing characters from a vector


I want to remove the current character and the previous character from a vector if it matches a specified character. The code works for alphabetic characters like a, b, c. But, if I want to remove multiple characters like *, the code gives a segmentation fault.

Any suggestions?

#include<iostream>
#include <vector>
#include<string>
using namespace std;
    
int main(){
    
    vector<char> v;
    vector<char>::iterator it;
    
    string s= "abcdef*gh*i";
    
    
    for(int i=0; i<s.size(); i++){
        v.push_back(s[i]);
        cout << v[i] <<" ";
    }
    cout <<"\n";
    
    for (it = v.begin(); it!= v.end(); it++)
    {
        if(*it == '*'){
        v.erase(it);
        v.erase(it-1);
        }
    }
    for(int i=0; i< v.size(); i++)
        cout << v[i]<<" ";
    
    return 0;
}

Solution

  • I realize you asked specifically about vectors, but I decided to use strings because that's the natural thing to do for sequences of characters.

    The first thing to do is to figure out how you'll test your solution. I came up with this:

    #include <cassert>
    #include <string>
    #include <string_view>
    
    void test(std::string_view original, std::string_view expected) {
        auto x = std::string(original.data(), original.size());
        treatStarAsBackspace(x);
        assert(x == expected);
    }
    
    int main() {
        test("", "");
        test("abc", "abc");
        test("ab*c", "ac");
        test("*", "");
        test("ab*cd*ef*", "ace");
        test("*abc", "abc");
        test("abc*",  "ab");
        test("abc***", "");
        return 0;
    }
    

    There are two things to note about the problem:

    1. chars are cheap to copy. They're small and don't have constructors or destructors. So there's not much harm if we copy a few more than absolutely necessary. This makes for a simpler algorithm.

    2. At each step in the process, the resulting string will never be longer than the original. Thus it's possible to process the characters in place. You don't have to do it that way, but it may be convenient.

    With that in mind, I came up with this:

    // Modifies the string in place as though each asterisk is an instruction to
    // delete the previous character.
    void treatStarAsBackspace(std::string &s) {
        auto target = s.begin();
        for (auto source = s.cbegin(); source != s.cend(); ++source) {
            if (*source == '*') {
                if (target != s.begin()) --target;
            } else {
                *target++ = *source;
            }
        }
        // The desired result is now the range `s.begin()` up to
        // `target`, so we have to erase anything beyond that.
        s.erase(target, s.end());
    }