c++ - 如何有效地将 STL 容器恢复到旧值

Question

我有一个大类表示一个图。此类包含多个复杂类型的容器( vector 和集合)。在搜索过程中，我需要修改图形以避免结果中出现循环。由于我必须运行许多搜索，因此我需要经常将类恢复到其原始状态。

目前我只是将保存的容器分配给修改后的容器:

 void Graph::restore(){
   mEdges=mSafeEdges; //std::vector<Edge> Edge has no heap based data
   mNodes=mSafeNodes; //std::vector<GraphNode> A Graph Node contains std::set<int>
 }

正如我所说，边和节点很复杂，每个节点包含例如一套。每对容器具有相同的大小。分析我的代码表明，简单的恢复功能是程序的主要瓶颈，每次运行大约需要 6 毫秒。边缘 vector 需要 1.5 毫秒来复制，节点需要 4.5 毫秒。是否有更好、更快的方法来复制复杂类型的容器或至少复制边缘 vector ？

Answer 1

如果您在每次搜索时只修改部分对象，那么您可以看到写时复制是否有帮助。

template<typename T>
class Cow {
  std::shared_ptr<T> owned;
  const Node* non_owned;
public:
  explicit Cow(const T& n) : non_owned(n) { }
  const T& get() const { return *non_owned; }
  T& copy() {
    if (!owned) {
      owned = std::make_shared<T>(*non_owned);
      non_owned = owned.get();
    }
    return *owned;
  }
};

然后替换mEdges和 mNodes带有 Cow<Edge> 的容器和 Cow<GraphNode> (或者只对节点执行此操作，因为这是复制成本更高的类型)。

您必须修改搜索逻辑以使用包装器类型(或为其提供一个到 const T& 的转换运算符)，然后显式添加对 copy() 的调用当你想要一个可修改的对象时，除非必要，否则你会避免复制对象。