Vector member functions

[aerowenn]

I'm wondering something, I really need to be able to access the next to last entry in a vector in real time. I am aware of the vector.back() method, but I need the next entry back.

My situation is that I have a vector of pointers, the function is to find a path through a maze, it is recursive. It pushes back the object at the beginning of the function call, then it needs to make sure that the address we are looking at doesn't match the direction we just came from. In other words, since I just pushed in a new object, the object that is checking it's addresses, using vector.back() will check it against itself. You might say, simple, push back the object after you check... but it's recursive, once it finds an open path the function is called again, therefore calling again.

Being able to access next to last entry in a vector would solve my problems, I think...

[Duthomhas]

This is plenty fast:
v[ v.size() - 2 ]
Just make sure your vector has a size >1 before you use it.

(If it is a possibility that size < 2 then use v.at( v.size() - 2 ) instead; this incurs the runtime penalty of checking range each use, but keeps your app from crashing.)

Hope this helps.

[aerowenn]

lll

[Duthomhas]

Some quick questions:

1. The path through the maze will always be 100 steps long?
2. You are sure that your maze has not any cycles?
3. What does Sector::getSize() do? (Do you mean to say: path.size()?)

You might want to look up some graph theory. Particularly, the depth-first search algorithm.

Your start and finish nodes should have special status (meaning that you should be able to ask the node if it is the "begin" or "end" node in the maze).

It would be most efficient if you could add a "visited" flag to your Sector type, so you can avoid the back problem entirely... (see question 2).

Let me know and I'll see what I can do to help more.

[aerowenn]

lll

[aerowenn]

Sorry I also forgot to mention, well, at least mention all of it. The size value signifies the beginning and end. Size = 0 is the start, size = 100 is end. Any size that is not either of those is considered a cost, but it doesn't change how the maze is traversed. The sectors are read in from a text file, names, followed by a bit wise direction value 1 = North, 2 = East, 4 = South, 8 = West. If you have say... 'A' you can go West or East. If you have 4, you can go South, 5 North and South, or F all directions... those are just some examples of directions you can have, not all of them. You can read these sectors in as any dimensions, 2x3 5x5 or whatever, but each block has a sector with pointers in it.

[aerowenn]

I'm going to move this to a new post, and lay it out a little clearer, this looks confusing a messy!

[Duthomhas]

No, stick with it here.

If you can put a "visited" flag in your Sector then you will eliminate lookup time to see if a node is already visited.

The path argument is presumably the result of the function too, so it should be a reference. (Even if it isn't it should be a reference, otherwise you'll use up your stack space pretty quickly with all those copies of the previous vectors there.)

#include <algorithm>
#include <vector> 

bool findPath( std::vector <Sector*> & path, Sector* node )
  {
  // If we have found the final node, then we're done.
  if (node->getSize() == 100)
    {
    return true;
    }

  // Otherwise, we have to keep searching
  #if STATUS_HAS_VISITED_FLAG
    #define VISITED( node ) (node->visited)
  #else
    #define VISITED( node ) (std::count( path.rbegin(), path.rend(), node ))
  #endif

  // Add the current node to the path
  path.push_back( node );
  #if STATUS_HAS_VISITED_FLAG
    node->visited = true;
  #endif

  // Try north, east, south, and west (in that order) for unvisited
  // paths.
  if (node->getNorth() && !VISITED( node->getNorth() ) && findPath( path, node->getNorth() ))
    return true;

  if (node->getEast() && !VISITED( node->getEast() ) && findPath( path, node->getEast() ))
    return true;

  if (node->getSouth() && !VISITED( node->getSouth() ) && findPath( path, node->getSouth() ))
    return true;

  if (node->getWest() && !VISITED( node->getWest() ) && findPath( path, node->getWest() ))
    return true;

  #undef VISITED

  // If none of them worked, we need to backtrack. We'll remove this node from the
  // path (since this node leads to all dead-ends), and return the failure.
  path.pop_back();
  #if STATUS_HAS_VISITED_FLAG
    node->visited = false;
  #endif
  return false;
  }

This code does not minimize cycles (it does not necessarily find the shortest path). The VISITED macro above was defined just so you can see the two ways to test for the "visited" status: the first is if the node has a "visited" flag. The second is if it doesn't.

Hope this helps.