使用std::vector实现时间和内存高效的工作

Question

我目前正在实现Astar算法，其中每个节点都存储在向量中，然后返回给外部对象 - 就像这样：

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();，因为它可能会有很多复制（更不用说在Astar类中的push_back()也会复制值）。我想到的可能解决方案是：将Foo的std :: vector & lt;Node> path;引用作为参数传递给Astar的find()，或者在Foo和Astar之间建立友谊，以便Foo可以访问私有路径。我优先考虑时间和内存效率（时间优先于内存）。

- 412131

---

如果你进行基准测试，我相信你会感到惊讶。具体来说，要对“拷贝省略”和“返回值优化”进行一些研究，以及对“移动语义”的一些研究。 - Some programmer dude

你可能想使用 reserve() 来减少在 find() 中的复制和移动。 - Persixty

Answer 1

首先要记住，C++允许返回值优化，因此按值返回vector本身并不是问题。

然而：

• 重复分配可能只需分配一次的对象是很昂贵的。因此，你可以理论上让方法接受一个路径的引用或指针，该路径必须保证具有足够的内存。这样，外部代码只需分配一次，就可以重复调用其缓冲区。
• 构造一个你不打算使用的对象是很昂贵的。因此，你可能需要一个名为has_path(const Node& source, const Node& target)的方法，甚至是具有该功能的独立函数。

- einpoklum