1 Тема від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 473
    • Репутація: 84

Тема: Помилка при обробці посилання на вказівник

Треба обійти дерево і зібрати все листя.
Зробив ось так:

void check_trees(TreeNode *root, vector<int> &leafs) {
    stack<TreeNode *> root_nodes;
    root_nodes.push(root);

    while (!root_nodes.empty()) {
        const auto node = root_nodes.top();
        root_nodes.pop();
        if (!node->left && !node->right) {
            leafs.push_back(node->val);
        }
        if (node->left) {
            root_nodes.push(node->left);
        }
        if (node->right) {
            root_nodes.push(node->right);
        }
    }
}

Але спочатку я використав посилання на вказівник, ось тут:

const auto &node = root_nodes.top();

І в такому варіанті збиралася лише частина листя в деяких випадках.
Чому так?

2 Відповідь від steamwater Востаннє редагувалося steamwater (22.10.2024 22:36:31)

  • steamwater
  • Користувач
  • Поза форумом
  • Дата реєстрації: 17.02.2024
  • Повідомлень: 93
    • Репутація: 16

Re: Помилка при обробці посилання на вказівник

Teg Miles, моя думка така: оскiльки верховина стеку це lvalue, то константне посилання на нього не утворює тимчасового объ'єкта. Тож, ваша const auto& node перетворюється на const Treenode *& node, де  Treenode * node це лiвобiчне значення обмежене щодо модiфiкацiї. Пiсля root_nodes.pop(), це посилання утворює UB. Бо pop очевидячки делетить ноду що мiстить непотрiбного вказника у стецi (якщо стек реалiзований як список, скажiмо).  А от коли ви кажете: const auto node то спонукаєте копiювання значення з верховини у об'явлений вказiвник i вже байдуже на те, що pop зробить з орiгиналом. Тож, як атеiст, раджу вам не довiряти popам. Бо може трапитись popа. I почитайте про константне посилання. Це перший звiр посилочної породи, якого навчили зв'язуватись з rvalue, при тому, що на lvalue вiн теж охоче нападає. Проте, його поведiнка у першому випадку дуже цiкава. Вiн подовжує життя тимчасового объекту до закiнчення областi. Але тут не той випадок. Спробуйте:

 const auto &node = std::move(root_nodes.top());
//чи навiть:
 const auto &&node = std::move(root_nodes.top());

Так повинно спрацювати. Але варiант const auto node тут найкращiй, мабуть.

Подякували: Teg Miles1

3 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Помилка при обробці посилання на вказівник

Teg Miles написав:
const auto &node = root_nodes.top();

означає, що node є посиланням на об'єкт (покажчик) на верхівці root_nodes. Будь-яка зміна root_nodes (наприклад, root_nodes.pop() чи root_nodes.push(...)) може призвести до того, що цей покажчик буде переміщено, а посилання стане некоректним. До того ж ви таким чином нічого не економите: під капотом, покажчик - це вказівник, і ви маєте в результаті вказівник на вказівник там, де можна використати просто вказівник.

koala вебсайт