Блог

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

Функция для поиска дубликатов с использованием хэш-таблицы ##

  std::vector<std::string>find_duplicates_with_hashtable(std::vector<std::string> amp; strings) {

        std::vector<std::string> dups;
        typedef std::unordered_map<std::string, std::string> hashtable;
        hashtable table;

        for (std::vector<std::string>::iterator i = strings.begin(); i < strings.end(); i  ) {
        std::unordered_map<std::string, std::string>::const_iterator it = table.find(*i);
        if (it != table.end() amp;amp; (std::find(dups.begin(), dups.end(), *i)) == dups.end()) {
            dups = find_duplicates_with_sorting(dups); // line causing the problem
        }
        table.emplace(*i, *i);
        }

        return dups; 
  }
  

Функция, используемая для проверки, присутствуют ли какие-либо элементы в данном векторе в векторе дубликатов

 std::vector<std::string> find_duplicates_with_sorting(std::vector<std::string> amp; strings) {
    std::vector<std::string> dups;

    std::sort(strings.begin(), strings.end());

    for( unsigned int i = 0; i < strings.size() - 1;   i ) {
        if( strings[i].compare(strings[i 1]) == 0 ) {
            std::string found_dup = strings[i];
            if( dups.size() == 0 ) {
                dups.push_back(found_dup);
            }
            else
            {
                std::string last_found_dup = dups[ dups.size() - 1 ];
                if( last_found_dup.compare(found_dup) != 0 ) {              // Not a dup of a dup
                    dups.push_back(found_dup);
                }
            }
        }
    }

    return dups;
}
  

Это контекст, в котором вызывается функция хэш-таблицы

 TEST(BaseHash, SuperShortVector)
{
    std::vector<std::string> dups_found;
    auto amp; search_vector      = super_short_vector;
    auto amp; known_dups_vector  = super_short_vector_dups;

    dups_found = find_duplicates_with_hashtable(search_vector);

    std::sort(dups_found.begin(), dups_found.end());
    std::sort(known_dups_vector.begin(), known_dups_vector.end());


}
  

Строка, вызывающая проблему, отмечена комментарием в функции ‘find_duplicates_with_hashtable’

Кроме того, поскольку это домашнее задание, я был бы очень признателен, если бы кто-нибудь объяснил, что я сделал не так, и просто дал мне общее направление, в котором я мог бы работать, чтобы устранить проблему, поскольку простое копирование-вставка кода не помогло бы мне научиться

Извините, если код ужасен. У меня возникли проблемы с пониманием того, как использовать хэш-таблицы.

Спасибо 🙂

Здесь происходит ошибка сегментации:

 for( unsigned int i = 0; i < strings.size() - 1;   i ) {
        if( strings[i].compare(strings[i 1]) == 0 ) {
  

Проблема в том, что вы сравниваете значение без знака, i со значением без знака, возвращенным из strings.size() - 1 . Когда strings.size() является 0 , эта часть i < strings.size() - 1 будет проверять, i меньше ли оно наибольшего целого значения, которое (в принципе) всегда будет истинным.

Это приводит к strings[i 1] ошибке сегментации, когда strings длина равна 0 или 1.

Это можно исправить многими способами, но for( int i = 0; i < (int)strings.size() - 1; i ) { это был бы быстрый и грязный способ исправить это.