Time/memory efficient work with std::vector

Question

I'm currently implementing Astar algorithm in which each node is stored in vector and then returned to outer object - like this:

class Astar
{
   std::vector<Node> find()
   {
      std::vector<Node> open;
      std::vector<Node> closed;
      std::vector<Node> path;

      //A_star algorithm working with open and closed vectors
      //when path found fill path with push_back()

      return path;
   }
}

In outer object code looks similar to this:

class Foo
{
   Astar astar;
   std::vector<Node> path;
   void findPath()
   {
      path = astar.find();
   }
   //do stuff with path
}

Reason why findPath() exists is that I want to make it run in another thread, so if path is found - do stuff, else - maybe it's time to find path (simplifying). Thing that bothers me is path = astar.find(); because it can be a lot of copying (not to mention that push_back() in Astar class also copies value).

Possible solutions I thought about are: passing Foo's std::vector<Node> path; reference as an argument to Astar's find(); or make friendship in between Foo and Astar so Foo could access private path. Prior to me is time and memory efficiency (time over memory).

If you benchmark it, I'm sure you would be surprised. Do some research about copy elision specifically, and return value optimization in general. As well as some research about move semantics. — Some programmer dude
– Some programmer dude, Commented Aug 18, 2017 at 10:42
You may want to use reserve() to reduce the copying and moving in find(). — Persixty
– Persixty, Commented Aug 18, 2017 at 11:11

einpoklum · Accepted Answer · 2017-08-18 12:23:22Z

1

First remember that C++ allows for Return Value Optimization, so returning a vector by value is not in itself a problem.

However:

It is costly to do repeated allocations of objects which might be allocated just once. So you could theoretically have the method take a reference or a pointer to some buffer for the path, which must be guaranteed to have enough memory. That way, the outer code only even allocates once and may re-use its buffer for repeated calls.
It is costly to construct an object which you don't plan on using it. So you might want a method named has_path(const Node& source, const Node& target), or even a stand-alone function with that functionality.

answered Aug 18, 2017 at 12:23

einpoklum

138k86 gold badges446 silver badges917 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Time/memory efficient work with std::vector

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related