Как создать последний недавно использованный кеш?

Если вы используете двусвязный список, вы получите вставку O (1) (после поиска), удаление O (1), поиск O (n).

Предполагая, что вы вставляете новые элементы спереди:

Если кеш не заполнен, просто добавьте его в начало (O(1)).

Если вам нужно обновить элемент, найдите его (O(n)), удалите из связанного списка (O(1)), затем добавьте на передний план (O(1)).

Если вам нужно удалить самый старый элемент, чтобы вставить новый элемент, удалите последний элемент (O (1)) и вставьте его вперед (O (1)) [примечание: в этом случае вам нужно сначала выполнить поиск в списке, чтобы увидеть если элемент еще не находится в кеше, поэтому O (n)].

Связанный список также может дать вам такое же время, так как поиск оставит вас на последнем элементе.

кеш LRU Python имеет O(1) вставку, удаление и поиск. В его дизайне используется двусвязный список записей (от самых старых к новым) и хэш-таблица для поиска конкретной ссылки.

Вот упрощенная (но быстрая) версия в менее чем 40 строк очень простого Python. Нетрудно перевести решение Python на C++:

class LRU_Cache(object):

    def __init__(self, original_function, maxsize=1000):
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = {}

        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        self.head = [None, None, None, None]        # oldest
        self.tail = [self.head, None, None, None]   # newest
        self.head[NEXT] = self.tail

    def __call__(self, *key):
        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        mapping, head, tail = self.mapping, self.head, self.tail
        sentinel = object()

        link = mapping.get(key, sentinel)
        if link is sentinel:
            value = self.original_function(*key)
            if len(mapping) >= self.maxsize:
                oldest = head[NEXT]
                next_oldest = oldest[NEXT]
                head[NEXT] = next_oldest
                next_oldest[PREV] = head
                del mapping[oldest[KEY]]
            last = tail[PREV]
            link = [last, tail, key, value]
            mapping[key] = last[NEXT] = tail[PREV] = link
        else:
            link_prev, link_next, key, value = link
            link_prev[NEXT] = link_next
            link_next[PREV] = link_prev
            last = tail[PREV]
            last[NEXT] = tail[PREV] = link
            link[PREV] = last
            link[NEXT] = tail
        return value

if __name__ == '__main__':
    p = LRU_Cache(ord, maxsize=3)
    for c in 'abcdecaeaa':
        print(c, p(c))

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

Вы также можете посмотреть WeakHashMap, который реализует автоматизированный механизм, в котором элементы могут быть удалены сборщиком мусора.

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

Редактировать: итератор std::list действителен при добавлении и удалении элементов при условии, что сам итератор элемента, на который ссылается итератор, не удаляется. См. последние строки в разделе Емкость и распределение в Википедии.

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

Тогда это будет O(n).

Взгляните на boost::multi_index. Одним из примеров, которые он показывает, является список MRU.