How to use original index of a string to erase single character?

Question

Assume that I have a string 'abcd', and a vector [4,1,3,2] to index the string. For example, first element of vector is 4, so I should remove 4th character in 'abcd' which refers to 'd'. Then the second element of vector is 1, so I should remove 1st character in 'abcd' which refers to 'a', and so on. I want to record the operated string every time I remove one character. And here is my code:

# include <iostream>
# include <vector>

using namespace std;

int main()
{
    int m;
    cin >> m;
    string T;
    cin >> T;
    cout << T << endl;
    vector<int> arr(m);
    for(auto &x : arr) cin >> x;
    // Remove character from string at given index position
    for (int i = 0; i < m; i++){
        T.erase(T.begin() + arr[i]-1);
        cout << T << endl;
    }
    return 0;
}

However, I had faced some problem in the output, how could I fix it?

4
abcd
abcd
4 1 3 2
abc
bc
Segmentation fault

Answer 1

You confuse the indicies of the characters in the original string with the indices of same characters in the updated string.

Consider the string ab and erasing characters at position 0 and 1 (indices are 0 based). Then you first remove the first character and have the new string b. Now you cannot remove the character at index 1 anymore, because there is none. The character b that was at position 1 in the original string is now at index 0.

As mentioned in a comment, the most simple is to keep the original string intact so you can use its indices and keep track of "removed" indices in a seperate vector:

std::vector<bool> removed_chars(T.size());
for (size_t i = 0; i < arr.size(); i++){  
     removed_chars[ arr[i] ] = true; // "remove" the next char
     for (size_t j = 0; j < T.size(); j++) {   
           if (! removed_chars[ j ]) std::cout << T[j]; // print the char if it is not removed yet
           std::cout << "\n";
     }
}

Note that I assumed the input uses 0-based indices. If the input uses 1-based indices, I would correct for that as early as possible while taking input.

Answer 2

For starters indices in C++ start from 0. So it will be much better if you will follow this convention. That is the vector with indices should contain the following sequence { 3, 0, 2, 1 } instead of { 4, 1, 3, 2 }.

A straightforward approach can look the following way. To correctly determine an index in the string you need to check how many elements in the string were already erased with indices that less than the currect index.

Here is a demonstration program.

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>

int main()
{
    std::vector<size_t> v = { 3, 0, 2, 1 };
    std::string s( "abcd" );

    for (size_t i = 0; i < v.size(); i++)
    {
        auto n = std::count_if( std::begin( v ), std::next( std::begin( v ), i ),
            [=]( const auto &item ) { return item < v[i]; } );

        s.erase( v[i] - n, 1 );
        std::cout << s << '\n';
    }
}

The program output is

abc
bc
b

Answer 3

You can just about do it without a parallel array if you mark the characters of the string at the relevant indices. (For example, as the null character.)

The following has left it with 1-based indices (I'm a Fortran programmer!)

# include <iostream>
# include <vector>
# include <string>
# include <algorithm>
# include <iterator>
using namespace std;

int main()
{
    int m;
    string T;
    cout << "Enter m: ";   cin >> m;
    cout << "Enter string: ";   cin >> T;
    vector<int> arr(m);
    cout << "Enter " << m << " positions [1-indexed]: ";
    for (auto &x : arr ) cin >> x;
    // MARK character in string at given index position (as the null character, say)
    for (int i = 0; i < m; i++)
    {
       T[arr[i]-1] = 0;
       copy_if( T.begin(), T.end(), ostream_iterator<char>( cout ), [](char &c){ return c; } );
       cout << '\n';
    }
}

Run:

Enter m: 4
Enter string: abcd
Enter 4 positions [1-indexed]: 4 1 3 2
abc
bc
b

Actually, I've just discovered that if you mark it with char(7) then you can get away with just outputting the string rather than using copy_if. No idea if that is standard behaviour, though.

for (int i = 0; i < m; i++)
{
   T[arr[i]-1] = 7;
   cout << T << '\n';
}