C++ Standard Library approach to removing one of a pair of items in a list that satisfy a criterion

Question

Imagine you have an std::list with a set of values in it. For demonstration's sake, we'll say it's just std::list<int>, but in my case they're actually 2D points. Anyway, I want to remove one of a pair of ints (or points) which satisfy some sort of distance criterion. My question is how to approach this as an iteration that doesn't do more than O(N^2) operations.

Example

Source is a list of ints containing:

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

If I gave this a distance criterion of 1 (i.e. no item in the list should be within 1 of any other), I'd like to produce the following output:

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

{ 20, 1, 15, 10, 5 } if I iterated backward

I feel that there must be some awesome way to do this, but I'm stuck with this double loop of iterators and trying to erase items while iterating through the list.

Answer 1

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

With no limit on density, this is O(N^2), and slow. But this gets faster and faster the more spread out the points are. If the points are somewhat evenly distributed in a known boundary, you can switch to a two dimensional array, making this significantly faster, and if there's a constant limit to the density, that technically makes this a O(N) algorithm.

That is how you sort a list of two variables by the way. The grid/map/2dvector thing.

[EDIT] You mentioned you were having trouble with the "nieve" method too, so here's that:

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 on linked lists, vectors, and similar containers, and works in reverse. Unfortunately, it's kinda slow due to not taking into account the properties of linked lists. It's possible to make much faster versions that only work on linked lists in a specific direction. Note that the return value is important, like with the other mutating algorithms. It can only alter contents of the container, not the container itself, so you'll have to erase all elements after the return value when it finishes.

Answer 2

Cubbi had the best answer, though he deleted it for some reason:

Sounds like it's a sorted list, in which case std::unique will do the job 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(n-m)<=1;});
    std::cout << '\n';
}

demo: https://ideone.com/OnGxk

That trivially extends to other types -- either by changing int to something else, or by defining a template:

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(n-m)<=distance;});
    return data;
}

Which will work for any type that defines operator - and abs to allow finding a distance between two objects.

Answer 3

As a mathematician I am pretty sure there is no 'awesome' way to approaching this problem for an unsorted list. It seems to me that it is a logical necessity to check the criterion for any one element against all previous elements selected in order to determine whether insertion is viable or not. There may be a number of ways to optimize this, depending on the size of the list and the criterion.

Perhaps you could maintain a bitset based on the criterion. E.g. suppose abs(n-m)<1) is the criterion. Suppose the first element is of size 5. This is carried over into the new list. So flip bitset[5] to 1. Then, when you encounter an element of size 6, say, you need only test

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

This would ensure no element is within magnitude 1 of the resulting list. This idea may be difficult to extend for more complicated(non discrete) criterions however.