How to add elements to a vector and traverse it simultaneously?

Question

I want to perform BFS on a tree, to find out a certain leaf, but the graph is dynamic in nature, when I land on a leaf and that leaf isn't the one I am looking for, then its children are computed from the leaf (The leaf is no longer a leaf it is a node). enter image description here

I tried two implementations , and both produced erronous results. I think the pointers are getting invalidated or this is an incorrect implementation. My code is as follows

int y=0;
while(graph.end() - graph.begin() < 262145  and   graph.end() - graph.begin() < y){
        if(found(graph[y])){
            clock2 = graph[y];
            break;
        }
        else{
        if(graph[y].b[0] < 4) graph.push_back(move1(graph[y]));
        if(graph[y].b[1] < 4) graph.push_back(move2(graph[y]));

    }
    y++;
}

and the next implementation was something like this

for(vector<foo> :: iterator i = graph.begin();i!=graph.end();i++){
    if(found(*i)){
        clock2 = *i;
        break;
    }
    else{
        if(i->b[0] < 4) graph.push_back(move1(*i));//move1 and move2 are
        if(i->b[1] < 4) graph.push_back(move2(*i));//functions of return type foo
    }
}

Both of these are causing the programme to crash. What is wrong with them, how to implement these? Please comment with additional queries.

possible duplicate of [Iterator invalidation rules](http://stackoverflow.com/questions/6438086/iterator-invalidation-rules) — Scis, Jun 10 '14 at 18:10
You cannot use vector as certain insertions may invalidate iterators, say when the size exceeds capacity. — Coder777, Jun 10 '14 at 18:11
In the first snippet, this doesn't look right: `graph.end() - graph.begin() <= y`. — laune, Jun 10 '14 at 18:13
what magic number is this ? graph.end() - graph.begin() < 262145 — AndersK, Jun 10 '14 at 18:14
That i sthe maximum allowable size of the tree... 4^9 +1 to be precise — Soumadeep Saha, Jun 10 '14 at 18:16
`graph.end() - graph.begin() < 262145` That line is totally wrong. Where does it state that vector iterator's are integral values? If you want to compute the "distance" between two iterators, use `std::distance` — PaulMcKenzie, Jun 10 '14 at 18:35
The second snippet is not correct due to the fact that vector iterators can become invalidated when adding elements. Basically you're looping over a container while adding items to the container. If you really want to add items like that, then use a `std::list`, not vector. The `std::list` iterators remain valid on insertion. — PaulMcKenzie, Jun 10 '14 at 19:18
Seems like you could make the second snippet work if you used an index instead of an iterator. But you should consider using a std::queue instead. — D Drmmr, Jun 10 '14 at 19:21
Just use ordinal indexes, `operator []`, and boundaries by `0` and `< size()` rather than iterators. — WhozCraig, Jun 10 '14 at 21:30

Jay · Answer 1 · 2014-06-10T19:58:06.770

0

I am a little confused as too what exactly is going on and what exactly you are asking. But if you are asking how to preform a simple BFS on a graph here is some sample code that I find pretty easy to read.

Comment further and I will change it to try and match the exact criteria of the question (once I have some more clarity that is)

struct node{
   std::vector children<node*>;
   int data;
}
void bfs(node* root, int value){ // THIS IS CHECK FOR INTS so change for whatever value
    if(!root) return;
    std::queue myq;
    myq.push(root);
    node* toCheck;
    while(!myq.Empty()){
         toCheck = myq.top();
         myq.pop();
         if(toCheck->data == value){
              //do whatever you want with that information
         }else{
         /*
          //forloop/whileloop as many times as necessary to set all the new children
           //Example:
              node* newNode = new node();
              newNode->data = someValue; // just some information that you want to add
              toCheck->children.push_back(newNode);
         */
         }
         for(int i = 0; i < toCheck->children.size(); i++){
              myq.push(toCheck->children[i]);
         }
    }
}

edited Jun 10 '14 at 19:58

answered Jun 10 '14 at 18:14

Jay

2,656
1
16
24

I have edited my question. See if you can understand better now – Soumadeep Saha Jun 10 '14 at 18:38
Wait so the tree is not already made? On what conditions do you decide to make more nodes? How many nodes? Is the tree already flat? (already in a vector)? i.e no need to process left/right only run through the vector? – Jay Jun 10 '14 at 18:46
The tree is not already made. I add more nodes when the current node is not the node I am searching for. i.e to say suppose I am trying to guess a password (for the sake of not having to draw a lot of branches lets consider it is in binary) I would do it like this. Is it 0, yes ? fine. No? is it 1. Yes? Fine. No? Is it 00 ? Yes . Fine. No? Is it 01? and hence forth... – Soumadeep Saha Jun 10 '14 at 18:51
And @Jay it is not a binary tree for gods sake... each node can have upto 9 children. – Soumadeep Saha Jun 10 '14 at 18:52
1

Hey man it doesn't matter if it is binary tree or not. A binary tree is a subset of graphs. I just used it as an example. I fixed the code. Tell me if I am more on the right track. – Jay Jun 10 '14 at 19:06
Well you are on the right track... help appreciated. I think i got the solution I was looking for. Will let you know if it doesn't work – Soumadeep Saha Jun 10 '14 at 19:15
http://paste.ubuntu.com/7625177/ here is complete code. Still producing errors for certain inputs – Soumadeep Saha Jun 10 '14 at 19:44
I will upvote all comments and answers when it works dont worry. The error too slow and the online judge where i submitted it gives: Run 3: Execution error: Your program had this runtime error: Bad syscall #32000175 (RT_SIGPROCMASK) [email kolstad if you think this is wrong]. The program ran for 0.143 CPU seconds before the error. It used 16280 KB of memory. Your program printed data to stderr. Here is the data: terminate_called_after_throwing_an_instance_of_'std::bad_alloc' __what():__std::bad_alloc – Soumadeep Saha Jun 10 '14 at 20:20
Actually it is fast enough... it throws bad_alloc – Soumadeep Saha Jun 10 '14 at 20:25
does the while execute forever? lets say you very find it will it continue? because the var `temp` may never be set if `found(temp)` is never true – Jay Jun 11 '14 at 00:12
@SoumadeepSaha huh? No lets say `found(temp) is never == true` the program will go on forever. Is this a case to look out for? – Jay Jun 11 '14 at 21:35
@SoumadeepSaha also how much memory does this system have? I hope more then 16 MB.. which could be the reason for the bad_alloc if its <16 MB – Jay Jun 11 '14 at 21:40
@Also I can't help as much unless you show more of the problem (i.e what you have done to debug it). Like have you tested if it works up until a line or something of the sort. – Jay Jun 11 '14 at 22:26
I have made the graph a queue... and each time i push the elements and yeah the grader has 16 MB of memory... And I have no idea how much my system has ... How do I find out? – Soumadeep Saha Jun 13 '14 at 09:41

How to add elements to a vector and traverse it simultaneously?

1 Answers1