Home

skiplist，即跳表是由William Pugh在1989年发明的，允许快速查询一个有序连续元素的数据链表，搜索、插入、删除的平均时间复杂度均为O(lgn)。 本文介绍下对于skiplist的理解，包括背景、推导过程、伪代码以及复杂度的证明。 1. 背景 有序数组的好处是可以通过二分实现O(lgn)的高效查找，然而插入元素时，为了保证有序性，时间复杂度是O(n)的。链表则刚好相反，插入数据是O(1)，查找元素则是O(n)的。即使链表数据是有序的，查找元素仍然是O(n)的，因为本质上，链表不支持random access. 那么，是否存在一种链表，既支持高效的数据插入，又可以实现高效的查找？ 介绍skiplist前，我们先举一个坐火车的例子。 假设公司组织出去bui，我们...

C++ 提供了多种 cast 的方式:static_cast/dynamic_cast/const_cast/interpret_cast。 其中google代码规范明确表示了不建议使用RTTI，也就是尽量少使用dynamic_cast。本文介绍下 protobuf 里是如何使用down_cast替代dynamic_cast的。

基于 protobuf 的 RPC 可以说是五花八门，其中不乏非常优秀的代码例如 brpc, muduo-rpc 等。 protobuf 实现了序列化部分，并且预留了 RPC 接口，但是没有实现网络交互的部分。 本文想介绍下，如何实现基于 protobuf 实现一个极简版的 RPC ，这样有助于我们阅读 RPC 源码。 一次完整的 RPC 通信实际上是有三部分代码共同完成： protobuf 自动生成的代码 RPC 框架 用户填充代码 本文假设用户熟悉 protobuf 并且有 RPC 框架的使用经验。首先介绍下 protobuf 自动生成的代码，接着介绍下用户填充代码，然后逐步介绍下极简的 RPC 框架的实现思路，相关代码可以直接跳到文章最后。

memcache

stl iterator