CODEWITHSUNDEEP
c++data-structures
Silver Flash
Silver Flash

Reputation: 1071

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;

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

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.

Upvotes: 1

Views: 109

Answers (1)

UnholySheep
UnholySheep

Reputation: 4096

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

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

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.

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

Upvotes: 2

Related Questions