CODEWITHSUNDEEP
c++c++11vectorscopebreadth-first-search
clo_jur
clo_jur

Reputation: 1409

Scope of an Object in a Loop

I have a simple algorithm which returns a list of lists, where each inner list contains the nodes on a different level of a binary tree. I'm having trouble understanding how to "reset" the scope of my inner list (e.g. see below).

My tree is a simple toy tree like so:

struct Node {
    int data;
    Node *left, *right;
}

I use a simple bfs that should return a list of lists. I try to create a new list on each of the loops, but I'm not sure how to "clear" the list and start a new one.

std::vector< std::vector<Node *> > build_lists(Node *root) {
    std::vector< std::vector<Node *> > result;

    Node *newline = new Node { std::numeric_limits<int>::min(), nullptr, nullptr };

    std::deque<int> q;
    q.push_back(root);
    q.push_back(newline);


    Node *tmp;
    std::vector<Node *> inner;    // HERE IS WHERE IS SET THE FIRST INNER VECTOR
    while(!q.empty()) {
        tmp = q.front();
        q.pop_front();
        if (tmp == newline) {
            result.push_back(inner);
            std::vector<Node *> inner; // HERE IS WHERE I TRY TO ''RESET'' THE VECTOR
            if (!q.empty())
                q.push_back(newline);
        } else {
            inner.push_back(tmp);
            if (tmp->left)
                q.push_back(tmp->left);
            if (tmp->right)
                q.push_back(tmp->right);
        }
    }
}

Clearly, I have failed to understand scope and some basic language features. If anyone could help point me in the right direction, I would appreciate it.

Upvotes: 1

Views: 292

Answers (2)

Xeren Narcy
Xeren Narcy

Reputation: 875

You can't reset a variable by declaring it again, which is what your code is doing. You now have a second variable with the same name, that for the duration of the second variable that name points to the second variable.

Instead you need to use a method to clear the first variable.

vector does have a method to reset it's contents - vector::clear.

You should do this instead:

result.push_back(inner);
// std::vector<Node *> inner;
inner.clear();

If you need to clear something you've pushed inside a vector, you can do this:

vector< vector< int > > vvi;
vector< int > vi;
vi.push_back(1); // fill
vii.push_back(vi); // vii has a copy of vi as it is now.
auto & _v = vii[0]; // fetch a reference to the copy
_v.clear(); // clear it
vii[0].clear(); // same in one step
assert( vii[0].size() == 0 ); // still contains a vector at index 0 but it's empty

Notwithstanding the fact that you would be clearing vectors of pointers - as others have pointed out (ha) you need to be very careful not to 'lose track' of pointers.

Eg, this would be bad:

vector< int* > x;
x.push_back( new int(4) );
x.clear(); // leak

Upvotes: 2

gsamaras
gsamaras

Reputation: 73366

In order of an object to go out of scope, it has to be created INSIDE the loop, like this for example:

while(1) {
  std::vector<int> v;
  ...
  // at that point 'v' will go out of scope and thus destroyed
}

However, when you do this:

std::vector<int> v;
while(1) {
  ...
  // 'v' is always the same at this point
}

You could use std::vector::clear() to reset your vector, but be careful, since you are using pointers. Unless you keeping track of the pointed objects, just clearing the vector would result to dangling pointers, thus Undefined Behavior and you don't want that to happen.

If you need to free the memory the pointers point to, then you should first delete the objects the pointers point to and then clear the vector.

Upvotes: 0

Related Questions