从邻接表C中删除元素

Question

这是我定义邻接列表的方式：向量

我想遍历整个邻接列表，找出是否存在某个值。如果邻接列表中存在该值，我想将其删除。我尝试了2种方法：

方法1:

for(auto elem: adj){
        for(auto ind: elem){
            if(elem[ind]==num){
                elem.erase(elem.begin()+ind);
            }
        }
    }

方法2:

auto it=elem.find(num);
if (it!=elem.end())
    elem.erase(it);

第二种方法给了我一个错误

在 “std：：vector” 中没有名为 “查找” 的成员

有人能告诉我为什么我尝试的方法不起作用吗？我能做些什么来解决这个问题？谢谢。




Answer 1

匿名用户

autoit=elem.find（num）；不起作用，因为std::向量没有名为find的成员函数。

要查找矢量中的项目，可以改用std:：find：

auto it=std::find(elem.begin(), elem.end(), num);
if (it!=elem.end())
    elem.erase(it);

两点:如果邻接表中的元素没有任何特定的顺序，你可以通过交换元素到向量的末尾，然后从那里删除它来加速这个操作。

另一方面，如果元素以某种已知的顺序排列，您可以使用< code>std::lower_bound更快地找到元素(对数时间而不是线性时间)。

另一种可能是使用std:：set或std:；unordered_set来代替 。如果您处理的图形非常大且稠密（因此每个节点都有许多相邻节点），这可能有意义，例如，您可以在对数时间而不是线性时间从 std:：set中找到并删除元素。问题是，为了实现这一点，它通常被实现为平衡树，每个节点都是从空闲存储区单独分配的。因此，尽管它的计算复杂度较低（非常低），但每次操作的时间常数通常要高得多。