Удалить алгоритм дубликатов

Question

Я пытаюсь написать алгоритм для удаления дубликатов из vector<struct xxxx*>.

struct xxxx{ 
    int value;  // This is just to make you understand 
    xxxx* one; 
    xxxx* two; 
} 

Как вы видите мою структуру, это похоже на дерево, но указатели не в порядке. Указатели могут указывать на любой (фактически не какой-либо другой) из остальных. И вектор не содержит структур, а указателей, поэтому я не мог использовать std-алгоритмы, чтобы помочь мне.

Я пытаюсь удалить дубликаты с точно таким же значением и теми же двумя указателями, но в то же время, если у меня есть два подобных Структуры (Скажем A и B) и C.one или C.two точек на B. Затем мне нужно изменить его на A и наоборот.

Иными словами: if A == B затем удалить B и изменить C.one в пункт A.

Я думаю, что могу написать грубую силу, поэтому, если нет лучшего алгоритма, я напишу его сам.

Answer 1

Вчера я попытался объяснить разумный подход к очень похожей проблеме для коллеги, который использовал решение N квадрата для решения N log N.

Сначала создайте вспомогательную структуру, которая в основном представляет собой оболочку вокруг xxxx * с оператором сравнения, проверяющим содержимое (не значение указателя) и, возможно, с некоторыми другими функциями полезности. Эта структура-оболочка строго не нужна против использования xxxx *, но из-за опыта я считаю, что это делает задачу более чистой.

Создайте std :: set из тех вспомогательных структур, в которые вы будете вставлять только уникальные элементы и, вероятно, другой набор, в который вы будете вставлять рекурсивно неразрешенные элементы.

Петля через оригинальный вектор и в каждой позиции рекурсия через своих детей. Если вы нажмете дочерний элемент уже в уникальном наборе, это будет окончательное значение для этого дочернего указателя. Если вы нажмете дочерний элемент, который соответствует уникальному элементу, который не совпадает с тем, который он соответствует, тогда исправьте указатель, который вас там нашел. Если есть также возможность нулевых указателей, которые должны находиться ниже рекурсии, и если петли возможны, вам необходимо их обнаружить (с этим рекурсивно неразрешенным набором) и некоторое решение о том, что делать с циклом. В какой-то момент вы попадаете в разрешенные уникальные элементы и добавляете это к уникальному набору.

Производительность и, возможно, даже обоснованность идеи зависят от глубины и сложности петель и от того, что вы хотите делать с циклами. Есть некоторые беспорядочные случаи, когда петля будет отображаться на другой цикл, но обнаружение может быть очень сложным. Если ваша фаза «как дерево» означала «никакие петли», тогда рекурсия была бы чистой и эффективной без дополнительной сложности явного управления рекурсивно неразрешенными элементами.

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

Редактировать: Чтобы понять, как мало узлов посещений там, несмотря на вложение рекурсии в последовательный цикл, подумайте с точки зрения указателей. Мы следим за каждым указателем не более одного раза (некоторые дубликаты предварительно обнаружены без следования их указателям).Для N узлов существует N указателей верхнего уровня (если я правильно понял ваше описание) и значительно меньше, чем 2N внутренних указателей (чем больше похожее на дерево, тем ближе к N-1 внутренним указателям, а не 2N) , Таким образом, каждый узел посещается в среднем менее 3 раз, а меньшинство этих посещений требует как предварительного поиска, так и поиска после рекурсии, и каждый поиск - это log U, где U - количество уникальных элементов, найденных до этой точки. Таким образом, мы можем тривиально увидеть оценку 6 N log N.