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

When you erase a character from your string, what should happen to the indices that were mapped to the old string? Is anything even achieved by erasing these characters? — Drew Dormann, Jul 18 '23 at 20:30
once you erased 1 character from a string with N characters it has only N-1 characters. And indices are shifted accordingly — 463035818_is_not_an_ai, Jul 18 '23 at 20:30
Try marking the "erased" elements with a parallel bool array rather than actually removing them. You can't erase the third character of a string with only two characters. — lastchance, Jul 18 '23 at 20:32
"....so I should remove 1st character in 'abcd' which refers to 'a',..." your code is not doing that. In the second iteration you are removing a character from `abc` not from `abcd` — 463035818_is_not_an_ai, Jul 18 '23 at 20:35
Try to instead build a new string with the desired elements ommited (this way is in general must faster and also easier to think about). Start by converting the indices to a set of integers. For every input character, copy it to the output only if its index is not found in the set of indices to remove. — user2407038, Jul 18 '23 at 20:40
@463035818_is_not_an_ai Of course `T.erase(T.begin() + arr[i]-1);` invalidates `T`s iterators. — πάντα ῥεῖ, Jul 18 '23 at 20:45
@πάνταῥεῖ yes I already realized that the comment was poorly phrased. Iterators are invalidated. Nevertheless thats not the issue in the code — 463035818_is_not_an_ai, Jul 18 '23 at 20:46

score 3 · Answer 1 · answered Jul 18 '23 at 20:41

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.

score 1 · Answer 2 · answered Jul 18 '23 at 21:15

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

lastchance · Answer 3 · 2023-07-18T21:44:35.380

0

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';
}

edited Jul 18 '23 at 21:44

answered Jul 18 '23 at 21:34

lastchance

1,436
1
3
12

`arr[i]-1` trasnforms the 1 based index to a 0-based index. The question is just where you do that. I'd recommend to do it once when reading the input, rather than every time the index is used – 463035818_is_not_an_ai Jul 19 '23 at 06:56
@463035818_is_not_an_ai , transformation between 1-based and 0-based indices is one of the most error-prone coding activities I know (and I switch between Fortran and C++ quite a lot). It's not a thing that I like doing late at night, when I'm tired. Probably the best error-avoidance tactic is a very explicit line of code ```index=position-1``` or similar. Perhaps l should have renamed ```arr``` as ```pos``` to signify this. I left it as 1-based indexing simply because that's what the OP used. – lastchance Jul 19 '23 at 08:45
my comment merely is a nitpick concerning "The following has left it with 1-based indices". You do not "leave it with 1 based indices" you apply the transformation. You only leave it to as late as possible. – 463035818_is_not_an_ai Jul 19 '23 at 08:47
Ah, fair comment. I meant "the INPUT assumes 1-based indices". Yes, I'm obliged to transform to the 0-based system (if I'm doing it in C++). – lastchance Jul 19 '23 at 08:53

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

3 Answers3