Member Avatar for aravind rao

Hi

I am developing a program that uses Breadth First Search to map a grid(2d array) out. Breadth First Search involves storing nodes in a stack and then exploring these nodes based on Breadth or level. I know how to create a vector array which I shall use as a stack. I need to know how to store array elements in the stack using the

push_back()

method. This is what I have so far..

vector<int>stack; //stack initialization.
stack.push_back(array[1][1]) //store array element itself, not Value held in array!

The value stored is not the array element, but the value which happens to be some integer x.

Thanks for helping.

  • 3 Contributors
  • 4 Replies
  • 209 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by aravind rao

Dani AI

Generated

Short answer: a vector<int> holds integer values. If you want to track which cell in a 2D grid you visited (so you can revisit or modify it later) store a location (coordinates or an index) or a pointer to the cell — not just the integer value. As discovered, storing the address is possible and compact, but it carries lifetime and reallocation risks. And as implied, BFS is a FIFO traversal: use a queue/deque, not a LIFO std::stack.

Safer and idiomatic for BFS: store a small coordinate type in a queue. This keeps code clear and avoids pointer lifetime problems:

struct Pt { int r, c; };
std::queue<Pt> q;
q.push({startR, startC});
visited[startR][startC] = true;

const int dr[4] = {-1,0,1,0}, dc[4] = {0,1,0,-1};
while (!q.empty()) {
    Pt p = q.front(); q.pop();
    for (int k = 0; k < 4; ++k) {
        int nr = p.r + dr[k], nc = p.c + dc[k];
        if (inBounds(nr,nc) && !visited[nr][nc]) {
            visited[nr][nc] = true;
            q.push({nr,nc});
        }
    }
}

If you care about cache locality or want smaller payloads, push a single flat index (r*cols + c) into the queue and reconstruct row/col when you pop. That often performs better than storing pairs on large grids.

Pointers are fine only when the underlying storage is guaranteed not to move (C-style 2D arrays or a single flat std::vector you never reallocate). Avoid storing pointers to elements of std::vector<std::vector<int>> unless you know those inner vectors will not reallocate. Common bugs to watch for: forgetting to mark a cell visited before pushing (causes duplicate pushes), pushing addresses of temporaries, and using std::vector + pop_front() (use std::deque or std::queue instead for O(1) pops).

Recommended Answers

All 4 Replies

Member Avatar for NathanOliver

if you want to store the address of that element in you vector than you can do

vector<int*> stack
stack.push_back(&(array[1][1]))

if you are trying to store the value of x and y values you can use a 2d vector like

vector< vector<int> > stack
vector<int> temp;
if (array[x][y] == something)
{
    temp.push_back(x);
    temp.push_back(y);
    stack.push_back(temp);
    temp.clear();
}

although this might not be the best way to do it.

commented: Great helpful post +0
Member Avatar for LordNemrod

Why would you want to simulate a stack for a vector if there is already an implemented stack?!

#include <stack>
#include <iostream>
int main()
{
 std::stack<int>  st;
 st.push(1);
 st.push(3);
 std::cout << st.top() << std::endl; // outputs 3;
 st.pop();
 std::cout << st.top() << std::endl; //outputs1
}
Member Avatar for aravind rao

Why would you want to simulate a stack for a vector if there is already an implemented stack?!

#include <stack>
#include <iostream>
int main()
{
 std::stack<int>  st;
 st.push(1);
 st.push(3);
 std::cout << st.top() << std::endl; // outputs 3;
 st.pop();
 std::cout << st.top() << std::endl; //outputs1
}

Well I looked into it, but for a Breadth First Search I need a FIFO(First In First Out) type stack. The one above is LIFO. So unless there is actually a FIFO stack, which I think only exists in a queue, I wont be using any stacks.

Thanks for replying.

Member Avatar for aravind rao

if you want to store the address of that element in you vector than you can do

vector<int*> stack
stack.push_back(&(array[1][1]))

if you are trying to store the value of x and y values you can use a 2d vector like

vector< vector<int> > stack
vector<int> temp;
if (array[x][y] == something)
{
    temp.push_back(x);
    temp.push_back(y);
    stack.push_back(temp);
    temp.clear();
}

although this might not be the best way to do it.

Great post, both methods worked, although the pointer method is more efficient. I knew pointers were the answer, thanks for showing me how!

Thanks for replying.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.