Какой контейнер следует использовать для набора элементов, которые постоянно добавляются и удаляются

Question

Я хотел бы знать, какой контейнер STL будет наиболее подходящим для «постоянно» меняющегося набора элементов с точки зрения производительности.Элементы представляют объекты в данном пространстве просмотра, и, поскольку вид меняется, а объекты перемещаются внутрь и из поля зрения, коллекция объектов должна обновляться.Каждый раз, когда представление обновляется, я получаю std :: vector объектов, которые должны быть в сцене, отсортированные по UID (давайте назовем этот List A).Я хочу выполнить проверку, чтобы:

• удалял объекты, которые больше не видны из текущего списка вещей, фактически находящихся в сцене (вызов этого списка B), на основе списка A

• добавляет новые объекты, которые теперь видны в списке B, снова на основе списка A

Вероятно, верхний предел числа составляет от двух до четырех тысяч объектовобъектов, когда-либо виденных.Я не могу использовать растровый вектор, поскольку UID объекта исчисляется миллиардами.Я думал, что мог бы использовать std :: map для Списка B. Моя предлагаемая стратегия обновления Списка B:

• Для каждого UID 'i' в Списке B найдите UID 'i'в списке A (используя std :: lower_bound).Если UID не существует в списке A, удалите его из списка B.

• Для каждого UID 'i' в списке A найдите UID 'i' в списке B (используя std:: Карта :: lower_bound).Если UID не существует в списке B, добавьте его.

Поэтому я хотел бы получить несколько советов, особенно если я использую правильный тип контейнера.Я не думал, что std :: vector будет хорошим выбором для списка B, потому что вставки / удаления будут дорогостоящими, и мне придется явно сортировать, если я хочу использовать бинарный поиск по std :: find.Кроме этого, я не знаю много о других типах контейнеров и о том, являются ли они более подходящими.

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

Answer 1

Похоже, ваши проблемы с вызовами для операций над множествами. Удаление объектов со сцены, которых нет в ListA, является заданной разницей. Добавление объектов из ListA, которых нет в сцене, является операцией объединения наборов. Операции над множествами обычно являются кандидатами на хеширование, когда данные не организованы надлежащим образом для растрового изображения.

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

# left operand is list, right is hash:

set_diff (list x, hash y):
   val ret = make_hash()
   for i in x:
      if not y[i]
          ret[i] = i
   return ret

# vice versa

set_diff (hash x, list y)
    val ret = copy_hash(x)
    for i in y:
        if ret[i]
            delete ret[i]
    return ret             

Кстати, зачем искать с помощью lower_bound; удостоверение личности не уникально или что?

Answer 2

Пробовал повысить неупорядоченный набор для обоих?

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

Answer 3

Что вам нужно решить, это Контейнеры STL , и прокрутите вниз до сложности операций. Ваш выбор между std::list, std::deque и std::vector, причем последний самый медленный из них, а первый самый быстрый. Теперь, какой из них обеспечивает все ваши требования? В идеале вы должны использовать std::list, потому что вставки - это O (n), где std::deque - это O (n + x), где x - количество элементов до точки вставки. Тем не менее, я думаю, вам понадобится std::deque::at() для извлечения элементов. Я думаю, что вам нужно это в обоих списках, поэтому вы должны использовать std::deque.