Удаление "первого" объекта из набора

В определенных ситуациях мне нужно выселить самый старый элемент в Java Set. Набор реализован с использованием LinkedHashSet, что делает это простым: просто избавьтесь от первого элемента, возвращаемого заданным итератором:

Set<Foo> mySet = new LinkedHashSet<Foo>();
// do stuff...
if (mySet.size() >= MAX_SET_SIZE)
{
    Iterator<Foo> iter = mySet.iterator();
    iter.next();
    iter.remove();
}

Это уродливо: 3 строки, чтобы сделать что-то, что я мог бы сделать с 1 строкой, если бы я использовал SortedSet (по другим причинам SortedSet здесь не вариант):

if (/*stuff*/)
{
    mySet.remove(mySet.first());
}

Итак, есть более чистый способ сделать это, без:

изменение реализации Set или
запись статического метода утилиты?

Любые решения, использующие Guava, являются точными.

_{Я полностью понимаю, что наборы не имеют встроенного порядка. Я спрашиваю об удалении первой записи, определенной порядком итерации.}

Ответы

Ответ 1

LinkedHashSet - это оболочка для LinkedHashMap, которая поддерживает простую политику "удалить самую старую". Чтобы использовать его как набор, вы можете сделать

Set<String> set = Collections.newSetFromMap(new LinkedHashMap<String, Boolean>(){
    protected boolean removeEldestEntry(Map.Entry<String, Boolean> eldest) {
        return size() > MAX_ENTRIES;
    }
});

Ответ 2

if (!mySet.isEmpty())
  mySet.remove(mySet.iterator.next());

кажется, меньше 3 строк.

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

Ответ 3

Если вам действительно нужно сделать это в нескольких местах вашего кода, просто напишите статический метод.

Другие предлагаемые решения часто медленнее, поскольку они подразумевают вызов метода Set.remove(Object) вместо метода Iterator.remove().

@Nullable
public static <T> T removeFirst(Collection<? extends T> c) {
  Iterator<? extends T> it = c.iterator();
  if (!it.hasNext()) { return null; }
  T removed = it.next();
  it.remove();
  return removed;
}

Ответ 4

С guava:

if (!set.isEmpty() && set.size() >= MAX_SET_SIZE) {
    set.remove(Iterables.get(set, 0));
}

Я также предлагаю альтернативный подход. Да, он меняет реализацию, но не резко: расширяем LinkedHashSet и получаем это условие в методе add:

public LimitedLinkedHashSet<E> extends LinkedHashSet<E> {
    public void add(E element) {
         super.add(element);
         // your 5-line logic from above or my solution with guava
    }
}

Он все еще 5 строк, но он невидим для кода, который его использует. И поскольку на самом деле это специфическое поведение набора, логично иметь его внутри набора.

Ответ 5

Я думаю, что вы делаете это хорошо. Это то, что вы делаете достаточно часто, чтобы стоить найти более короткий путь? Вы могли бы сделать в основном то же самое с Guava следующим образом:

Iterables.removeIf(Iterables.limit(mySet, 1), Predicates.alwaysTrue());

Это добавляет небольшие накладные расходы на обертку набора и его итератор для ограничения, а затем вызов предиката alwaysTrue() один раз... не кажется мне особенно полезным для меня.

Изменить: Чтобы добавить то, что я сказал в комментарии в ответ, вы можете создать SetMultimap, который автоматически ограничивает количество значений, которые он может иметь для каждого ключа, например:

SetMultimap<K, V> multimap = Multimaps.newSetMultimap(map,
    new Supplier<Set<V>>() {
      public Set<V> get() {
        return Sets.newSetFromMap(new LinkedHashMap<V, Boolean>() {
          @Override protected boolean removeEldestEntry(Entry<K, V> eldestEntry) {
            return size() > MAX_SIZE;
          }
        });
      }
    });

Ответ 6

Быстрое и грязное однострочное решение: mySet.remove(mySet.toArray(new Foo[mySet.size()])[0]);)

Тем не менее, я все равно поеду для решения итератора, так как это будет более читаемым, а также быстрее.

Редактировать: я бы выбрал решение Майка Самуэля.:)