c++ - 使用std::vector的时间/内存高效工作

我当前正在实现Astar算法，其中每个节点都存储在vector中，然后返回到外部对象-像这样:

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;
   }
}

在外部目标代码看起来类似于:

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

之所以存在findPath()，是因为我想使其在另一个线程中运行，因此，如果找到路径，则执行其他操作，也许是时候找到路径(简化)了。困扰我的是path = astar.find();，因为它可能会大量复制(更不用说push_back()类中的Astar也会复制值)。

我考虑过的可能解决方案是:将Foo的std::vector<Node> path;引用作为Astar的find();的参数传递，或者在Foo和Astar之间建立友谊，以便Foo可以访问私有(private)路径。在我之前是时间和内存效率(内存时间)。

最佳答案

首先请记住，C++允许使用Return Value Optimization，因此按值返回 vector 本身并不是问题。

然而:

重复分配可能只分配一次的对象是很昂贵的。因此，从理论上讲，您可以使该方法对路径的某个缓冲区采用引用或指针，必须保证该缓冲区具有足够的内存。这样，外部代码甚至只分配一次，并且可以将其缓冲区重新用于重复调用。

构造您不打算使用它的对象会很昂贵。因此，您可能需要一个名为has_path(const Node& source, const Node& target)的方法，或者甚至具有该功能的独立函数。