CODEWITHSUNDEEP
c++vectordata-structuresstliterator
user3022426
user3022426

Reputation: 49

Safe to store and reuse vector iterator values?

I am building a C++ program using graph. I am using vector of class. Problem is when I am inserting new object of class into vector previous values of iterator started pointing to some garbage values. My class is as follow: 

class LinkedList
{
    public:
    int node;
    list <children> child;
    vector <vector <LinkedList>::iterator > pl; // it store the iteration values of parent of node
    vector <vector <LinkedList>::iterator > cl; // it store the iteration values of childof node
};
class children
{
    public:
    int dest;
    string label;
};

How much it is safe to store and reuse the iterator values?

Below function works as follows:

First it will find the parent and child of every node and store the iteration result respectively.

Secondly it will children of a graph (nodes with no furthur child nodes).

When it tries to insert child nodes into the graph, the iteration of other nodes become garbage.

void parentchildList(vector <LinkedList> &graph)//, vector <transclosure> &tc)
{
vector <int> childNode;

for(vector<LinkedList>::iterator ii = graph.begin(); ii != graph.end(); ii++)
{   

    for(vector<LinkedList>::iterator it = graph.begin(); it != graph.end(); it++)
    {
        for(list<children>::iterator li = it -> child.begin(); li != it -> child.end(); li++)
        {
            if(ii -> parent == li -> dest)
            {
                ii -> pl.push_back(it);
                it -> cl.push_back(ii);
            }
        }

    }
}


//Finding child nodes in a graph.
for(vector<LinkedList>::iterator ii = graph.begin(); ii != graph.end(); ii++)
{
    if(ii ->cl.size() != ii->child.size())          // finding child nodes and adding them to graph //linking child nodes 
    {
        bool flag = false;
        for(list<children>::iterator li = ii -> child.begin(); li != ii -> child.end(); li++)
        {
            flag = false;
            for(vector <vector <LinkedList>::iterator >::iterator itt = ii->cl.begin(); itt != ii->cl.end(); itt++)
            {   
                if((*itt)->parent == li->dest)
                    flag = true;
            }
            if(!flag)
                childNode.push_back(li->dest);
        }
    }
}


sort(childNode.begin(), childNode.end());
childNode.erase(unique(childNode.begin(), childNode.end()),childNode.end());

cout<<"Child Nodes are ";
for(vector<int>::iterator it=childNode.begin(); it!= childNode.end(); it++)
    cout<<*it<<" ";
cout<<endl;

for(vector<int>::iterator it=childNode.begin(); it!= childNode.end(); it++)
{
    LinkedList obj;
    obj.parent = *it;
    graph.push_back(obj);

    // Error happens here when I tried to insert a new obj into graph, all vaues of pl and cl becomes garbage.
}
}

Upvotes: 0

Views: 2513

Answers (1)

UmNyobe
UmNyobe

Reputation: 22890

How much it is safe to store and reuse the iterator values?

std::vector::insert
Causes reallocation if the new size() is greater than the old capacity().
If the new size() is greater than capacity(), all iterators and references are invalidated.
Otherwise, only the iterators and references before the insertion point remain valid.
The past-the-end iterator is also invalidated.

vector reference

You can safely assume that eventually the new size is going to be greater than the initial capacity.
Thus you are not using the right data structure.

Your design is close to adjacent lists. So use std::list, which doesn't invalidate iterators or references upon insertion.

Btw boost has an implementation for adjacent lists..

Upvotes: 1

Related Questions