This is the way that I define my adjacency list:
vector<vector<int>> adj;
I want to iterate through the entire adjacency list and find if a certain value exists. If that value exists in the adjacency list, I want to delete it. I have tried 2 approaches:
Approach 1:
for(auto elem: adj){
for(auto ind: elem){
if(elem[ind]==num){
elem.erase(elem.begin()+ind);
}
}
}
Approach 2:
auto it=elem.find(num);
if (it!=elem.end())
elem.erase(it);
The second approach throws me an error of
no member named 'find' in 'std::vector<int, std::allocator >'
Can someone tell me why the approaches I have tried do not work, and what I can do to solve this problem? Thanks
This: auto it=elem.find(num); doesn't work because std::vector doesn't have a member function named find.
To find an item in a vector, you can use std::find instead:
auto it=std::find(elem.begin(), elem.end(), num);
if (it!=elem.end())
elem.erase(it);
Two points: if the elements in the adjacency list aren't in any particular order, you can probably speed up this operation by swapping the element to the end of the vector, then erasing it from there.
On the other hand, if the elements are in some known order, you may be able to use std::lower_bound to find the element faster (logarithmic time rather than linear time).
Another possibility would be to use an std::set or std::unordered_set instead of an std::vector. If you're dealing with graphs that are extremely large and dense (so each node has a lot of adjacent nodes) this could make sense-for example, you can find and erase an element from a std::set in logarithmic time instead of linear time. The problem is that to achieve that, it's typically implemented as balanced tree, with each node individually allocated from the free store. So although its computational complexity is (quite a lot) lower, its time constant per operation is typically quite a bit higher.