C++实现支持泛型的LFU详解

首先定义LFU存储数据节点ListNode的结构, 此结构支持键K和值V的模板，为了在有序元素中实现比较（严格小于），这里需要重载小于号，如果此数据的使用频次最少，则小于结果为true，如果频次相等，轮次早的数据最小。

template<typename K, typename V>
struct ListNode {
    K key;
    V value;
    int freq;
    long cur;
    bool operator<(const ListNode &x) const {
        if (freq < x.freq)
            return true;
        else if (freq == x.freq)
            return cur < x.cur;
        else
            return false;
    }
};

然后我们来实现lfu类，我们用unordered_map去存key值对应的ListNode，用set<ListNode<K,V>> freq来充当频次的存储容器，使用set的好处是自动排序，频次小的数据迭代器会被排到freq的begin()，删除是只需要erase掉begin所指向的迭代器即可。我们来具体分析get和put操作

  • get操作首先去map中查询此key对应ListNode是否存在，如果此数据存在，将其对应的频次+1（这里用reinsert函数实现），如果数据不存在，返回-1。
  • put操作也要去map中查询此key对应ListNode是否存在，若存在，直接将ListNode的value更新，并且将其对应的频次+1（同上），否则，在map对应此键值的桶中插入ListNode，然后在freq中将其对应的频次设为1并插入。

完整代码如下：

#include <map>
#include <set>
#include <unordered_map>
using namespace std;
template<typename K, typename V>
struct ListNode {
    K key;
    V value;
    int freq;
    long cur;
    bool operator<(const ListNode &x) const {
        if (freq < x.freq)
            return true;
        else if (freq == x.freq)
            return cur < x.cur;
        else
            return false;
    }
};
template<typename K, typename V>
class lfu {
private:
    long cur_rount;
    int capacity;
    unordered_map<int, ListNode<K, V>> m;
    set<ListNode<K, V>> freq;
public:
    lfu(int capacity) {
        capacity = capacity;
        cur_rount = 0;
    }
    V get(K key) {
        auto it = m.find(key);
        if (it == m.end())
            return -1;
        V value = it->second.value;
        reinsert(it->second);
        return value;
    }
    void put(K key, V value) {
        if (capacity == 0) return;
        auto it = m.find(key);
        if (it != m.end()) {
            it->second.value = value;
            reinsert(it->second);
            return;
        }
        if (m.size() == capacity) {
            const ListNode<K, V> &node = *freq.begin();
            m.erase(node.key);
            freq.erase(node);
        }
        ListNode<K, V> node{key, value, 1, ++cur_rount};
        m[node.key] = node;
        freq.insert(node);
    }
    void reinsert(ListNode<K, V> &node) {
        freq.erase(node);
        ++node.freq;
        node.cur = ++cur_rount;
        freq.insert(node);
    }
};

这里写了一个简单的主函数去验证，K和V都使用int进行实例化。

可以看到第一次查询，得到key=1的值为8，符合预期，在插入key=7 value=10的ListNode后，LFU频次最低的Key=5 ListNode。此时再去get Key=5的值会得到一个-1，符合预期。

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • C++泛型编程基本概念详解

    目录 1.什么是泛型编程? 2.函数模板 (1)函数模板概念 (2)函数模板格式 (3)函数模板的原理 (4)函数模板的实例化 (5)模板参数的匹配原则 3.类模板 (1)类模板的定义格式 (2)类模板的实例化 总结 1.什么是泛型编程? 比如说,我们如何实现一个通用的交换函数呢?int型.double型.char型的交换 void Swap(int& left, int& right) { int temp = left; left = right; right = temp; } vo

  • 自定义的Troop<T>泛型类（ c++, java和c#）的实现代码

    Troop<T>是一个泛型列表操作类,适用于非高性能和非大数据量的要求.包括了:取值get,赋值set,追加append,插入insert,清除remove,进队enqueue,出队dequeue,交换swap,滚动roll,进栈push,出栈pop等日常操作. //for more information, please access http://www.one-lab.net using System; using System.Collections.Generic; using Sy

  • C++泛型算法的一些总结

    泛型算法的一些总结1.每个泛型算法的实现都独立于单独的容器,并且不依赖于容器存储的元素类型. 2.泛型算法从不直接添加或删除元素. 3.与容器的类型无关,只在一点上隐式地依赖元素类型:必须能够对元素做比较运算. A.需要某种遍历集合的方式:能够从一个元素向前移到下一个元素. B.必须能够知道是否到达了集合的末尾. C.必须能够对容器中的每一个元素与被查找的元素进行比较. D.需要一个类型来指示元素在容器中的位置,或者表示找不到该元素. 4.迭代器将算法和容器绑定起来.算法基于迭代器及其操作实现,

  • C++算法与泛型算法（algorithm、numeric）

    本文包括的算法有: 只读算法:find().count().accumulate().equal() 写算法:fill().fill_n().back_inserter().copy().copy_backward().replace().replace_copy().next_permutation().prev_permutation() 重排元素算法:sort().stable_sort().unique() 一.算法简介 大多数算法在头文件algorithm中.标准库还在头文件numer

  • 关于C++ TpeScript系列的泛型

    目录 一.模版 二.泛型 三.泛型递归 四.默认泛型参数 五.泛型重载 前言: 我在面试的时候,通常喜欢问候选人一些莫名其妙的问题.比如这样的问题,假如你是某个库的作者,你如何实现某个功能.这类问题一般没有正确的答案,主要意图是考察一下候选人对这个库有没有更深入的理解,次要意图是觉得这样挺好玩.玩归玩,但该严肃的时候也要严肃起来.有一次,我面试到一位用过TypeScript的同学,这让人眼前一亮(从我的经验看,国内偶尔有大厂会用,小厂基本没有).随后,我问了句,你是怎么理解泛型的呢?问了之后,我

  • C++实现的泛型List类分享

    额,不要说我三心二意:一边在看.NET和CLR的原理.一边在看JavaScript.一边在看Java:有时看算法有时看Unity.Hibernate:有时看Hadoop有时看Redis:现在又开始看C++了. 以前觉得无论什么语言嘛,其实都差不多,核心思想基本一致.现在又不这么想了,其实语言的选择对软件的性能.可靠性.开发成本之类的关系很大,所以觉得还是要多接触一些比较核心的东西--那么自然是C++了.以前在学校学的C++完全是酱油,太水了基本没啥用,用来用去和C差不多,所以现在要自己学啦. 废

  • C++使用泛型导致的膨胀问题

    目录 临峰不畏博主从事C++软件开发多年,由于之前的开发环境都是资源充足的服务器,不用考虑磁盘空间的问题.最近打算在智能家居主机的嵌入式平台上使用C++进行开发.FLASH存储空间有限,这是必须要考虑的因素,一定要重视. 如下定义两个list,元素类型不同: list<int> l1; list<string> l2; 如果是用C语来做应该怎么办?它会对应list<int>写一套代码,再对list<string>写一套.每套都有相同的成员函数,只是变量类型各

  • C++ 泛型编程详解

    泛型编程与面向对象编程的目标相同,即使重用代码和抽象通用概念的技术更加简单.但是面向对象编程强调编程的数据方面,泛型编程强调的是独立于特定数据类型. 这一篇介绍一下 C++ 编程中与面向对象并列的另一大分支--泛型编程,这一篇主要介绍函数模板.类模板和成员模板三大部分 如有侵权,请联系删除,如有错误,欢迎大家指正,谢谢 泛型编程 模板是泛型编程的一种重要思想,STL(Standard Template Library,标准模板库)是采用模板实现的一个实例 函数模板 对比函数重载(同一作用域内函数

  • C++实现支持泛型的LFU详解

    C++实现支持泛型的LFU详解

    首先定义LFU存储数据节点ListNode的结构, 此结构支持键K和值V的模板,为了在有序元素中实现比较(严格小于),这里需要重载小于号,如果此数据的使用频次最少,则小于结果为true,如果频次相等,轮次早的数据最小. template<typename K, typename V> struct ListNode { K key; V value; int freq; long cur; bool operator<(const ListNode &x) const { if

  • java反射之通过反射了解集合泛型的本质(详解)

    java反射之通过反射了解集合泛型的本质(详解)

    本文接上文"java反射之方法反射的基本操作方法",利用反射了解下java集合中泛型的本质 1.初始化两个集合,一个使用泛型,一个不使用 ArrayList list1 = new ArrayList(); ArrayList<String> list2 = new ArrayList<String>(); 2.有定义类型可得在list2中添加int类型会报错 list2.add("Hello"); list2.add(20); //报错 3

  • TypeScrip中泛型的案例详解

    泛型的定义 // 需求一: 泛型 可以支持不特定的数据类型, 要求,传入的参数和返回参数一致 // 这种方式虽然能实现传入和返回的参数一致,但是失去类型参数检验 /* function getData(value: any): any { return "success" } */ // 定义泛型解决需求一 // T表示泛型(这里的大写字母可以随便定义,但一般默认为T) 具体什么类型是调用这个方法的时候决定的 function getData<T>(value: T):T{

  • Go1.18新特性工作区模糊测试及泛型的使用详解

    Go1.18新特性工作区模糊测试及泛型的使用详解

    目录 前言 Go工作区模式(Go Workspace Mode) 现实的情况 多仓库同时开发 多个新仓库开始开发 工作区模式是什么 推荐的使用方法 使用时的注意点 Go模糊测试(Go Fuzzing Test) 为什么Golang要支持模糊测试 模糊测试是什么 Golang的模糊测试如何使用 最简单的实践例子 提供自定义语料 使用时的注意点 Go的泛型 类型参数(Type Parameters) 类型集合(Type Sets) 类型推导(Type Inference) 类型统一化(Type Un

  • Java中泛型的示例详解

    目录 泛型概述 使用泛型的好处 泛型的定义与使用 定义和使用含有泛型的类 含有泛型的方法 含有泛型的接口 泛型通配符 通配符基本使用 通配符高级使用----受限泛型 泛型概述 我们都知道集合中是可以存放任意对象的,只要把对象存储集合后,那么这时他们都会被提升成Object类型.当我们在取出每一个对象,并且进行相应的操作,这时必须采用类型转换. 大家观察下面代码: public class GenericDemo { public static void main(String[] args) {

  • 微信小程序图片自适应支持多图实例详解

    微信小程序图片自适应支持多图实例详解 微信小程序图片自适应,是一个比较常见的需求,平时我们在WEBView中,只需要设置max-width:100%.在微信里面虽然widthFix也能实现,但有一个缺陷就是图片的宽度值要大于或者等于设定的值,否则就会发生拉伸变形,本文通过另外一种来适应. 首先我们来看看图片组件给的一些说明: 属性名 类型 默认值 说明 src String 图片资源地址 mode String 'scaleToFill' 图片裁剪.缩放的模式 binderror HandleE

  • Python3 xml.etree.ElementTree支持的XPath语法详解

    xml.etree.ElementTree可以通过支持的有限的XPath表达式来定位元素. 语法 ElementTree支持的语法如下: 语法 说明 tag 查找所有具有指定名称tag的子元素.例如:country表示所有名为country的元素,country/rank表示所有名为country的元素下名为rank的元素. * 查找所有元素.如:*/rank表示所有名为rank的孙子元素. . 选择当前元素.在xpath表达式开头使用,表示相对路径. // 选择当前元素下所有级别的所有子元素.

  • 手机Python编程软件QPython支持第三方库安装详解

    手机Python编程软件QPython支持第三方库安装详解

    目录 前言 安装 如何使用呢? 终端 编辑器 文件 QPYPI 前言 不得不说,对于写代码这件事,真的必须就是在电脑上才会有很好的体验.手机上写Python代码,那种感觉确实不敢想. 但是总有粉丝私信我: 有没有手机端写Python代码的软件呢?上班.下班坐地铁,坐公交挺无聊的,想要练练代码. 鉴于此,我还是写一篇文章给大家推荐这款软件(软件名字叫做QPython

  • Vue2如何支持composition API示例详解

    目录 前言 如何使用 原理解析 响应式( ref reactive 的实现) 总结 前言 自从 Vue3 发布之后,composition API 这个词走入写 Vue 同学的视野之中,相信大家也一直听到 composition API 比之前的 options API 有多好多强,如今由于 @vue/composition-api 插件的发布,Vue2 的同学也可以上车咯,接下来我们主要以响应式的 ref 和 reactive 来深入分析一下,这个插件是怎么实现此功能的. 如何使用 // 入口

  • Android RecyclerView网格布局（支持多种分割线）详解(2)

    Android RecyclerView网格布局（支持多种分割线）详解(2)

    上篇Android RecyclerView 详解(1)-线性布局 记录了下RecyclerView的使用方法,并且讲述了线性布局列表的使用方法,在此基础上加上了万能分割线,支持颜色分割线和图片分割线,同时支持对分割线设置线宽. 这篇是总结一下网格布局的使用,同样也支持两种分割线和线宽的设置. 主要的相关类: 1. RecyclerView.Adapter 2. GridLayoutManager 网格布局管理器 3. RecycleView.ItemDecoration 分割线 下面就直接通过

随机推荐