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

Question

我目前正在实现 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)路径。摆在我面前的是时间和内存效率(time over memory)。

Answer 1

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

但是:

• 重复分配可能只分配一次的对象的成本很高。因此，理论上您可以让该方法采用引用或指针指向路径的某个缓冲区，必须保证有足够的内存。这样，外部代码甚至只分配一次，并且可以重新使用其缓冲区进行重复调用。
• 构建一个您不打算使用它的对象的成本很高。因此，您可能需要一个名为 has_path(const Node& source, const Node& target) 的方法，或者甚至是具有该功能的独立函数。