C ++将对象保存在列表中以供以后重用 [英] C++ Saving objects inside a list to reuse later

问题描述

假设我拥有保存在矢量中的边列表:

Suppose I own a list of edges saved inside a vector like:

typedef struct edge
{
  int v;
  size_t start;
  size_t end;
}e;

typedef vector<list<e>> adj_list;
adj_list tree;

我必须在此 tree 对象上执行逻辑，但是逻辑太复杂而无法就地执行(仅限于不可递归).我需要一个额外的数据结构来处理每个节点.作为一个简单的示例，让我们考虑增加每个边的v值:

I have to do logic on this tree object, but the logic is too complicated to do it in place (constricted to not recurse). I need an extra data structure to handle each node. As a simple example, lets consider incrementing each edge's v value:

list<e> aux;
  aux.insert(aux.begin(), tree[0].begin(), tree[0].end());
  while (!aux.empty())
    {
      e& now = aux.front();
      aux.pop_front();
      now.v++;
      aux.insert(aux.begin(), tree[now.v].begin(), tree[now.v].end());
      
    }

这样做的问题是对 now 变量所做的更改不能反映 tree 中的值.我需要一个列表(可以是任何列表(向量，链接，队列，堆栈)，该列表具有像Dijkstra这样的empty()布尔值)ds来处理 tree 中的 edge 对象.有没有一种优雅的方法可以做到这一点?我可以使用迭代器列表吗?我特别要问一个优雅"的人.希望它不涉及指针.

The problem in doing this is that the changes made to the now variable does not reflect the value in tree. I need a list(can be any list(vector,linked,queue,stack) that has an empty() boolean like Dijkstra) ds to handle my edge objects in tree. Is there an elegant way to do this? Can I use a list of iterators? I'm specifically asking an "elegant" approach in hopes that it does not involve pointers.

推荐答案

如注释中所述，解决方案是存储迭代器而不是副本，例如:

As discussed in the comments, the solution is to store iterators instead of copies, e.g.:

list<list<e>::iterator> aux;
aux.insert(aux.begin(), tree[0].begin(), tree[0].end());
while (!aux.empty())
{
  e& now = *(aux.front());
  aux.pop_front();
  now.v++;
  aux.insert(aux.begin(), tree[now.v].begin(), tree[now.v].end());    
}

仅当您可以确保没有任何东西会使存储的迭代器无效(例如，对 tree 进行的某些操作可以这样做)时，此方法才有效.

This works only if you can guarantee that nothing will invalidate the stored iterators, such as certain operations on tree could do.

如 n所指出.代词" m.，迭代器可以被视为通用指针"，因此很多问题使得常规指针也适用于迭代器.

As pointed out by n. 'pronouns' m., iterators can be considered as "generalized pointers", so many problems that regular pointers have also apply to iterators.

另一种(稍微安全些)的方法是将 std :: shared_ptr s存储在 tree 的内部列表中-然后，您可以简单地存储另一个 std::shared_ptr 到 aux 中的同一对象，以确保在仍然引用该对象时不会意外删除该对象

Another (slightly safer) approach would be to store std::shared_ptrs in the inner list of tree - then you can simply store another std::shared_ptr to the same object in aux which makes sure that the object cannot be accidentally deleted while it is still being referenced

这篇关于C ++将对象保存在列表中以供以后重用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！