Update your browser to view this website correctly. Update my browser now
STL中的关联容器分为set和map两大类，以及他们的衍生体multiset和multimap，这些容器均由红黑树（RB-tree）实现。另外，STL还提供了不在标准之外的关联式容器：hashtable以及以此为底层机制的hash_set，hash_map和他两的multi衍生体。 以红黑树和哈希表为底层结构构造的容器最大的不同是前者为直接排序而后者不是。 1.红黑树 我的这篇博客介绍了红黑树和AVL树的大概轮廓，具体插座和查找细节可以参考《算法导论》，此处不介绍这些细节了。红黑树是一种接近平衡的平衡二叉搜索树，拥有良好的查找、插入复杂度。 STL中的RB-tree提供了两种插入操作：insert_unique()和insert_equal()，前者表示被插入节点的key值独一无二，后者表示ke…
退役好久了，惭愧的是一直没搞过树状数组和线段树，以前都是队友搞的，最近刷codeforeces被树状数组卡了好几次，遂决定怒刷树状数组。 0.算法 本来想写写长篇的算法过程，从如何建树到如何维护更新，结果发现这篇博客写的很赞了，我也就不写了，就写写个人对算法的理解以及刷的题目吧。 树状数组的优点就在于维护了一个前序和树，算法的核心就是『前序和』，碰到的各种题目也都是将各种模型转换为前序和，然后再进行查找和插入操作。 其时间复杂度如下：查找和插入/更新都是O(log MaxVal)，其中MaxVal表示树的最大下标，非常适合插入频繁的操作。以下read(x)表示查找x的前序和，update(x, p)表示更新x下标对应的数组的数值为p，以下BIT为表示树状数组的简称。 模板…
在STL中，有以下几个序列式容器：array、vector、heap、priority_queue、list、slist、deque、stack、queue。其中vector、list、deque为三个标准容器（container）；stack和queue是在deque上进行封装而成的，专有名词叫做配接器（adapter）；array是C++内建容器，不对外使用；heap是基于vector封装的，priority_queue是基于heap封装的；slist是非标准的单向链表。 1.vector vector是C++中的动态数组，可以动态增删，而不需要类似静态数组自己维护空间的分配，其维护的也是一个连续线性空间，支持随机存取，良好的特性使得其成为STL中最常用的容器之一。 vector中有几个需要注意的概念： vecto…
好久没刷题了，前几天做google笔试生疏了很多，还是需要刷刷题，保持头脑灵活。不过codeforces题目一般都在晚上，真心没精力熬夜，只能改天起来再搞。这次是几天前的比赛。 A.Olesya and Rodion 简单题 B.Kolya and Tanya 简单题 C.Marina and Vasya 题意：给定两个字符串s1, s2，给定t，问是否存在一个相同长度的字符串与s1, s2各有t个字符不一致（位置不变）。 思路：判断s1和s2存在几个相同字符（相同位置），记为nr。记t=n-t，意味着找出n-t个一样的字符即可。则若不满足t - nr > (n - nr) / 2则不存在，反之存在。若t<=nr则这几个相同字符之内选t个即可，否则再把不一样的字符里面选t-nr个变为一样。 &e…
hamp是ovs提供的一种哈希表的结构。 0. 普通hash表 以前我们用的哈希表结构一般是如下情况： 左边为一维数组，每个数组元素对应一个映射之后的hash值，每个数组元素对应一条单向链表，该单向链表中所有元素的值域在哈希映射之后一致，且都为表头数组元素的值。链表中一般包含两个域，一个为值域，另一个为指针域。好的哈希映射函数应该使每条链上的长度差不多，而不是某条过长。装填因子的概念就是：散列表中的元素个数与散列表大小的比值。 1. hmap结构 而hmap的结构与之非常相似，其结构如下： hmap为hash表总节点，其结构如下： /* A hash map. */ struct hmap { struct hmap_node **buckets; /* Mu…
linux建议开发者使用其内建的数据结构，而不要自作主张搞一套山寨的。本文讲解内核中常用的4种数据结构：链表，队列，映射，二叉树。 1.链表 链表包括单向链表（有一个后向指针），双向链表（有一个后向指针和一个前向指针），环形链表（首尾相连）。linux内核的标准链表采用环形双向链表形式实现。 1.1 链表数据结构 linux内核方式与众不同，它不是将数据结构塞入链表，而是将链表节点塞入数据结构。比如，一个普通的链表节点： struct Node { int data; struct Node *pre;; struct Node *next; }; linux下的实现是把前后指针抽出来，形成单独数据结构…
以前一直想好好看看红黑树，但看着看着认为这种实现的东西直接调别人的包就可以了，我只要知道大概的时间空间复杂度就ok了。好吧，我承认我理解肤浅了，今天没啥事就把红黑树好好复习了一下。 红黑树(RB-Tree)用途真是太广了，Linux内核，STL中的关联容器，nginx的实现……太多地方用到了。目前的AVL树已经快走入博物馆了，红黑树开始在历史舞台上发挥光和热了。好吧，废话扯多了。move on! 二叉搜索树 首先回顾一下平衡二叉搜索树的祖先：二叉搜索树。它具有以下性质： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。 它的优点我就不说了，缺点就是可能导致不平衡：某一边的子树高…
