leetcode::lfu_cache::LFUCache类 参考

#include <leetcode.h>

Public 成员函数
	LFUCache (int capacity)
	用数据结构的容量 capacity 初始化对象 更多...
int	get (int key)
	如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。 更多...
void	put (int key, int value)
	如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。 更多...

Private 属性
int	capacity
unordered_map< int, int >	cnt
map< int, list< int > >	tnc
unordered_map< int, int >	um

详细描述

在文件 leetcode.h 第 3373 行定义.

构造及析构函数说明

LFUCache()

leetcode::lfu_cache::LFUCache::LFUCache ( int  capacity )

inline

用数据结构的容量 capacity 初始化对象

在文件 leetcode.h 第 3381 行定义.

                : capacity(capacity){};

成员函数说明

get()

int leetcode::lfu_cache::LFUCache::get

(

int

key

)

如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。

在文件 leetcode.cpp 第 9434 行定义.

                                 {
            if(capacity == 0) {
                return -1;
            }
            int ans = -1;
            if(um.contains(key)) {
                // 如果存在
                ans = um[key];
                cnt[key]++;                                                                   //增加计数
                const auto it = find(tnc[cnt[key] - 1].begin(), tnc[cnt[key] - 1].end(), key);//
                if(it != tnc[cnt[key] - 1].end()) {
                    tnc[cnt[key] - 1].erase(it);
                    if(tnc[cnt[key] - 1].empty()) {
                        tnc.erase(cnt[key] - 1);
                    }
                }
                tnc[cnt[key]].emplace_back(key);
            }
            return ans;
        }

引用了 capacity, cnt, acwing::acwing861::find(), tnc , 以及 um.

被这些函数引用 leetcode::lfu_cache::TEST().

put()

void leetcode::lfu_cache::LFUCache::put	(	int	key,
		int	value
	)

如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。

在文件 leetcode.cpp 第 9455 行定义.

                                             {
            if(capacity == 0) {
                return;
            }
            cnt[key]++;
            if(um.size() == capacity) {
                //满
                if(um.contains(key)) {
                    //已存在
                    tnc[cnt[key] - 1].erase(find(tnc[cnt[key] - 1].begin(), tnc[cnt[key] - 1].end(), key));
                    if(tnc[cnt[key] - 1].empty()) {
                        tnc.erase(cnt[key] - 1);
                    }
                } else {
                    //不存在
                    while(tnc.begin()->second.empty()) {
                        tnc.erase(tnc.begin());
                    }
                    const auto evicted = tnc.begin()->second.begin();
                    const int val      = *evicted;
                    tnc.begin()->second.erase(evicted);
                    cnt.erase(val);
                    um.erase(val);
                }
            } else {
                //未满
                if(um.contains(key)) {
                    //已存在
                    tnc[cnt[key] - 1].erase(find(tnc[cnt[key] - 1].begin(), tnc[cnt[key] - 1].end(), key));
                    if(tnc[cnt[key] - 1].empty()) {
                        tnc.erase(cnt[key] - 1);
                    }
                } else {
                    //不存在
                }
            }
            tnc[cnt[key]].emplace_back(key);
            um[key] = value;
        }

引用了 capacity, cnt, acwing::acwing861::find(), tnc , 以及 um.

被这些函数引用 leetcode::lfu_cache::TEST().

类成员变量说明

capacity

int leetcode::lfu_cache::LFUCache::capacity

private

在文件 leetcode.h 第 3377 行定义.

被这些函数引用 get() , 以及 put().

cnt

unordered_map<int, int> leetcode::lfu_cache::LFUCache::cnt

private

在文件 leetcode.h 第 3375 行定义.

被这些函数引用 get() , 以及 put().

tnc

map<int, list<int> > leetcode::lfu_cache::LFUCache::tnc

private

在文件 leetcode.h 第 3376 行定义.

被这些函数引用 get() , 以及 put().

um

unordered_map<int, int> leetcode::lfu_cache::LFUCache::um

private

在文件 leetcode.h 第 3374 行定义.

被这些函数引用 get() , 以及 put().

---

该类的文档由以下文件生成:

• leetcode.h
• leetcode.cpp