StackPub

LRU(Least recently used，最近最少使用)算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。 常见的LRU实现策略是: 新数据插入到链表头部； 每当缓存命中（即缓存数据被访问），则将数据移到链表头部； 当链表满的时候，将链表尾部的数据丢弃。 但是如上实现存在一个问题：命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部，时间复杂度是$O(N)$。未解决遍历带来的消耗，再此设计的是一种哈希表维护的双向链表结构，以减少寻找数据块时的时间消耗。 如上图所示，每个数据块拥有2个角度的身份，一个身份是缓存双向链表的成员，一个身份是哈希表成员。 LRU结构体设计 1234567891011121314151617/*定义LRU缓存的缓存单元*/typedef struct cacheEntryS{ char key; /* 数据块的key */ char data; /* 数据块的data */ struct cacheEntryS *hashLi...

方法 最好 最坏 平均 空间复杂度 稳定性 冒泡排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定 快速排序 $O(n\log_{2}n)$ $O(n^2)$ $O(n\log_{2}n)$ $O(n\log_{2}n)$ 不稳定 直接插入排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定 希尔排序 $O(n^{1.3})$ $O(1)$ 不稳定 简单选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定 堆排序 $O(n\log_{2}n)$ $O(n\log_{2}n)$ $O(n\log_{2}n)$ $O(1)$ 不稳定 归并排序 $O(n\log_{2}n)$ $O(n\log_2{2}n)$ $O(n\log_{2}n)$ $O(n)$ 稳定 基数排序 $O(d(r+n))$ $O(d(r+n))$ $O(d(r+n))$ $O(r)$ 稳定 排序算法的稳定性: 若在原始序列中,$a_i$和$a_j$的关键字相同,$a_i$出现在$a_j$...

查找是在一些(有序/无序)的数据元素中通过一定的方法找出与给定关键字相同的数据元素。 无序查找最简单的无序查找为: 12345678int sq_find(int arr[], int n, int key){ for(int i = 0; i < n; i++){ if(arr[i] == key) return i; } return -1;} 对于这个for循环查找,一般的时间浪费在了i<n的边界检查上了,因此可以设置一个监视哨兵来优化无序查找: 12345678int sq_find(int arr[], int n, int key){ int i = n; arr[0] = key; while(arr[i] != key) i--; return i;} 有序查找二分查找非递归实现 12345678910111213141516171819int BiSearch(int arr[], const int num, int begin, ...

树(Tree)是由$n(n>=0)$个结点组成的一个具有层次关系的非线性有限集合，树中的每个元素被称为树的节点，每个节点有若干个指针指向的后继结点(子结点)。树中节点的子树数目称为节点的度(degree)。树中各结点度的最大值称为树的度，通常称为几次树。度为0的结点称为叶子结点。 二叉树二叉树每个结点最多只有两个分支，左孩子右兄弟表示法可以将一颗 多叉树转化为二叉树。 非完全二叉树：普通二叉树。 完全二叉树：除最后一层外，每层的结点数均达到最大值，在最后一层上只缺少右边的结点。 满二叉树：除叶子结点外，每个结点都有两个孩子结点，且每一层的结点数都达到最大值。一颗深度为k的二叉树有$2^{k}-1$个结点。 二叉树的性质性质1：在二叉树的第i层上至多有$2^{i-1} (i>0)$个结点。 性质2：深度为k的二叉树至多有$2^{k}-1 (i>0)$个结点。 性质3：对于任何一颗二叉树，若度为2的结点数目有 n 个，则叶子数必定为 n+1 个。 性质4：具有n个结点的完全二叉树，它的深度必为$\lfloor \log_{2^n} \rfloor +...

栈(Stack)：后进先出(LIFO last in first out)。 队列(Queue)：先进先出(FIFO first in first out)。 栈(Stack)12345678typedef struct{ int data[MAXSIZE]; int top;}Stack;stack->data[stack->top--]; /* 弹出元素后，top-- */stack->data[++stack->top]; /* top++后，增加一个元素 */ 链式实现 12345678910111213141516typedef struct Node{ int data; struct Node* next;}Node;typedef struct{ Node* top; int size;}Stack;stack->top = node;stack->size++;stack->top = stack->top->next;stack-...

功能 POSIX C C++11 启动线程 pthread_t类型和相关API函数,pthread_create(),pthread_detach()和pthread_join() std::thread类与成员函数 互斥 pthread_mutex_t类型相关API函数,pthread_mutex_lock(),pthread_mutex_unlock()等 std::mutex类与成员函数,std::lock_guard<>和std::unique_lock<>模板 监控等待预期 pthread_cond_t类型与相关API函数,pthread_cond_wait(),pthread_cond_timed_wait()等 std::condition_variable和std::condition_cariable_any类与成员函数 原子操作与并发感知内存模型 不可用 std::atomic_xx类型,std::atmoic<>类模板,std::atomic_thread_fence()函数 线程安全容器 不可...

面向对象编程和泛型编程都能处理在编写程序时不知道类型的情况。OOP能处理类型在程序运行之前都未知的情况；而泛型编程中，在编译时就可以获知类型。 定义模板函数模板模板定义以关键字 template开始，后接模板参数列表(template parameter list)，模板参数列表表是用尖括号<>括住的一个或多个模板形参的列表，用逗号分隔，不能为空。使用模板时，我们显式或隐式地指定模板实参，将其绑定到模板参数上。 123456template<typename T>int compare(const T &v1, const T &v2){ if(v1 < v2) return -1; if(v2 < v2) return 1; return 0;} 模板类型参数(type parameter)：类型参数前必须使用关键字class或者typename，这两个关键字含义相同，可以互换使用。旧的程序只能使用class。 非类型模板参数(nontype parameter)：表示一个值而非...

继承与派生 继承方式 继承的构造函数 多继承 虚继承 多态与虚函数 虚函数 虚析构函数 纯虚函数与抽象类 RTTI dynamic_cast运算符 typeid运算符 type_info类 OOP：概述面向对象程序设计（object-oriented programming）的核心思想是数据抽象、继承和动态绑定。 继承（inheritance）：通过继承联系在一起的类构成一种层次关系。通常在层次关系的根部有一个基类（base class）。其他类直接或者间接从基类继承而来，这些继承得到的类成为派生类（derived class）。基类负责定义在层次关系中所有类共同拥有的成员，而每个派生类定义各自特有的成员。 对于某些函数，基类希望它的派生类个自定义适合自己的版本，此时基类就将这些函数声明成虚函数（virtual function）。 派生类必须通过使用类派生列表（class derivation list）明确指出它是从哪个基类继承而来。形式：一个冒号，后面紧跟以逗号分隔的基类列表，每个基类前都可以有访问说明符。 12345678910class Quote
...

基本概念重载运算符是具有特殊名字的函数：由关键字operator和其后要定义的运算符号共同组成。 当一个重载的运算符是成员函数时，this绑定到左侧运算对象。成员运算符函数的(显示)参数数量比运算对象的数量少一个。 只能重载大多数的运算符，而不能发明新的运算符号。重载运算符的优先级和结合律跟对应的内置运算符保持一致。 123456//非成员运算符函数data1 + data2;operator+(data1, data2);//成员运算符函数data1 += data2;data1.operator+=(data2); 将运算符是否定义为成员函数的一些判断: 赋值(=)、下标([])、调用(())和成员访问箭头(->)运算符必须是成员。 复合赋值运算符一般来说是成员,但并非是必须的。 改变对象状态的运算符或者与给定类型密切相关的运算符通常是成员，如递增、解引用。 具有对称性的运算符可能转换任意一端的运算对象，如算术、相等性、关系和位运算符等，通常是非成员函数。 可以被重载 不可以被重载 +, -, *, /, %, ^ ::, .*, ., ? :, ...

IO库 istream：输入流类型，提供输入操作。 ostream：输出流类型，提供输出操作 cin：一个istream对象，从标准输入读取数据。 cout：一个ostream对象，向标准输出写入数据。 cerr：一个ostream对象，向标准错误写入消息。 >>运算符：用来从一个istream对象中读取输入数据。 <<运算符：用来向一个ostream对象中写入输出数据。 getline函数：从一个给定的istream对象中读取一行数据，存入到一个给定的string对象中。 IO类 iostream头文件：从标准流中读写数据，istream, ostream, iostream等。 fstream头文件：从文件中读写数据，ifstream, ofstream, fstream等。 sstream头文件：从字符串中读写数据，istringstream, ostringstream, stringstream等。 IO对象无拷贝或赋值 1.IO对象不能存在容器里. 2.形参和返回类型也不能是流类型。 3.形参和返回类型一般是流的引用。 4.读写一个IO...