Segfault при удалении символов из вектора

Если вы хотите удалить элементы из вектора или массива, рекомендуется выполнять итерацию с конца цикла. Этот подход помогает поддерживать целостность индексов всех элементов вашего вектора, массива и т. д.

Например:

При повторении с начала цикла:

vector container = [a,b,c,d]

Если вы сотрите, скажем, «b»:

Ваш «c» теперь индексируется как второй элемент, и, таким образом, целостность нарушена. Здесь он обновляется, а затем повторяется.

Однако при повторении с конца цикла:

vector container = [a,b,c,d]

Если вы снова удалите букву «b»:

Ваш «c» остается индексированным как второй элемент, сохраняя целостность. Это связано с тем, что сначала выполняется итерация «c», а затем обновляется. Этот метод имеет существенное значение!

Вот ваш исправленный программный код:

#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 << s[i] <<" ";
}
cout <<"\n";



for (it = v.end(); it >= v.begin();  it--)
{
    if (*it == 'i'){
    v.erase(it);
    v.erase(it-1);
    }
}
for(int i=0; i< v.size(); i++)
    cout << v[i]<<" ";

return 0;
}

Я понимаю, что вы спрашивали конкретно о векторах, но я решил использовать строки, потому что это естественно для последовательностей символов.

Первое, что нужно сделать, — это выяснить, как вы будете тестировать свое решение. Я придумал это:

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

По поводу проблемы следует отметить две вещи:

1. char копировать дешево. Они маленькие и не имеют конструкторов и деструкторов. Так что не будет большого вреда, если мы скопируем несколько больше, чем это абсолютно необходимо. Это упрощает алгоритм.

2. На каждом этапе процесса полученная строка никогда не будет длиннее исходной. Таким образом можно обрабатывать символы на месте. Вам не обязательно делать это таким образом, но это может быть удобно.

Имея это в виду, я придумал следующее:

// 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());
}

Особенно в таком случае, когда вы все равно копируете данные, @some Programmer Dude прав: самый простой способ справиться с этим — почти наверняка фильтровать данные во время их копирования.

    std::string s= "abcdef*gh*i";
    std::string v;

    std::cout << s << "\n";

    for (std::size_t source = 0; source < s.size()-1; source++) {
        if (s[source+1] != '*')
            v.push_back(s[source]);
        else
            ++source;
    }

    if (s.back() != '*')
        v.push_back(s.back());

    std::cout << v << "\n";

Результат:

abcdef*gh*i
abcdegi

  string s ;
  cin >> s ;
  stack<char> temp ;
  for(auto it : s){
    if (it=='*' and temp.size() > 0){
        temp.pop();
    }
    else{
        temp.push(it);
    }
  }
  string ans = "";
  while(temp.size()){
    char ch = temp.top();
    ans+=ch;
    temp.pop();
  }
  reverse(ans.begin(),ans.end());
  cout << ans << endl;  

Чтение/запись пары

Возвращаясь к этому, чтобы предложить решение, которого не было представлено. Для любой индексированной последовательности (также известной как упорядоченная последовательность, не обязательно смежная), где вы знаете, что каждая модификация уменьшит длину последовательности (путем, например, простого удаления элементов), тогда все, что вам нужно, это пара указателей для чтения/записи. (или итераторы).

То есть:

• итератор чтения для сканирования вперед
• итератор записи для записи изменений

Пространство прогнозирования

Поскольку ваша модификация требует одного просмотра вперед, то для промежуточного хранения полезен один буфер для чтения, но не записи (что делает это добавлением пространства O (1). Опять же, поскольку вы имеете дело со сжатием, вам не обязательно хранить его как отдельный буфер, это может быть просто еще один итератор в последовательности! (Однако если вы это сделаете, обязательно помните о возможности перекрытия!) Для одного символа вполне подойдет отдельный прочитанный, но еще не записанный символ.

Проблемы должны быть полными и конкретными.

Ваше описание проблемы оставляет неясным, что означают ведущие и несколько последовательных звезд. Далее предполагается, что:

• любое количество звезд в последовательности эквивалентно одной звезде
  (вместо более сложной возможности «abCD**efg» --> «abefg»
  или даже простой возможности «звезды могут есть звезды») и
• любые ведущие звезды просто исчезают.

Фильтр чтения/записи

// The interface here is the long-time Standard C++ kind of way to access an
// ordered sequence: provide iterators to the beginning (inclusive) and to
// the end (exclusive).
//
// It also uses the long-standing C++ Standard Library filter-modify design
// where it returns the NEW end of the sequence, but does not ERASE any elements;
// It only moves things around.

template <typename Iterator>
Iterator remove_x_star( Iterator begin, Iterator end )
{
    // Empty sequences get no love
    if (begin == end) return end;

    auto read  = begin;
    auto write = begin;

    // All leading stars are to be eliminated.
    while (*read == '*')
        if (++read == end) // If we hit the end, then we're done.
            return write;  // Return the new end.

    // Initialize our one-character buffer
    // (Observe that c cannot be a star!)
    auto c = *read++;

    // While there are unprocessed characters...
    while (read != end)
    {
        // If we find a star, we want to move to the next possible
        // sequence, resetting our one-character buffer as appropriate
        //   ...x**...  -->  ...x**...
        //       r                 cr
        if (*read == '*')
        {
            // (This should look familiar)
            while (*read == '*')
                if (++read == end)
                    return write;
            // Restock our one-character buffer and update our read
            c = *read++;
        }

        // Otherwise, there is no star and we should write our
        // one-character buffer to its final destination, restock the
        // buffer with the next available character, and update our
        // read and write iterators.
        //   ....cx.  -->  c...cx.
        //   w   cr         w   cr
        else
        {
            *write++ = c;
            c = *read++;
        }
    }

    // Don't forget that one-character waiting to be copied
    *write++ = c;

    // The end of the written (copied) characters == end of the new sequence
    return write;
}

Я знаю, что это выглядит длинно, но если вы избавитесь от всех комментариев, вы поймете, насколько прост на самом деле код. Опять же, идея такова: просматривайте вперед, отслеживая потенциальных персонажей для написания, и пишите по мере необходимости.

Вспомогательные функции для победы

Теперь мы можем обернуть желаемую функциональность в небольшую вспомогательную функцию, которая принимает любой контейнер и применяет описанный выше алгоритм И фактически изменяет размер контейнера с помощью метода Container::erase(it, end).

template <typename Container>
void delete_x_stars( Container & xs )
{
    xs.erase(
        remove_x_star( xs.begin(), xs.end() ), // new end
        xs.end() );  // old end
}

Основная программа

Наконец-то мы можем с этим поиграть.

#include <iostream>
#include <string>
#include <vector>

//using namespace std;
// Get into the habit of not dragging an entire namespace into your code.
// It is totally worth your time to get used to just typing “std::”
// (or whatever the correct namespace is) in front of objects and functions.
// It is easy and gets you to better learn when you _shouldn’t_ do it.

// Here's a helper to make testing easy
void test( std::string s )
{
    std::cout << "\n[" << s << "]\n";  // print before
    delete_x_stars( s );
    std::cout << "[" << s << "]\n";    // and after
}

int main()
{
    const std::string s = "abcdef*gh*i";

    // We can use a vector (or any indexed sequence) to play with the string
    std::vector <char> v( s.begin(), s.end() );

    std::cout << "[";  for (char c : v) std::cout << c;  std::cout << "]\n";  // before
    delete_x_stars( v );
    std::cout << "[";  for (char c : v) std::cout << c;  std::cout << "]\n";  // after

    // We can even use (a copy of) our original string
    test( s );

    // And we can verify that it works for special cases,
    // such as leading and consecutive stars
    test( "*ab**c" );
    test( "***" );
    test( "a***" );
    test( "ab**" );
    test( "*b**" );
    test( "*b" );
    test( "*" );
    test( "" );
}

Резюме

Не хочу ничего преувеличивать, но опять же идея состоит в том, чтобы иметь указатель/индекс/итератор для позиции чтения и другой для позиции записи. Это работает со всеми типами контейнеров, если контейнер заказан. (Так, например, это плохо для хэш-карты, поскольку элементы не упорядочены относительно, но отлично подходит для векторов, деков, файлов, строк и т. д., поскольку их элементы упорядочены.)

Даже простые операции по индексированию массивов (например, игра со строками char* в C) очень легко выполнить с помощью этого базового преобразования чтения-фильтрации-записи.

На самом деле обучение программированию требует довольно большого времени, но вам просто нужно уяснить это. Продолжайте в том же духе, и станет легче (и интереснее)! 🙂