Ошибка сегментации при использовании vector.push_back внутри определенных циклов

Question

В настоящее время я использую g ++ на терминале Cygwin согласно запросу моего профессора.

Я должен взять входной файл и прочитать его слово за словом, а затем поместить все слова в вектор, отсортировано по алфавиту и без дубликатов.

Однако каждый раз, когда я пытаюсь манипулировать моим вектором (т.е. push_back) внутри определенных циклов , моя программа просто вызывает ошибки сегментации.

Вот фрагмент моего кода:

void word_count(ifstream& input){
    string temp;
    vector<string> v;

    input >> temp; //set first variable
    v.push_back(temp);

    while (!input.eof()) { //I'm aware of the limitations while using !eof, this is just the way I am required to loop over a file
        input >> temp;

        for (vector<string>::iterator i = v.begin(); i != v.end(); i++) { //check entire vector for word
            if (*i == temp) { //just break and skip the word if it already exists
                break;
            }
            if (i == v.end() - 1) { //if the word doesn't exist yet
                for (vector<string>::iterator k = v.begin(); k != v.end(); k++) { //re-search the vector for the proper place
                    if (k == v.end() - 1) { //if at the end, just push_back the vector
                        v.push_back(temp); //Causes segmentation fault
                        break;
                    }
                    if ((*k < temp) && (*(k + 1) > temp)) { //find correct place and insert the word in the vector
                        v.insert(k, temp); //Also causes segmentation fault if execution even manages to get this far
                    }
                }
            }
        }
    }
}

Первый push_back в строке 5 отлично работает, я могу скопировать и вставить это несколько раз без ошибок. Я также могу нажать push_back сразу после ввода >> temp (внутри while l oop) без ошибок. Однако, если я попытаюсь нажать push_back под 'k' l oop, то произойдет сбой сегментации. Я в полном замешательстве.

Я пытался посмотреть на другие вопросы, связанные с вектором, здесь, в StackOverflow, но я не совсем понимаю, почему я могу (или не могу) использовать push_back в определенных местах.

Спасибо за любую помощь заранее!

Редактировать 1: Я должен упомянуть, что я протестировал его в VS 2019. Файл векторной библиотеки выскочил, сообщив, что было сгенерировано исключение «нарушение прав чтения-доступа». Нет ошибок сегментации (или, может быть, так VS сообщает, что произошла ошибка сегментации?)

Редактировать 2: Изменение вектора делает недействительными итераторы. Я не знал этого, спасибо всем за помощь!

Редактировать 3: Мне разрешено использовать только векторы, а не наборы или другие контейнеры. Если бы я мог использовать набор, я бы полностью.

Answer 1

При изменении вектора итераторы становятся недействительными.

Есть две причины:

• при push_back и std :: vector ::acity вылетает новый блок данных, и данные перемещаются / копируются в новый буфер
• , когда вы добавляете / удаляете элементы в среднем старом итераторе, он может указывать на другой элемент, возможно, больше не существующий.

Существует быстрый способ исправить это. Когда вы делаете модификацию, вы должны получить обновленное значение итератора. poush_back не имеет такой функциональности, но std :: vector :: insert возвращает итератор к новому значению, и этот итератор можно использовать для обновления для итератора l oop.

Я мог бы исправить ваш код, но он настолько запутан (до большого отступа), что я буду sh, чтобы избежать этого. Сначала вы должны разделить этот код на меньшие функции.

Вместо того, чтобы спасти ваш код, вот моя версия:

template<typename Iter>
size_t count_unique_items(Iter begin, Iter end)
{
    using value_type = typename std::iterator_traits<Iter >::value_type;
    std::unordered_set<value_type> unique_items;

    std::copy(begin, end, std::inserter(unique_items, unique_items.end()));

    return unique_itmes.size();
}

size_t count_unique_words(std::istream& input)
{
    return count_unique_items(std::istream_iterator<std::string>{input}, {});
}

https://wandbox.org/permlink/bHji7JZoB7E9ZoLn

Answer 2

Изменение вектора во время итерации по нему может сделать недействительными итераторы, и тогда может произойти все, что угодно.

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

Я бы (поскольку вы, вероятно, не должны использовать какие-либо функции из <algorithm> или такие «расширенные» функции)

• Прервите l oop, когда вы достигнете конца или когда вы нашли элемент,
• Если вы найдете элемент больше, чем элемент, вы должны вставить перед этой позицией и остановиться.
  К счастью, insert берет итератор чтобы вставить ранее, так что вы можете использовать i.

Примерно так:

for (vector<string>::iterator i = v.begin(); i != v.end() && *i != temp; ++i)
{
    if (*i > temp)
    {
        v.insert(i, temp);
        break;
    }
}

Обратите внимание, что break означает, что i не используется ни для каких сравнения после insert, поэтому я Вставка безопасна.

Answer 3

Как уже упоминалось, вы можете использовать std::set для хранения ваших уникальных слов. Вы можете заполнить его так:

std::set<std::string> set_of_words(std::ifstream & input)
{
  std::set<std::string> words;

  std::string word;
  while (input >> word)
  {
    words.insert(word);
  }

  return words;
}

или вы можете использовать std::vector как в вашем вопросе. Используя std::lower_bound из <algorithm>, вы можете использовать его следующим образом:

std::vector<std::string> vector_of_words(std::ifstream & input)
{
  std::vector<std::string> words;

  std::string word;
  while (input >> word)
  {
    auto pos = std::lower_bound(words.begin(), words.end(), word);
    if (pos == words.end())
    {
      words.push_back(word);
    }
    else
    {
      if (*pos != word)
      {
        words.insert(pos, word);
      }
    }
  }

  return words;
}