Nested loop of same vector - Erase–remove idiom

Question

I want to iterate all the elements of a vector and for each element to check a condition for all other elements of the vector.

The logic:

Precondition: q is not in vector for every x,y in vector if d(x, y) <= d(x, q) && d(x, q) <= d(y, q) then eliminate x, y

An approach:

for(vector<Point_d>::iterator it = candidates.begin(); it != candidates.end(); ++it){ for (vector<Point_d>::iterator it2 = candidates.begin(); it2 != candidates.end(); ++it2) { if(dist.transformed_distance(*it, *it2) <= dist.transformed_distance(*it, q) && dist.transformed_distance(*it, q) <= dist.transformed_distance(*it2, q)){ /* Remove x,y without invalidate the iterators */ } } }

I know that if I remove an element inside the loop the iterators will be invalidated. Is there any way to do this with Erase-Remove Idiom or is there any other way to do this? I have searched a lot and I have find various piece that I can combine to make it work, ie by remove the iterators from for-loops and use erase and remove_if, but I can't figure it out and also because I am new to c++ and STL I would like to hear better approaches.

EDIT

Also if is possible I don't want to do the condition for the same elements ie d(x, x) <= d(x, q).

naïve solution : check first if it != it2; and secondly, store somewhere in list for example elements that should be remove, and after iterate over vector, delete it, instead of deleting it directly in iteration — Garf365
– Garf365, Commented Jun 15, 2016 at 8:42
@Garf365 Why a list and not a vector? Is there a function to delete the elements that are same between a vector and a list or another vector? Thanks for the answer. — Laxmana
– Laxmana, Commented Jun 15, 2016 at 8:46
Check vector::erase, it returns a iterator, so you can safely remove the iterator and continue with the returned iterator. — Mine
– Mine, Commented Jun 15, 2016 at 8:47
@Henrik You mean for elimination ? Something like that vec.erase(vec.begin() + 1) — Laxmana
– Laxmana, Commented Jun 15, 2016 at 8:48

Smeeheey · Accepted Answer · 2016-06-15 10:31:56Z

Your job could be easier if you use indices instead, as per below code. I have a slightly modified live demo which shows this works. (I replaced the dist function with something that returns just abs(x-y) for integers).

for(size_t i=0; i<candidates.size();){ bool deleted = false; for (size_t j = 0; j < candidates.size();) { if(i==j) { ++j; continue; } if(dist.transformed_distance(candidates[i], candidates[j]) <= dist.transformed_distance(candidates[i], q) && dist.transformed_distance(candidates[i], q) <= dist.transformed_distance(candidates[j], q)){ bool dec_i = false; if(i < j) --j; else dec_i = true; candidates.erase(std::next(candidates.begin(), i)); candidates.erase(std::next(candidates.begin(), j)); if(dec_i) --i; deleted = true; break; } else ++j; } if(!deleted) ++i; }

Note that you can have an alternative implementation that marks the elements to be deleted in a first pass, and then deletes them. In this case behaviour is different: as elements are not deleted they are still considered for later pair matching. Thus a single element can be paired to more than one other one for deletion, and in the end potentially more elements are removed than with the above. This time the cost is O(n^2) rather than O(n^3). Live demo here:

std::vector<int> deleteIndices; deleteIndices.reserve(candidates.size()); for(size_t i=0; i<candidates.size(); ++i){ for (size_t j = 0; j < candidates.size(); ++j) { if(i==j) { continue; } if(dist.transformed_distance(candidates[i], candidates[j]) <= dist.transformed_distance(candidates[i], q) && dist.transformed_distance(candidates[i], q) <= dist.transformed_distance(candidates[j], q)){ deleteIndices.push_back(i); deleteIndices.push_back(j); } } } std::sort(deleteIndices.begin(), deleteIndices.end()); auto unique_end = std::unique(deleteIndices.begin(), deleteIndices.end()); //I'm using this complicated thing as the template param just because I don't know what your element type is std::vector<std::remove_reference_t<decltype(candidates[0])>> output; output.reserve(candidates.size() - deleteIndices.size()); auto it = deleteIndices.begin(); auto i = 0; std::copy_if(candidates.begin(), candidates.end(), std::back_inserter(output), [&it,&i,unique_end](int elem) { if(it==unique_end) { ++i; return true; } if(i == *it) { ++i; ++it; return false; } ++i; return true; });

erase(iter) is avg O(N/2) so this algorithm is potentially O(n^3)
Can be done in O(n^2) ? Linear is possible? d(x,y) = d(y,x) so can we get away with some elements?
It can be done in O(n^2), just not with the pseudo-algorithm you presented. You could mark the elements to be deleted instead of deleting them, and then copy the non-delete-marked elements into a second output vector in a separate pass.
See above for alternative implementation, that first creates a list of all pairs eligible for deletion before deleting. Note the behaviour is different, and performance is now O(n^2)

Leon · Accepted Answer · 2016-06-15 11:32:49Z

The conceptual algorithm that you described can be interpreted in two different ways:

Identify all pairs of elements {x, y} in the collection that satisfy some condition pred(x, y). After all such pairs have been identified, remove all elements participating in them.
The exact imperative pseudocode version that you presented. Elements are removed as soon as it becomes clear that they should be removed.

The difference of 2. from 1. is that after you remove element x as soon as you detect that it satisfies your predicate when paired with element y, you eliminate the chance for that element to form a satisfying pair with another element z, and it may turn out that no other element will form such a satisfying pair with z.

The solution for the 1st interpretation follows:

#include <iostream> #include <vector> #include <algorithm> // Finds in the container 'c' pairs of elements {x, y} such that // pred(x, y) == true // and removes any such elements. // The remaining elements may be reordered. // pred is assumed to be commutative, i.e. // pred(x, y) == pred(y, x) template<class C, class Pred> void remove_element_pairs(C& c, Pred pred) { typedef typename C::iterator It; typedef typename C::value_type X; It e = c.end(); for ( It it = c.begin(); it != e; ) { const X& a = *it; const auto boundPred = [&pred, a](const X& x) -> bool { pred(a, x); }; if ( c.end() == find_if(std::next(it), c.end(), boundPred) ) ++it; else std::swap(*it, *--e); } c.erase(e, c.end()); } int main() { std::vector<int> v{1, 2, 7, 0, 0, 4, 4, 5}; remove_element_pairs(v, [](int a, int b) -> bool { return a + b == 8; }); for(int x : v) std::cout << x << " "; return 0; }

You are right. I have to think it a bit because is a part of a bigger problem , an approximate algorithm(from a paper) to find the reversed nearest neighbor of a query point, and I want to see if the 2. affects it. That's why I delay. As I explained the problem the 1. is the case but you made me see something I didn't notice.
Ok. It is the first case. Thanks a lot for pointing this critical difference. Because I ask a different question and realized it after your clever notice I have to accept the answer by Smeeheey. So if you don't mind telling, how you would approach the first case?
@Laxmana Can I assume that pred(x, y) is commutative, i.e pred(x,y) == pred(y,x)?
@Laxmana I am working on the solution. Meanwhile, why don't you post another question?

Richard Hodges · Accepted Answer · 2016-06-15 10:39:20Z

I really don't think you can get it better than O(<=N^2)

#include <vector> #include <algorithm> #include <iostream> #include <cmath> #include <iterator> struct point_d { double x, y; }; std::ostream& operator<<(std::ostream& os, const point_d& p) { return os << "(" << p.x << ", " << p.y << ")"; } double distance(const point_d& l, const point_d& r) { return std::sqrt(std::pow(r.x-l.x, 2) + std::pow(r.y-l.y,2)); } using d_array = std::vector<point_d>; //for every x,y in vector if d(x, y) <= d(x, q) && d(x, q) <= d(y, q) then eliminate x, y. q is not in vector. d_array remove_q(const d_array& vec, point_d q) { d_array result; std::vector<char> dropped(vec.size(), 0); // note! avoid vector<bool> result.reserve(vec.size()); auto is_dropped = [&](auto& p) { return dropped[std::distance(vec.data(), std::addressof(p))]; }; auto drop = [&](auto& p) { dropped[std::distance(vec.data(), std::addressof(p))] = 1; }; auto should_drop = [&](auto& x) { for (auto& y : vec) { if (is_dropped(y)) return true; if (std::addressof(x) != std::addressof(y)) { if (distance(x, y) <= distance(x, q) and distance(x, q) <= distance(y, q)) { return true; } } } return false; }; for (auto& x : vec) { if (not should_drop(x)) result.push_back(x); else drop(x); } return result; } int main() { d_array v = { point_d{ 0, 0}, point_d{ 1, 1}, point_d{ 0.5, 0.5 }, point_d{ 0.4, 0.4 }, point_d{ 0.25, 0.25 } }; auto v2 = remove_q(v, {0.45, 0.45}); std::copy(v2.begin(), v2.end(), std::ostream_iterator<point_d>(std::cout, ", ")); std::cout << std::endl; }

Collectives™ on Stack Overflow

Nested loop of same vector - Erase–remove idiom

3 Answers 3

4 Comments

8 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

8 Comments

Comments

Related