C ++ Standard Library allows you to delete one of a pair of items in a list that meets the criteria

Question

Imagine you have a std::list with a set of values ​​in it. For demonstration, we will just say this std::list<int> , but in my case they are actually 2D points. Anyway, I want to remove one of a pair of int (or points) that satisfy some distance criterion. My question is how to approach this as an iteration that no longer does O (N ^ 2) operations.

Example

The source is an int list containing:

{ 16, 2, 5, 10, 15, 1, 20 }

If I gave a criterion for distance 1 (i.e., no element in the list should be inside 1 any other), I would like to create the following output:

{ 16, 2, 5, 10, 20 } if I went forward or

{ 20, 1, 15, 10, 5 } if I repeated back

I feel that there must be some awesome way to do this, but I got stuck in this double iterator loop and tried to erase items during iteration through the list.

Answer 1

Make a map of the "regions", basically std::map<coordinates/len, std::vector<point>> . Add each point to this region and each of the 8 neighboring O(N*logN) regions O(N*logN) . Run the "nieve" algorithm in each of these smaller lists (technically O(N^2) , if theres maximum density, then it becomes O(N*density) ). Finally: in your source list, iterate through each point , and if it was removed from any of the 8 mini-lists, it was inserted, remove it from the list. O(n)

Without density restrictions, it is O(N^2) and slow. But it gets faster and faster as the dots are more common. If the points are somewhat evenly distributed on a known boundary, you can switch to a two-dimensional array, which will greatly accelerate it, and if there is a constant density limit, this technically does this O(n) algorithm.

So you sort the list of two variables. The grid / map / 2dvector element.

[EDIT] You mentioned that you also have problems with the "nieve" method, so here's what:

 template<class iterator, class criterion> iterator RemoveCriterion(iterator begin, iterator end, criterion criter) { iterator actend = end; for(iterator L=begin; L != actend; ++L) { iterator R(L); for(++R; R != actend;) { if (criter(*L, *R) { iterator N(R); std::rotate(R, ++N, actend); --actend; } else ++R; } } return actend; } 

This should work with linked lists, vectors and similar containers and work in reverse order. Unfortunately, this is a bit slow due to the fact that linked list properties are not taken into account. It is possible to make much faster versions that work only with linked lists in a certain direction. Note that the return value is important, like other mutation algorithms. It can modify the contents of the container, not the container itself, so you will need to delete all the elements after the return value when it ends.

Answer 2

Cubbi had a better answer, although for some reason he deleted it:

It looks like this is a sorted list, in which case std :: unique will perform the task of removing the second element of each pair:

 #include <list> #include <algorithm> #include <iostream> #include <iterator> int main() { std::list<int> data = {1,2,5,10,15,16,20}; std::unique_copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "), [](int n, int m){return abs(nm)<=1;}); std::cout << '\n'; } 

demo: https://ideone.com/OnGxk

This trivially extends to other types - either by changing the int to something else, or by defining a pattern:

 template<typename T> void remove_close(std::list<T> &data, int distance) { std::unique_copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "), [distance](T n, T m){return abs(nm)<=distance;}); return data; } 

Which will work for any type that defines operator - and abs so that you can find the distance between two objects.

Answer 3

As a mathematician, I am sure that there is no “surprising” way to approach this problem for an unsorted list. It seems to me that it is logically necessary to check the criterion for any one element in relation to all previous elements selected to determine whether the insert is viable or not. There can be several ways to optimize this, depending on the size of the list and the criteria.

Perhaps you could support bit-based criteria. For instance. Assume that abs (nm) <1) is a criterion. Suppose the first item is size 5. This is transferred to the new list. So, flip the beatset [5] to 1. Then, when you come across an element of size 6, let's say you only need to check

 !( bitset[5] | bitset[6] | bitset[7]) 

This ensures that no items are within the 1st level of the resulting list. However, this idea is difficult to extend to more complex (non-discrete) criteria.

Answer 4

What about:

 struct IsNeighbour : public std::binary_function<int,int,bool> { IsNeighbour(int dist) : distance(dist) {} bool operator()(int a, int b) const { return abs(ab) <= distance; } int distance; }; std::list<int>::iterator iter = lst.begin(); while(iter != lst.end()) { iter = std::adjacent_find(iter, lst.end(), IsNeighbour(some_distance))); if(iter != lst.end()) iter = lst.erase(iter); } 

This should have O (n). It searches for the first pair of neighbors (maximum some_distance from each other) and removes the first of this pair. This is repeated (starting from the element found, and not from the very beginning, of course) until the pairs are found more.

EDIT: Sorry, you said any other , not just its next element. In this case, the specified algorithm only works for a sorted list. Therefore, you must first sort it if necessary.

You can also use std::unique instead of this custom loop above:

 lst.erase(std::unique(lst.begin(), lst.end(), IsNeighbour(some_distance), lst.end()); 

but this removes the second element of each same pair, not the first, so you may need to change the direction of the iteration if that matters.

For two-dimensional points, instead of ints (1D points), this is not so simple since you cannot just sort them by their Euclidean distance. Therefore, if your real problem is to do this at 2D points, you can rephrase the question to clarify this and remove the simplified example.

Answer 5

I think this will work if you don't mind making copies of the data, but if it's just a pair of integers / float, this should be pretty cheap. You do n ^ 2 comparisons, but you use std :: algorithm and you can declare an input vector const.

 //calculates the distance between two points and returns true if said distance is //under its threshold bool isTooClose(const Point& lhs, const Point& rhs, int threshold = 1); vector<Point>& vec; //the original vector, passed in vector<Point>& out; //the output vector, returned however you like for(b = vec.begin(), e = vec.end(); b != e; b++) { Point& candidate = *b; if(find_if(out.begin(), out.end(), bind1st(isTooClose, candidate)) == out.end()) {//we didn't find anyone too close to us in the output vector. Let add! out.push_back(candidate); } } 

Answer 6

std :: list <>. erase (remove_if (...)) using functors

http://en.wikipedia.org/wiki/Erase-remove_idiom

Update (added code):

 struct IsNeighbour : public std::unary_function<int,bool> { IsNeighbour(int dist) : m_distance(dist), m_old_value(0){} bool operator()(int a) { bool result = abs(a-m_old_value) <= m_distance; m_old_value = a; return result; } int m_distance; int m_old_value; }; main function... std::list<int> data = {1,2,5,10,15,16,20}; data.erase(std::remove_if(data.begin(), data.end(), IsNeighbour(1)), data.end());