Блог

Главная - Вопросы по программированию - Возвращаемое значение из списка / очереди C

Возвращаемое значение из списка / очереди C

#c #c 11 #stl

#c #c 11 #stl

Вопрос:

У меня есть код на C следующим образом :

 #include <iostream>
#include <queue>
#include <list>
using namespace std;

int main(){
    priority_queue<pair<int, int>> q;
    q.push({8, 8});
    q.push({19, 19});
    q.push({23, 23});

    while (q.size() > 0){
        autoamp; cur = q.top();
        q.pop();
        cout << cur.first << " " << cur.second << " "; // returns 19 19 8 8 8 8
    }
    cout << endl;

    list<pair<int, int>> newq;
    newq.push_back({19, 19});
    newq.push_back({8, 8});
    newq.push_back({23, 23});
    while (newq.size() > 0){
        autoamp; cur = newq.front();
        newq.pop_front();
        cout << cur.first << " " << cur.second << " "; // returns 19 19 8 8 23 23
    }
    cout << endl;
    return 0;
}

Повторение с list использованием autoamp; vs auto приводит к тому же результату. Но я пытаюсь понять, почему, если я использую autoamp; во время итерации по очереди приоритетов, вывод неверен. Если я изменю его на auto правильный вывод:

     priority_queue<pair<int, int>> q;
    q.push({8, 8});
    q.push({19, 19});
    q.push({23, 23});

    while (q.size() > 0){
        auto cur = q.top();
        q.pop();
        cout << cur.first << " " << cur.second << " "; // returns 23 23 19 19 8 8
    }
    cout << endl;

Спасибо за любые разъяснения!

Ответ №1:

     autoamp; cur = q.top();
    q.pop();

Причина auto amp; , по которой здесь не работает и auto работает, заключается в том, что при auto amp; этом вы получаете ссылку на объект в top() начале очереди…

… и сразу же, в следующей строке, этот объект в верхней части очереди удаляется и уничтожается, оставляя вас с висячей ссылкой.

Использование этой ссылки с этого момента приводит к неопределенному поведению.

auto Вместо этого используется копирование объекта, и копия продолжает существовать после уничтожения исходного объекта.

Конечно, возможно, что аналогичная ошибка при использовании с std::list не приводит к явно неправильным результатам, но это все еще неопределенное поведение. «Неопределенное поведение» означает именно это: может случиться все, что угодно. Включая получение ожидаемых результатов, чисто случайно. Хороший инструмент статического анализа, такой как valgrind, должен быть в состоянии обнаружить эту ошибку.

Комментарии:

1. Но разве код не присваивает ссылку на top в каждой итерации цикла cur ?

2. Нет, это не так. auto amp; является ссылкой на другой объект. Не копия другого объекта. auto cur является полноценным объектом. auto amp;cur является ссылкой на какой-либо другой объект. Как вы думаете, в чем разница между auto cur и auto amp;cur ? auto amp;cur=q.top() является ссылкой на объект в верхней части очереди. pop() уничтожает этот объект. Этого больше нет. Он перестал существовать. Он тоскует по фьордам. Это бывший объект. Тот факт, что где-то была ссылка на объект, не мешает его уничтожению.

3. хорошо, я думаю, я понимаю. Но даже тогда я подумал, что, поскольку я переназначаю ссылку в cur top на каждой итерации, она должна работать без создания копии пары. Как мне включить фактический объект top cur без копирования?

4.@pranav3688 Просто распечатайте cur перед выполнением pop . Ссылка будет действительна до тех пор.

5. @SamVarshavchik: Я пытался использовать Valgrind в этом коде. Это не улавливается. Но спасибо!

Ответ №2:

Когда вы делаете:

 autoamp; cur = q.top();

вы берете ссылку на верхний элемент в priority_queue . Но когда вы делаете:

 q.pop();

этот элемент удаляется, и все ссылки на него, в том числе cur , остаются висячими. Любая попытка чтения, cur например:

 cout << cur.first << " " << cur.second << " ";

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

Выполнение:

 auto cur = q.top();

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