Why vector children is not modified?

Question

I want to modify vector stack entries in while loop, but somehow reference modification does not work. I thin i am modifying copied one, but i can't figure out how to modify real entry.

#include <iostream>
#include <memory>
#include <string>
#include <utility>
#include <vector>

int main() {
  struct Node {
    Node* parent;
    std::vector<std::unique_ptr<Node> > children;

    Node(Node* parent) : parent(parent){};
  };

  struct Tree {
    std::unique_ptr<Node> root;

    Tree():root(new Node{nullptr}){};
  };



  std::unique_ptr<Tree> t{new Tree};

  auto p = t->root.get();

  p->children.emplace_back(new Node{p});
  p->children.emplace_back(new Node{p});

  p = p->children[0].get();
  p->children.emplace_back(new Node{p});

  p = p->children[0].get();
  p->children.emplace_back(new Node{p});
  p->children.emplace_back(new Node{p});



  using Сhildren_const_iterator = decltype(std::cbegin(t->root->children));

  struct FirstCurrentLast {
    const Сhildren_const_iterator first;
    Сhildren_const_iterator current;
    const Сhildren_const_iterator last;
  };

  std::vector<FirstCurrentLast> stack;

  stack.push_back({std::cbegin(t->root->children),
                   std::cbegin(t->root->children),
                   std::cend(t->root->children)});





  auto print_stack = [&stack]() {
    std::cout << "/stack.size= " << stack.size() << "\n";

    std::string row1, row2, row3;
    for (auto&& it : stack) {
      row1.append(std::to_string(0)).append("_.");
      row2.append(std::to_string(it.current - it.first)).append("_.");
      row3.append(std::to_string(it.last - it.first)).append("_.");
    };

    std::cout << "first  |" << row1 << ";\n";
    std::cout << "current|" << row2 << ";\n";
    std::cout << "last   |" << row3 << ";\n\n";
  };





  while (!stack.empty()) {
    FirstCurrentLast& iterators = stack.back();
    Сhildren_const_iterator first = iterators.first;
    Сhildren_const_iterator& current = iterators.current;
    Сhildren_const_iterator last = iterators.last;

    std::cout << ">begin \n";

    print_stack();

    if (current == last) {
      stack.pop_back();
      continue;
    };

    if (!current->get()->children.empty()) {
      print_stack();

      stack.push_back({std::cbegin(current->get()->children),
                       std::cbegin(current->get()->children),
                       std::cend(current->get()->children)});

      print_stack();
    };

    iterators.current++;


    print_stack();

    std::cout << "end<\n\n";
    abort();
  };

  std::cout << "fini ok\n";
}

I get output:

>begin
/stack.size= 1
first  |0_.;
current|0_.;
last   |2_.;

/stack.size= 1
first  |0_.;
current|0_.;
last   |2_.;

/stack.size= 2
first  |0_.0_.;
current|0_.0_.;
last   |2_.1_.;

/stack.size= 2
first  |0_.0_.;
current|0_.0_.;
last   |2_.1_.;

end<

But it should look like this:

>begin
/stack.size= 1
first  |0_.;
current|0_.;
last   |2_.;

/stack.size= 1
first  |0_.;
current|0_.;
last   |2_.;

/stack.size= 2
first  |0_.0_.;
current|1_.0_.;
last   |2_.1_.;

/stack.size= 2
first  |0_.0_.;
current|1_.0_.;
last   |2_.1_.;

end<

Where exactly are you changing the value of elements? – NutCracker Feb 03 '20 at 14:55 — NutCracker, Feb 03 '20 at 14:55
@NutCracker - `iterators.current++;` – darkside Feb 03 '20 at 14:57 — darkside, Feb 03 '20 at 14:57

score 3 · Accepted Answer · answered Feb 03 '20 at 14:58

3

The problem might be because your iterators reference become invalidated by push_back on the stack vector. Try using a deque instead of vector or re-acquire the reference to the needed element of the vector after you call push_back.

answered Feb 03 '20 at 14:58

Andrey Semashev

10,046
1
17
27

Good catch, though unclear what you mean by "re-acquire the reference" – Slava Feb 03 '20 at 15:13
Usually, that means obtaining the reference again, after `push_back`, by using an index of the element. – Andrey Semashev Feb 03 '20 at 15:16
I got it, but still not clear how in C++ you could rebind a reference. As match as I know after created reference cannot change what it refers to. Can you explain mechanism you suggest? – Slava Feb 03 '20 at 15:20
You cannot rebind a reference, but you can destroy the old one (by enclosing it in a `{}` scope) and create a new one using the index. – Andrey Semashev Feb 03 '20 at 15:22
I see, thanks for clarification. In this particular case `auto oldcurrent = iterators.current++;` before addition would me much simpler but this code needs rework IMHO anyway, in this state it is way too unreadable. – Slava Feb 03 '20 at 15:29
more details on why this happening here https://stackoverflow.com/a/34708290/6569209 – darkside Feb 03 '20 at 15:29

Why vector children is not modified?

1 Answers1