Как называется контейнер хранящий N лучших элементов?

#массивы #структуры #терминология #любой_язык

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

Есть ли у такого контейнера каноническое название (английский и русский термины) ?
    

Ответы

Ответ 1

На мой взгляд, канонического названия у такой структуры нет. В зависимости от задачи
она может иметь разные названия. Как примеры:


LRU Cache: в данной структуре данные упорядочиваются по частоте обращений к ним,
наименее используемые удаляются при достижении заданного размера кэша.
MRU Cache: такой же принцип, но в отличии от LRU вытесняется последний использованный
элемент.
EvictingQueue: структура данных из Guava, первый элемент очереди удаляется, если
очередь заполнена. Также есть MinMaxPriorityQueue.
CircularFifoQueue: структура данных из Apache Commons, заменяет старейший элемент,
если очередь заполнена.


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


Ответ 2

Для начала, я бы не стал называть такую структуру данных контейнером. От контейнера
ожидается, что он будет хранить все элементы а не только те, которые ему понадобятся.

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


Ответ 3

В C++ такого рода контейнер называется "очередь с приоритетом" std::priority_queue.
Правда, автоматического вытеснения, о котором упомянуто вопросе, при достижении максимального
размера не происходит. Такую функциональность можно достаточно легко реализовать самостоятельно.
Итоговый вариант можно было бы назвать "Очередь фиксированного размера с приоритетом"
(fixed_size_priority_queue).


Ответ 4

Может быть Circular buffer (кольцевой буфер)


Ответ 5

Я бы использовал обычный multi_set.

Как-то так:

multi_set  best;

if (best.size() < lim || x > *best.begin())
{
  best.insert(x);
  if (best.size() > lim)
    best.erase(best.begin());
}