1 虹少侠

尚未进行身份认证

醉生梦死.....

等级
TA的排名 33w+

任意类型容器Any

利用模板类继承非模板类,实现一个可以存储任意类型的容器#ifndef_ANY_H#define_ANY_H#include<string>#include<algorithm>classIAnyItemabstract{public: virtual~IAnyItem(){} virtualconsttype_info&...

2019-08-13 20:08:50

c++实现LFU算法

LFU(LeastFrequentlyUsed),是一种缓存算法,它对每一个数据块都有一个访问次数的记录,也就是一个数据块的访问次数越大,在将来越可能访问。1.每个节点(数据块)都有一个访问次数,新插入的节点访问次数为12.相同访问次数的依据时间排序,后插入的在前面3.当需要淘汰数据时,会从尾部,也就是访问次数从小到大,开始淘汰这里是使用c++实现的LFU缓存:主要利用了一个mu...

2019-08-09 15:10:31

c++实现LRU算法

LRU算法(LeastRecentlyUsed),是内存管理中为了保证命中率的一种页面置换算法,可用于内存和辅存之间也可用用在cache和内存之间,redis中的过期淘汰策略中也使用了lru算法。它是利用了程序局部性的原理,简单说就是此刻访问的页面很可能在下一时刻也会访问。这里使用c++实现简单的LRU缓存#ifndef_LRU_H#define_LRU_H#include...

2019-07-31 20:49:52

跳跃表实现

跳跃表:跳跃表与链表结构相似,只是引入“分层”的概念,从上到下的每一层都是一个链表。借个图:从图中可观察到跳跃表有以下的性质:1.每个节点有多个层,每层都有一个指向同层的下一节点的指针2.每层的链表都是一个有序链表,根据给定的key排序3.最底层也就是第一层,的链表包含所有节点4.存在于k层的节点,同样也存在于<k层的链表中引入多层的链表的概念是为...

2019-07-04 11:57:47

Redis源码阅读二,链表和字典

Redis链表redis链表本质上就是一个可以前后移动,并带有头尾指针的双向链表它的结构:typedefstructlistNode{structlistNode*prev;structlistNode*next;void*value;//使用void*实现泛型}listNode;typedef...

2019-06-13 21:13:35

Redis源码阅读一,简单动态字符串

Redis简单动态字符串(SDS)的特点1、在计算长度时的时间复杂度为o(1)。2、在进行拷贝,连接字符串时不必担心空间溢出,因为它会根据长度的需要进行扩容。3、二进制安全,传统的char*是以'\0'作为字符串结尾的标志,也就是字符串本身不能包含'\0'否则会截断。4、惰性空间释放,当字符串的空间被手动缩减时,不会将空间释放,而是记录在free字段中,方便之后可能的append、...

2019-06-12 22:28:53

排序算法总结对比

/*常用排序算法分析*/void swap(int&x,int&y){ if(x!=y){ x=x+y; y=x-y; x=x-y; }}/*冒泡排序时间复杂度为o(n^2)两两比较,交换,每次内层循环在未排序序列中找出最大值放到已排序中对于部分有序的序列来说,效率较高稳定*/void bubble_sor...

2019-04-28 10:45:36

B+树插入删除实现(c++)

B+树性质B+树B+树的实现有多种,有关键字和子树个数相等的,还有向B树一样的子树比关键字数量多一个。这里使用第二种方式。1.树的每个节点最多有M个子树2.根节点至少有两个子树(如果不是叶子节点)3.除根节点之外的所有非叶子节点,至少有M/2个子树(向上取整)4.所有非叶子节点包括keycount,child[0],key[1],child[1],key[2]..key[keyco...

2019-03-20 22:29:36

B树插入删除实现(c++)

B树的性质1、树的每个节点最多有M个子树。2、根节点至少有两个子树(除非它是叶子节点)。3、除根节点之外的所有非叶子节点至少有M/2个子树(向上取整)。4、所有非叶子节点包含keycount,childs[0],keys[1],childs[1],keys[2]........keys[keycount],childs[keycount]。也就是所有非叶子节点的子树在key值...

2019-03-14 13:14:59

Effective c++ 读书总结 21-25

条款二十一:必须返回对象时,别妄想返回其reference1、为什么我们会选择返回引用类型因为返回引用类型可以避免以值返回造成的对象构造和析构带来的效率问题。特别是当一个对象内部资源很大的时候,以值返回往往造成效率降低。2、什么情况下可以使用引用返回当一个函数操作是对对象内部资源生效时,且需要返回生效之后的结果的时候。classtest{private:str...

2019-03-11 13:42:37

Effective c++ 读书总结 16-20

条款十六:成对使用new和delete时要使用相同的形式1、在使用new操作符时,事件上做了两件事,一是申请堆区空间,二是在此空间上执行申请类型的构造函数。使用delete也是两件事,一是调用对象的析构函数,释放里面的资源,二是释放内存。2、数组类型的空间申请和释放string*strs=newstring[10];//new操作符会对每一个string对象都调用一次...

2019-03-10 19:45:16

使用mmap遇到总线错误bus error

先简单描绘一下错误发生的场景:#defineMMAP_BUFF_SIZE4096structMessage{intlen;chardata[1024];};intfd=open("./test",O_RDWR|O_CREAT);lseek(fd,MMAP_BUFF_SIZE,SEEK_SET);Message*m...

2019-03-07 14:21:35

哈夫曼编码

哈夫曼树哈夫曼树就是一棵带权二叉树、它的WPL是最小的、也就是从根节点到每一个节点的路径长度(经过的边数)与权值乘积的总和是最小的、就称为哈夫曼树。哈夫曼编码把各个字符在整个串中出现的频率作为它的权重、通过使用0、1表示来缩短整个串的长度、可用于无损压缩。完成哈夫曼编码首先要先建立哈夫曼树、根据树中节点的路径、计算出对应节点的编码。下面我写了一个类其中就包含了建立哈夫曼树和完成...

2019-01-23 21:22:25

智能指针shared_ptr

说明:在使用c++语言编程时、为了防止忘记对申请的空间进行释放、我们通常使用智能指针来管理对象。智能指针有很多种、它们适用于不同的场合。auto_ptr:只允许唯一的一个auto_ptr对象管理一个资源、在拷贝时会自动将原auto_ptr指向置空。unique_ptr:同一时刻只允许一个unique_ptr对象指向指定资源、不允许拷贝、通过release()释放所有权、move移动所有...

2019-01-23 19:17:33

队列转栈

队列转栈队列转栈就是使用两个队列、相互不断地push、pop完成stack的功能直接看代码:要通过使用队列提供的操作接口来完成栈的功能、不能直接操作指针。#ifndefQUEUE_TO_STACK_H#defineQUEUE_TO_STACK_H#include<cstdio>#include<string>usingnamespacest...

2019-01-22 16:09:03

栈转队列

栈转队列栈转队列就是利用两个栈相互push、pop操作完成队列的功能。直接看代码:#ifndef_STACK_TO_QUEUE_H#define_STACK_TO_QUEUE_H#include<string>#include<iostream>#include<stack>#include<cstdio>#i...

2019-01-22 15:12:01

遇到的错误以及一些配置、做个记录

Vs2012重定义的错误2018-12-5今天我遇到了一个链接期错误“重定义”、以前也遇到过、但是以前是“真的重定义”、有重复的变量或者是重定义的函数、但是这次不一样、听我讲清整个事件的全过程:地点:一个头文件中、暂时命名为“app.h”,更细致一些是在一个命名空间中如下:namespacetest{namespaceAPP{boos...

2018-12-05 19:56:30

Effective c++ 读书总结 11-15

条款十一:在operator=中处理“自我赋值”1、自我赋值的发生1、clssTest;Testt;t=t;//有点傻2、arr[i]=arr[j];//不容易察觉、当i==j时自我赋值3、*p1=*p2;//当p1,p2指向同一个地址时自我赋值2、几种解决方案解决自我赋值时、在operator=中需要同时考虑自...

2018-11-06 09:23:29

开链式哈希表

简单说明hashtable适用于需要频繁插入、删除、查找的场合、在这些场合中hashtable都可以常数平均时间完成、然而之所以hashtable的效率这么高、是因为在以上这些操作时都是通过hashfunction直接定位元素在表中的位置然后直接操作。不可避免的有一些部分性质或全部性质相同的元素被定位到同一个位置上、这时新的问题产生了:解决冲突。实际上解决方法有很多:像线性探测、二次探测、开...

2018-11-04 20:06:46

优先队列实现

简单说明优先队列可以根据key值的大小将元素进行排序、先被pop的通常是优先级最高的。优先队列的内部实现其实是利用了堆的数据结构、binaryheap是一种完全二叉树、以大堆为例、每棵树的根节点的key值一定大于其子孙节点的key值、完全二叉树处了最底层的叶子节点外、其他位置都是填满的。这样我们可以利用数组来存储所有节点。若将数组从下标1开始存储元素、那么下标为i的节点的左孩子节...

2018-10-31 17:02:16

查看更多

勋章 我的勋章
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。