Подход стандартной библиотеки C ++ к удалению одного из пары элементов в списке, которые удовлетворяют критерию

Question

Представьте, что у вас есть std::list с набором значений в нем.Ради демонстрации мы скажем, что это просто std::list<int>, но в моем случае это фактически 2D точки.В любом случае, я хочу удалить одну из пары int s (или точек), которые удовлетворяют некоторому критерию расстояния.Мой вопрос заключается в том, как подходить к этому как к итерации, которая выполняет не более O (N ^ 2) операций.

Пример

Источник представляет собой список int с, содержащие:

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

Если бы я дал этому критерию расстояния 1 (т.е. ни один элемент в списке не должен быть в пределах 1 любого другого), яЯ хотел бы получить следующий вывод:

{ 16, 2, 5, 10, 20 } если я итерировал вперед или

{ 20, 1, 15, 10, 5 } если я итерировал назад

Я чувствуючто должен быть какой-то замечательный способ сделать это, но я застрял с этим двойным циклом итераторов и пытаюсь стереть элементы, перебирая список.

Answer 1

Составьте карту «регионов», в основном, std::map<coordinates/len, std::vector<point>>.Добавьте каждую точку в ее регион, и каждый из 8 соседних регионов O(N*logN).Запустите алгоритм «nieve» для каждого из этих меньших списков (технически O(N^2), если нет максимальной плотности, тогда он становится O(N*density)).Наконец: в вашем исходном списке выполните итерацию по каждому point, и, если он был удален из любого из 8 мини-списков, в которые он был добавлен, удалите его из списка.O(n)

Без ограничения по плотности, это O(N^2), и медленно.Но это становится все быстрее и быстрее, чем больше разбросаны точки.Если точки в некоторой степени равномерно распределены на известной границе, вы можете переключиться на двумерный массив, что сделает это значительно более быстрым, а если есть постоянный предел плотности, то технически делает это алгоритмом O(N).

Таким образом, вы сортируете список двух переменных.Сетка / карта / 2dvector.

[EDIT] Вы упомянули, что у вас тоже были проблемы с методом "nieve", так что вот что:

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;
}

Это должно работать в связанных списках, векторы и аналогичные контейнеры, и работает в обратном порядке.К сожалению, это довольно медленно из-за отсутствия учета свойств связанных списков.Можно сделать намного более быстрые версии, которые работают только со связанными списками в определенном направлении.Обратите внимание, что возвращаемое значение важно, как и в других алгоритмах мутации.Он может изменять только содержимое контейнера, но не сам контейнер, поэтому вам придется стирать все элементы после возвращаемого значения после его завершения.

Answer 2

Как математик, я почти уверен, что не существует «удивительного» подхода к решению этой проблемы для несортированного списка. Мне кажется, что логически необходимо проверить критерий для любого одного элемента по всем предыдущим элементам, выбранным, чтобы определить, является ли вставка жизнеспособной или нет. Существует несколько способов оптимизировать это в зависимости от размера списка и критерия.

Возможно, вы могли бы поддерживать набор битов на основе критерия. Например. Предположим, что abs (n-m) <1) является критерием. Предположим, что первый элемент имеет размер 5. Это перенесено в новый список. Так что переверните bitset [5] в 1. Затем, когда вы встретите элемент размером 6, скажем, вам нужно только проверить </p>

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

Это будет гарантировать, что ни один элемент не будет в пределах величины 1 от результирующего списка. Однако эту идею может быть сложно распространить на более сложные (недискретные) критерии.

Answer 3

У Кубби был лучший ответ, хотя он почему-то удалил его:

Звучит так, будто это отсортированный список, и в этом случае std :: unique выполнит работу по удалению второго элемента каждой пары:

#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';
}

демо: https://ideone.com/OnGxk

Это тривиально распространяется на другие типы - либо путем изменения int на что-то другое, либо путем определения шаблона:

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;
}

Который будет работать для любого типа, который определяет operator - и abs, чтобы позволить найти расстояние между двумя объектами.

Answer 4

Я думаю, что это будет работать, если вы не против скопировать данные, но если это просто пара целых чисел / чисел с плавающей запятой, это должно быть довольно дешево.Вы делаете n ^ 2 сравнений, но используете std :: алгоритма и можете объявить входной вектор 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's add!
        out.push_back(candidate);
    }
}

Answer 5

А как же:

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);
}

Это должно иметь O (n). Он ищет первую пару соседей (которые находятся на максимальном расстоянии some_distance друг от друга) и удаляет первую из этой пары. Это повторяется (начиная с найденного предмета, а не с самого начала, конечно), пока пары больше не будут найдены.

РЕДАКТИРОВАТЬ: Извините, вы сказали любой другой , а не только его следующий элемент. В этом случае приведенный выше алгоритм работает только для отсортированного списка. Поэтому, если нужно, сначала нужно отсортировать.

Вы также можете использовать std::unique вместо указанного выше пользовательского цикла:

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

но при этом удаляется второй элемент каждой равной пары, а не первый, поэтому вам, возможно, придется изменить направление итерации, если это имеет значение.

Для 2D-точек вместо целых (1D-точек) это не так просто, так как вы не можете просто отсортировать их по евклидову расстоянию. Поэтому, если ваша настоящая проблема заключается в том, чтобы сделать это на двухмерных точках, вы можете перефразировать вопрос, чтобы указать на это более четко и удалить пример упрощенного int.

Answer 6

std :: list <>. Erase (remove_if (...)) с использованием функторов

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

Обновление (добавлен код):

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());