c++ - 存储和重用 vector 迭代器值是否安全？

Question

我正在使用图形构建 C++ 程序。我正在使用类 vector 。问题是当我将类的新对象插入 vector 时，迭代器的先前值开始指向一些垃圾值。我的类(class)如下:

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

存储和重用迭代器值在多大程度上是安全的？

下面的函数工作如下:

首先会找到每个节点的父节点和子节点，并分别存储迭代结果。

其次，它是图的子节点(没有进一步子节点的节点)。

当它试图向图中插入子节点时，其他节点的迭代变成垃圾。

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.
}
}

Answer 1

存储和重用迭代器值在多大程度上是安全的？

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

您可以安全地假设最终新大小将大于初始容量。
因此您没有使用正确的数据结构。

您的设计接近adjacent lists .所以使用 std::list，doesn't invalidate iterators or references upon insertion .

顺便说一句 boost has an implementation对于相邻列表..