Обновление сохраненных индексов после удаления элемента из std :: vector
Предположим, что у меня есть вектор точек:
vector<int> points;
Треугольники хранят индексы точек, из которых они сделаны:
struct Triangle {
int p0, p1, p2;
};
Triangle tri0;
tri0.p0 = 3;
tri0.p1 = 6;
tri0.p2 = 7;
Triangle tri1;
tri1.p0 = 4;
tri1.p1 = 6;
tri1.p2 = 7;
Теперь я решаю стереть point[3], Однако, если я сотру point[3]индексы точек после индекса 3 сместятся назад, поэтому мне нужно уведомить все треугольники о том, что индексы, которые они хранят, могут быть изменены. Что может быть правдоподобным способом уведомления треугольников?
Решение
Мне кажется, что наиболее вероятный путь не удалить вершины. Потому что если вы действительно удалите их, то вам придется сдвинуть все вершины вправо (В / 2 элементов в среднем), то вам нужно пройти через все треугольники (T проверяет всегда).
Вместо этого вы можете пометить вершины как мертвых. Просто поместите плохое значение в массив точек (в вашем примере -1 в порядке). Установка отметки занимает только O (1) на каждом удалении. Время от времени вы можете физически удалять мертвые вершины. Вы можете сделать это за два полных прохода (один над вершинами, один над треугольниками) и сжать вашу сетку за линейное время O (V + T).
Чтобы упростить использование, я предлагаю создать класс для ваших мешей. В объекте сетки поддерживайте количество мертвых записей прозрачно для пользователя класса. Когда часть мертвых записей становится значительной (например, более половины) после удаления, вызовите удаление мертвых вершин. Вы также можете создать методы перечисления треугольников, которые будут перебирать только живые треугольники (просто для удобства).
Такой подход обеспечивает O (1) амортизированное время на одно удаление, если количество времени, потраченное на сжатие, не превышает число обращений, умноженное на постоянное. При условии T <= с V в любой момент (для некоторой постоянной с), это правда. В самом деле, очень маловероятно, что сетка с числом треугольников будет намного больше, чем количество вершин, так что все в порядке.
Совсем другое решение — использовать связанные списки вместо массивов для хранения вершин и треугольников (с указателями друг на друга). В этом случае вы можете удалить вершину v в О (Зв) время, где Sv это число треугольников, к которым он принадлежит. Но низкоуровневая производительность такой структуры данных может быть низкой.
РЕДАКТИРОВАТЬ: Другая проблема пришла мне в голову. Удаление мертвых вершин называется прозрачным для пользователя, но в данный момент пользователь может оказаться в середине нумерации треугольников или вершин. Очевидно, что эта ситуация вызовет большие проблемы.
Чтобы избежать опасности, добавьте lock/unlock методы для вашей сетки. Затем вы можете убедиться, что, пока меш заблокирован, его вершины гарантированно будут оставаться на месте по индексу. В таком случае вы можете безопасно выполнять такие операции, как, например, фильтрация вершин.
Другие решения
Других решений пока нет …