StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>What about:</p> <pre><code>struct IsNeighbour : public std::binary_function<int,int,bool> { IsNeighbour(int dist) : distance(dist) {} bool operator()(int a, int b) const { return abs(a-b) <= 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); } </code></pre> <p>This should have O(n). It searches for the first pair of neighbours (which are at maximum <code>some_distance</code> away from each other) and removes the first of this pair. This is repeated (starting from the found item and not from the beginning, of course) until no pairs are found anymore.</p> <p><strong>EDIT:</strong> Oh sorry, you said <strong>any other</strong> and not just its next element. In this case the above algorithm only works for a sorted list. So you should sort it first, if neccessary.</p> <p>You can also use <code>std::unique</code> instead of this custom loop above:</p> <pre><code>lst.erase(std::unique(lst.begin(), lst.end(), IsNeighbour(some_distance), lst.end()); </code></pre> <p>but this removes the second item of each equal pair, and not the first, so you may have to reverse the iteration direction if this matters.</p> <p>For 2D points instead of ints (1D points) it is not that easy, as you cannot just sort them by their euclidean distance. So if your real problem is to do it on 2D points, you might rephrase the question to point that out more clearly and remove the oversimplified int example.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload