CODEWITHSUNDEEP
c++performancec++11vector
412131
412131

Reputation: 91

Time/memory efficient work with std::vector

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).

Upvotes: 3

Views: 147

Answers (1)

einpoklum
einpoklum

Reputation: 132182

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.

Upvotes: 1

Related Questions