Ведение списка элементов массива в определенном состоянии

Question

У меня длинный массив элементов. Это встроенная платформа, и каждый цикл мне нужно выполнить операцию со всеми элементами, для которых установлен флаг.

Только несколько элементов имеют установленный флаг одновременно. Из-за соображений производительности я не могу запустить весь массив.

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

Полагаю, это старая и "решенная" проблема, но мне не хватает словарного запаса, чтобы правильно ее описать. Каковы лучшие методы решения этой проблемы и как она называется?

Спасибо

Answer 1

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

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