Ошибка сегментации при использовании приоритетных очередей

У меня есть приоритетная очередь с элементами класса с именем A. Мне нужны элементы из этой очереди, которые могут быть ниже в очереди (уменьшают приоритет). Итак, я пытаюсь вытолкнуть несколько элементов, пока не получу элемент по своему выбору. Как только я получу элемент по своему выбору, я планирую отправить все элементы, которые я временно сохранил в массиве. У меня есть цикл, и для каждой итерации я иду дальше по очереди, чтобы проверить, является ли элемент, который я вытолкнул, моим выбором. Таким образом, у меня есть больше данных во временном массиве. Проблемы возникают, когда я пытаюсь отправить данные из этого временного массива обратно в очередь приоритетов. Базовым контейнером приоритета является вектор, и отладка показывает, что проблема в stl_queue.h со строкой std::push_heap(c.begin(), c.end(), comp); (с — вектор)

Я знаю, что это может быть неправильный способ сделать это, и мне, вероятно, следует использовать конструктор вместо malloc и иметь std: list вместо приоритетной очереди, но может ли кто-нибудь сообщить мне, что здесь происходит?

while(count < length_of_queue) // Iterate over all elements of queue
{

  A* temp_array = (A *)malloc(count * sizeof(A));;
  for (int i = 0;i<count;i++) // remove count number of elements from queue
  {
      temp_array[i] = priority queue.top();
      priority queue.pop(); // free_list is the priority queue
  }

  A check_element = free_list.top(); // Check if (count+1)th elements satisfies our         
                                     // criteria   
  if (criteria_satisfied)
  {
    priority_queue.pop();
    //freeing the temp_array and pushing back all the elements from temp_array into 
    // priority_queue like done in the else condition
    return check_element;
   }
  else
  {

    for (int i = 0;i<count;i++) // Push back all the elements popped until now
    {
      priority_queue.push(temp_array[i]); // Offending line
    }
    free (temp_array);
  }
  count++
}

person cyrux    schedule 29.07.2010    source источник
comment
Лучший способ получить помощь — предоставить свободный компилируемый фрагмент кода, показывающий проблему. Поскольку этот код не соответствует этим требованиям, то, что вы просите, усложняется и может быть невыполнимым, потому что проблема может быть даже не в предоставленном вами коде.   -  person Martin York    schedule 29.07.2010
comment
Замените строку с malloc на вектор. Приведенный выше код очень плохо протекает.   -  person Martin York    schedule 29.07.2010
comment
Вы не освобождаете (local_bd_arr) перед возвращением. Также вы не отодвигаете назад ни один из предметов перед возвратом.   -  person    schedule 29.07.2010
comment
@martin, попытался сделать код более читабельным @shifbit, я удалил часть кода, где я освобождал массив перед его возвратом и несколько push(s), чтобы уменьшить размер кода.   -  person cyrux    schedule 29.07.2010
comment
Если вы написали этот код очистки массива дважды, то лучший способ сделать код более читабельным — переместить этот код в отдельную функцию.   -  person Dan Breslau    schedule 29.07.2010
comment
А как объявляется priority_queue?   -  person Dan Breslau    schedule 29.07.2010
comment
Почему вы используете malloc и free в программе на C++? Если на то пошло, почему вы вообще занимаетесь ручным управлением памятью?   -  person sbi    schedule 29.07.2010
comment
@cyrux: ваши упрощения не помогают. Нам нужно увидеть фактические определения классов нескольких объектов. Нам нужен фрагмент кода, который компилируется и запускается. Предоставленный код даже не скомпилируется, не говоря уже о запуске. Вы обнаружите, что при программировании место аварии обычно является побочным эффектом чего-то совершенно другого. Но мы можем найти совсем другую часть, так как вы ее не предоставили.   -  person Martin York    schedule 29.07.2010


Ответы (2)


Ваша строка malloc выделяет массив, достаточно большой для хранения count объектов типа A, но фактически не создает никаких объектов. Неопределенное поведение возникает (например, segfault), когда вы пытаетесь использовать объекты, которые не существуют.

Попробуйте заменить ваш malloc на std::vector<A> temp_array(count). Это даст вам (фактически) массив из count созданных по умолчанию A объектов. Что еще более важно, он освободится, когда выйдет за пределы досягаемости.

person Michael Kristofik    schedule 29.07.2010
comment
Правда, malloc создает массив для хранения количества объектов. Но позже я также делаю это temp_array[i] = priority queue.top(); где приоритетная очередь имеет элементы типа A. Итак, у меня есть мой первый объект. Причина, по которой я знаю, что это происходит, заключается в отладке конкретной строки priority_queue.push(temp_array[i]); Я проверил, что такое temp_array[i] (в данном случае i = 0), и он отменил ссылку на объект типа A, но, как ни странно, когда я вхожу в код, я получаю SIGTERM в stl_vector.h. Не делать векторы изначально, потому что у моего класса A не было конструктора по умолчанию - person cyrux; 29.07.2010
comment
и странно то, что даже без конструктора по умолчанию мой код теперь работает. У меня есть параметризованный конструктор в классе, который должен переопределять стандартный конструктор по умолчанию. - person cyrux; 29.07.2010

Если A не является POD, то использование malloc может вызвать всевозможные проблемы. Вместо этого используйте вектор:

std::vector<A> temp_array(count);

Тогда бесплатное исчезнет полностью.

person Mark B    schedule 29.07.2010
comment
Зачем О, зачем ты это делаешь! Используйте вектор во всех подобных ситуациях, чтобы вам не приходилось вручную управлять памятью. Каждый раз, когда ваш код выглядит так, как будто он содержит бизнес-логику и управление памятью, это запах кода. Код представляет собой либо бизнес-логику, либо управление памятью (никогда не смешивайте их). - person Martin York; 29.07.2010
comment
@martin, я согласен, что код воняет. Причина, по которой я не написал вектор ранее, заключается в том, что я думал, что если у вас есть оператор инициализации, такой как std::vector‹A› temp_array(count), он будет вызывать конструктор по умолчанию A count количество раз. У меня не было конструктора по умолчанию для класса A, а был только параметризованный. Поэтому подумал об использовании malloc. Позже, когда я изменил его на вектор после принятия предложений, код работал, что снова сбивает с толку, потому что мой класс A не имеет конструктора по умолчанию. Я знаю, что эта проблема решена, но я просто хочу знать, как происходит проверка кода. - person cyrux; 29.07.2010
comment
@cyrux Вы уверены, что для A нет конструктора по умолчанию? Если инициализация вектора компилируется, компилятор считает, что смог ее найти. - person Mark B; 29.07.2010
comment
@Mark, я почти уверен, что в классе A нет конструктора по умолчанию. Я только что отладил оператор вектора инициализации, чтобы посмотреть, что произойдет. Управление перешло от оператора инициализации › vector():_Base() (stl_vector.h) › allocator.h ›new_allocator.h и обратно в исходный файл. Он вообще не попал в класс А. Странный - person cyrux; 29.07.2010
comment
@cyrux: Пожалуйста, прочитайте мой комментарий к вашему вопросу. Вам нужно предоставить больше кода. например, определение класса A (есть целый ряд проблем, которые могут быть в определении класса, вызвавшем проблему, но без кода она никогда не будет решена). Сейчас он может работать, но это не поможет вам понять, почему он был сломан. Поэтому ВСЕГДА публикуйте компилируемую и работоспособную версию проблемы. - person Martin York; 29.07.2010