用C++11实现的STL标准库，容器和算法包含但不限于STL 容器实现了几乎所有标准接口,无异常处理
代码测试环境: vs2015,release,O2优化,64位,i3处理器
以下为一些数据结构的设计,和某些算法的数学证明
(主要是 <<stl源码剖析>> 没有写出来的).
未特殊说明,下文中std/stl全部指代vs2015自带的标准库
=============转载请注明出处=============
第一级配置器使用malloc-free作为分配
释放器.第二级分配器使用内存池,对于大于128字节的请求,第二级分配器
直接调用第一级分配器.这两级配置器的程序照搬自<<stl源码剖析>>的
SGI的某一版实现.
针对这一点该头文件提供两个分配器,一个是qmj容器的默认内存分配器allocator,使用二级分配器.
另一个是simple_allocator使用一级分配器.这两个分配器都不符合标准.
qmj::各容器虽然都提供有自定义内存分配器模板参数,但不提供接受分配器的 构造函数,所以不支持动态改变容器的分配器.即使在编译器提供分配器也要 符合allocator_base的接口.
为qmj::map和qmj::set基类,树中所有叶节点和少子节点
(没有左节点或右节点)的空闲指针以及根节点的父节点都指向名为NIL的黑色节点.
1.在插入和删除中始终维护NIL的父节点的为空,以作为NIL的标识,左节点
指向树中的最大节点,右节点指向最小节点,这可让迭代器递增递减算法
更加简洁高效.
由于极值节点都在NIL中,rbt::begin,rbt::end()可为常数时间,虽然
没有增加每次插入删除的复杂度,但会增加rbt::insert,rbt::erase等
的常数.对比通过rbt::minimum(root),rbt::maximum(root)复杂度O(lgn),
来获得最小最大节点来说.如果经常进行插入删除操作,而较少使用迭代器
可能有点得不偿失.但经过测试,qmj::rbt::insert,qnj::rbt::erase还是比
std快.实际上经过测试发现对qmj::rbt的遍历并没有提高多少速度,原因在于
根据Amdahl定律,相对于O(n)复杂度的遍历,O(l)的迭代器提取所占的总体
百分比太少.所以我的算法反而复杂了代码.
对1000000个无重复随机int整数的set对比测试
对1000000个随机int整数的set对比测试,其中无重复数据32768个
对1000000个随机有重复整数的multiset对比测试,(图中set test 标题有误)
2.qmj::rbt::find比std::rbt::find更快的原因在于std使用了
std::rbt::lower_bound作为查找内部函数.该操作可能进行额外的递增
/递减操作.
图中的桶是连续内存
qmj::unordered_map和qmj::unordered_set的基类,
对于qmj::hashtable::equal_range(key),该函数返回表中关键字key所在
的区间迭代器,我使用的算法是在调用该算法时才改变内部结构,让在一个桶中
具有关键字key的节点连在一起.这样做的优点是加速插入,缺点是如果多次
调用该算法,该算法每次都会遍历该关键字所在桶中的每一个节点.
例如比对两个允许相同关键字的hashtable内的元素是否相等时就会多次调用
equal_range.
以上测试unordered_set无重复数据
以上测试unordered_set有3/4重复数据
以上测试unordered_multiset
qmj::unorder_multi(set/map)::operator== 和access(遍历)慢很多,operator==慢
一是因为遍历慢,二是因为equal_range每次都要遍历桶中全部元素.
operator==使用了qmj::is_permutation,该算法确定第一个区间
是否是第二个区间的排列,复杂度O(n^2).隐藏在其中的常数非常大,
如果直接使用该算法是没有用处的.但是hashtable::equal_range是常数时间,
所以operator==对两个hashtable::equal_range里的元素区间进行比较,
一般桶里的元素数目为常数,所以整个算法复杂度为O(n).
维护一个节点指针head,初始化为nullptr,每当一个空桶插入元素,就让新插入
的元素的next指针指向head,然后让head指向新插入的元素.删除时如果一个桶
变为空,更新head指向删除元素的next.
这样各个节点将会变成单向链表,如图
但这会造成一个问题,无法直接判断一个桶中的local_iterator是否走到尽头,
对于equal_range将造成阻碍.
1.直接对当前迭代器所指元素调用hash函数来判断元素是否在目标桶中, 但hash函数开销比较大.
2.添加哨兵节点,next==nullptr,next_bucket指向了下一个桶,如图
3.令每个桶存储一个结构体而不是一个指针,其中包含节点指针和桶元素计数器,无图.
文件中的qmj::hashtable并未使用上述3个算法
qmj::avl_tree 将AVL_tree的递归回溯插入法优化成循环上溯插入法.qmj::avl_tree的插入和删除采用了
和qmj::rb_tree相同的模式,先完成插入(删除),然后上溯维护树高.
首先完成节点插入,上溯修复过程在不改变当前节点的高度或完成旋转后退出而不是上溯到根节点.
容易证明旋转后近根节点的高度不会改变其父节点的高度.其insert和delete操作中旋转操作中的
节点改变操作不同.insert的旋转操作更加细化,不证明.
在完成旋转操作或不改变当前节点高度后退出.由于删除操作是我思考出来的,所以主要讲删除操作.
和删除普通二叉搜索树的节点类似,qmj::avl_tree::erase面对四种情况.
第一二种情况比较简单,如果要删除的节点的只有一个子节点,就用这个子节点代替它,关键节点为其 父节点,所谓关键节点就是删除节点后可能改变高度的第一个节点.对于没有子节点的节点可以归为 第一种情况中.
对于有左右子树的节点,取其右子树中的最小节点代替它.此时分为三四种情况. 对于右子树中最小节点为其右节点视为情况三.让其右节点代替它.与第一二种 情况的不同之处在于此时关键节点不是删除节点的父节点而是其右节点.
第四种情况较为复杂.其右子树中的最小节点right_min不是其右节点.首先让right_min的右节点代替
right_min,然后让right_min代替要删除的节点,此时关键节点为right_min的父节点,注意是right_min
的父节点而不一定是要删除节点的右节点.
qmj::avl_tree能够达到和qmj::multiset相同的性能,当然,qmj::avl_tree没有封装带来的间接性.
splay_tree适用于需要多次查找最近查找过得元素,因为每次find后会将最接近查找元素的树 中元素上升到根节点,平摊时间为O(lgn).splay_tree占用的内存较小.和双向链表相当.由于不能 保证是平衡树,所以遍历是使用递归可能栈溢出,特别是数据量较大时.我写了一个"一次性"遍历 算法,因为会破坏树的结构,但因为只是用在析构上,所以是否一次性无所谓.具体思想是将栈结构 组织到树上.
比std::vector快的原因在于std::vector使用new对于预分配的内存
会全部进行构造,而qmj::vector只构造qmj::vector::size大小的内存.
算法复杂度,摊还时间为O(1).
1.slist不是单向链表,list继承自slist,不同之处在于slist::splice
复杂度O(1),slist::size()复杂度O(n).而qmj::list::splice复杂度O(n),
qmj::list::size复杂度O(1).
2.如果使用一级配置器,链表类容器qmj相对于std没有明显效率改善,使用内存池
分配器后,效率有质的改变.如图
3.list/slist使用回溯归并排序iterator merge_sort(first,last,len,cmp),
返回值为排好序区间的首迭代器.forward_list也使用了归并排序
std::deque架构较为复杂,其中map是指向block(区块)的映射表,也就是指针的指针,
根据单个value_type的数据大小来指定区块所存元素个数.当需要在首尾插入数据时,就将
map的首尾指针指向区块地址.
qmj::deque限定map的指针映射一个数据元素而不是一个区块,如果需要在中间插入元素
qmj::deque能获得更高的性能,因为qmj::deque只需要使用memcpy移动map中的指针,
而std::deque需要对元素进行赋值之外,迭代器的遍历涉及的控制流和计算也会拖慢速度.
对比qmj::deque和std::deque.
1.当单个元素的大小较大时,如果qmj::deque不使用内存池配置器,qmj::deque在首尾插入
元素没有明显提高,但如果使用内存池分配器,速度会快上很多.
deque 非POD数据测试
2.当元素较小时,如果qmj::deque不使用内存池配置器,为一个较小的元素单独分配和释放内存,
花费的开销太大,速度比std::deque慢上很多.(使用内存池配置器后又会快上很多)
3.在中间插入和删除元素或者排序,qmj::deque要比std::deque快.对于排序,特意为
qmj::deque_iterator设计了iter_swap,因为qmj::deque只用交换map中的指针.
当元素大小较小时,不使用内存池分配器的qmj::deque处于劣势,所以qmj::deque采用了双层架构,
当元素大小较小或为POD类型时的内存布局采用类似qmj::vector布局,直接使用了qmj::vector的迭代器.
数据移动直接使用memcpy,与qmj::vector的不同之处只在qmj::deque在预分配内存的中间开始使用而不是头部.
deque int数据类型测试
对于qmj::deque的使用和std::deque一致,qmj::deque会自动检测,如果元素小于一个指针的大小
或者该元素为POD类型并且小于10个指针的大小时会自动调用qmj::vector模型的deque.
怎么检测在后面的type_traits会说明.但对于数据较大的POD类型数据使用qmj::vector排序会
较慢.使用qmj::deque<value_type,Alloc,value_type>模式会强制调用映射模型的qmj::deque.
std::priority_queue包含一个容器,主体算法都来自algorithm.std::pop_heap,
std::push_heap.我也写了同名算法,不过在qmj::binary_heap里重新写了一遍.
与std的不同之处在于pop_heap算法.
std::pop_heap算法将top(root)元素移出后,通过迭代下溯从子树元素提取元素填补洞口,
最后在叶子节点会空出一个洞口,然后以该洞口洞号开始为尾端元素上溯使用std::push_heap
找到合适洞口.
qmj::pop_heap算法使用的heapify(堆维护)算法则直接在下溯中为尾端元素找到洞口,
而没有再使用一次push_heap上溯.但跌代体中会多出一个控制流.
pop_heap算法分析,因为尾端元素原本就是叶节点,所以它的优先权重较小,更有可能就在底层
找到洞口,而且由于二叉堆是满二叉树,大部分数据就在底层(2^n-1个元素的满二叉树的叶节点
占总体元素一半),所以综合来看std::pop_heap堆更合理.
经过测试,对于随机数据,两者速度没有明显差异.但对于具有较多重复
元素的数据,qmj::priority_queue(继承自qmj::binary_heap)快10%左右.
对于随机数据qmj::make_heap比std::make_heap快20%,对于完全重复或降序数据快80%.
增序无较大差异.
对于随机数据qmj::sort_heap和std::sort_heap无明显速度差异,对于有序数据(增序/降序)
qmj::sort_heap要快,而对于重复数据.如图
对重复或增序数据较快的原因在于改进的heapify(堆维护算法)复杂度变成了O(1)
斐波那契堆主要用于优化后面的图算法,和binary_heap相比,传入小于比较符是最小堆,
隐藏在其中的常数非常大.是其9倍左右.
qmj没有完成的函数有equal,copy,copy_backward,fill等,
原因在于看了std源码以后发现这些算法已经优化到了极致,
重写一遍还要造很多型别判定的轮子,可能后面会补上.
qmj::power(x,n,fn2)是非标准算法.
该算法返回对x进行fn2操作的n幂次方,fn2要满足结合律而
不需满足交换律,其中n必须是非负整数,复杂度O(lg(n)).
template<typename value_type,
typename UnsignInteger,
typename Fn2>
value_type power(value_type x, UnsignInteger n, const Fn2& fn2)
{//N=(2^a)*b
if (n <= 0)
return (x);
for (; !(n & 1);)
{//循环a次
n >>= 1;
x = fn2(x, x);
}
value_type result = x;//result=X^(2a),n==b
for (n >>= 1; n != 0; n >>= 1)
{
x = fn2(x, x);
if (n & 1)
result = fn2(result, x);
}
return (result);
}
证明假设fn2为乘法操作,其伪代码循环体中的if语句下面的语句应有一个缩进
qmj::iter_swap在文件algorithm.h中. 将两个迭代所指的对象对调,不同于std::iter_swap, qmj::iter_swap首先判定两个迭代是否是同类类型, 不是同类型直接调用std::iter_swap,是同类类型然后判断 迭代器是否有自定义的成员函数iter_swap,如果没有调用 std,否则调用成员函数.
Assume:
void mySwap(first1,last1,first2,last2)
{//_QMJ distance(first1,last1)=_QMJ distance(first2,last2)
for(;first!=last1;++firs1,++first2)
_QMJ iter_swap(first1,first2);
}
len1=_QMJ distance(first,mid);
len2=_QMJ distance(mid,last);
template<typename FIter>inline
void _rotate_imple(FIter first, FIter middle,
FIter last, std::forward_iterator_tag)
{
for (FIter mid = middle;;)
{
_QMJ iter_swap(first++, mid++);
if (first == middle)
{
if (mid == last)
return;
middle = mid;
}
else if (mid == last)
mid = middle;
}
}
1.len1=len2
mySwap(first,mid,mid,last)
完成
2.len1<len2
rotate(first,mid,last)=mySwap(first,mid,mid,mid+len1)+rotate(mid,mid+len1,last)
3.len1>len2
rotate(first,mid,last)=mySwap(first,first+len2,mid,last)+rotate(first+len2,mid,last)
花费为mySwap调用的次数和区间的长度的乘积,
容易证明每次区间的长度为非递增状态,
因为每次调用两个区间的的较短区间长度,然后较长区间要减去
较小区间的长度.
0<α<1/2,假设整个区间长度为n,某个区间的长度为αn,
最多调用n/(αn)次,每次调用最多花费αn,复杂度为n/(αn)*αn=O(n).
template<typename BIter>inline
void _rotate_imple(BIter first, BIter middle,
BIter last, std::bidirectional_iterator_tag)
{
_QMJ reverse(first, middle);
_QMJ reverse(middle, last);
_QMJ reverse(first, last);
}
先完成两个区间的反转,最后对整个区间反转
1.len1=len2
mySwap(first,mid,mid,last)
完成
2.len1<len2
rotate(first,mid,last)=mySwap(first,mid,mid,mid+len1)+reverse(mid,last-len1)
3.len1>len2
rotate(first,mid,last)=mySwap(first,first+len2,mid,last)+reverse(first+len2,mid)
O(n)
对于随机存储迭代器,由于测试 <<stl源码剖析>> 的速度没有直接使用 双向迭代器的快,所以不证明.
求序列的下一个(上一个)排列.
首先,从最尾端开始往前寻找两个相邻元素,令第一元素为
*i,第二元素为*ii,且 满足*i<*ii.找到这样一组相邻元素后,再从尾端开始往前检验,找出第一个大于*i的元素,令为*j,将i,j元素对调,再将ii之后的所有元素颠倒排列,此即所求之 "下一个"排列组合. -------- <<stl源码剖析>>
假设一个序列的每一个元素是非递减的,它的最后一个排列一定是非递增的. 这两者之间的排列一定是严格递增的
0 1 2 3 4 0 1 2 4 3 0 1 3 2 4 0 1 3 4 2 ... 4 3 2 1 0
所谓下一个排列亦即重新排列元素,并使整个序列表示的数字增长最小的排列.
要使元素增长最小自然从最低位开始向高位开始查找.
图中区间S中的元素由于是严格递减的(从左往右),不可能
重新排列这个区间的元素使序列变大.所以要替换*i.
从后向前找到的第一个不小于(对于有重复元素的序列)*i的元素*j.
根据单调性,*j一定是在区间S中最接近*i的.交换*i和*j后区间S仍然是
严格递减的.再将区间S颠倒便得到区间S所能组成的最小序列.
将接受的区间随机重排,也就是在N!中可能的元素序列中随机选择一种. qmj并没有重新实现这一个函数.
template<typename RIter>inline
void random_shuffle(RIter first,RIter last)
{
_QMJ iter_dif_t<RIter> len=last-first;
if(len<2)
return;
for(_QMJ iter_dif_t<RIter> i=1;i!=len;++i)
_QMJ iter_swap((first+i),first+(rand()%(i+1)));
}
只需证明len个元素在每个位置的概率都相同,为1/len.
循环不变式:在每次循环体开始之前,序列前i个元素在前i个位置任一位置的概率都为1/i.
初始时:i=1,第一个元素在第一个位置的概率为1/i=1,条件成立.
保持:第i次循环体结束后,前i+1个元素在前i+1个位置任一的概率都为1/(i+1).
由初始条件可知,前i个元素在前i个位置中任一位置的概率为1/i.在循环体
结束后,前i个元素中每个元素还在原位置的概率为(1/i)*(i/(i+1))=1/(i+1).
其中i/(i+1)为该元素未被选中交换的概率.前i个元素中每个元素在第i+1个位置的概率
和第(i+1)个元素在前(i+1)个位置中某个位置的概率都为1/(i+1).
综上,前i+1个元素在前i+1个位置任一的概率都为1/(i+1).
终止:i=len,此时len个元素在len个位置中任一位置的概率都为1/len.
template<typename RIter,
typename Comp>inline
void partial_sort(RIter first, RIter middle, RIter last,
const Comp&cmp)
{
iter_dif_t<RIter> len = middle - first;
if (!len)
return;
else if (len == 1)
{
_QMJ iter_swap(first, _QMJ min_element(first, last, cmp));
return;
}
_QMJ make_heap(first, middle,cmp);
for (RIter cur = middle; cur != last; ++cur)
if (cmp(*cur, *first))
{
iter_val_t<RIter>val = std::move(*cur);
*cur = std::move(*first);
_QMJ _heapify(first, iter_dif_t<RIter>(0), len, std::move(val), cmp);
}
_QMJ sort_heap(first, middle,cmp);
}
该函数使序列中的middle-first个最小元素以cmp制定的顺序排序置于[first,middle)内,
其余last-middle个元素安置于[middle,last)中,不保证有任何特定顺序.以下假设cmp为小于
比较符.
该函数首先对[first,middle)造堆,此时其中的最大元素位于first,然后遍历[middle,last),
如果有元素小于*first,就交换两者,然后维护堆.最后调用堆排序对[first,middle)排序.
以下假设cmp为小于比较符.
循环不变式:每次循环体开始之前,*first是[first,cur)个元素中第middle-first小的元素.
由堆的性质可知[first,middle)是[first,cur)中middle-first个最小的元素.
初始时:make_heap(first,middle),条件显然成立.
保持:循环体结束后,*first是[first,cur)个元素中第middle-first小的元素.
由堆的性质[first,middle)是[first,cur)中middle-first个最小的元素.
如果*cur>=*first什么都不做,循环不变式得到保持.
否则交换*first,*cur,然后维护堆的性质.此时*cur将成为新的第middle-first小的元素.
[first,middle)是[first,cur)中middle-first个最小的元素.循环不变式得到保持.
终止:cur=last.*first是[first,last)个元素中第middle-first小的元素.
由堆的性质[first,middle)是[first,last)中middle-first个最小的元素.
令k=middle-first,n=last-first,首先make_heap花费O(k),最坏情况下后面循环体中每个元素
都比*first小,将花费O((n-k)*lg(k))来找出k个最小元素.最后sort_heap花费O(k*lgn(k)),
所以整个算法的复杂度为O((n-k)*lg(k)+k*lgn(k)+k)=O(n*lg(k)).
qmj::sort 采用了introSort,主体采用循环加递归的快速排序.如果递归恶化(深度过深)会采用
堆排序,如果序列长度低于阈值退出.最后对整个序列进行插入排序.以下是测试结果.
随机不重复int数据
有序(增序/降序)不重复数据*
完全重复数据
qmj::sort在不重复数据比std::sort表现更好的一个原因在于
template<typename RIter,
typename Comp>inline
RIter _mid_partition(RIter first, RIter last,
const Comp&cmp)
{
iter_val_t<RIter> piovt = _get_piovt(
*first, *(first + ((size_t)(last - first) >> 1)), *(last - 1), cmp);
for (;; ++first)
{
for (; cmp(*first, piovt); ++first)
;
for (--last; cmp(piovt, *last); --last)
;
if (!(first < last))
return (first);
_QMJ iter_swap(first, last);
}
return (first);
}
在两个比对piovt循环体中没有边界检查,节省了很多常数时间.但这也是qmj:sort在面对完全重复数据时
表现不如std::sort的原因.std::sort的mid_partition返回一个pair表示piovt的所在区间.当数据
完全重复时std::sort复杂度为O(n).而qmj::sort的mid_partition要做很多无用的交换.
经过测试,即使序列有超过一半的重复的元素,但如果序列是随机排列的qmj::sort还是比std::sort
具有更好的性能.
for (; cmp(*first, piovt); ++first)不需要边界检查的原因在于piovt是区间中的一个元素.
该循环一定会在越界之前停下来.第二个循环也是如此.而后检查两个迭代器的位置,如果不满足
要求直接返回.而满足要求后会交换两个对象,一旦交换后就很显然不需要担心越界问题了.
qmj::sort对递归深度有限制,一旦递归恶化(复杂度偏向O(n^2))便调用堆排序.保证了复杂度O(nlgn),
对于最后进行的一次插入排序,也可证明是O(n)的.原因在于原序列被划分成了不大于阈值的若干个区间,
每个区间的元素虽然不一定是有序的,但该区间与其他区间是独立的,该区间的元素是整个序列有序后该区间
元素的一个排列.这便保证了插入排序内层循环的花费不会超过阈值,内层循环为常数时间,插入排序复杂度O(n).
整个算法的复杂度O(nlgn).
qmj::stable_sort 采用归并排序和插入排序,当序列长度大于阈值时采用归并排序, 否则使用插入排序.qmj::stable_sort需要使用缓冲区.在有序(升序/降序)或重复元素 较多时比std::stable_sort更快.
qmj::stable_sort接受的比较符对应的有序区间和完全重复元素比std::stable_sort快50%, 逆序快40%,随机数据没有明显提高.
正序或完全重复元素
逆序
随机不重复数据
template<typename FIter,
typename Dif,
typename value_type,
typename Pred>inline
FIter _search_n_imple(FIter first, FIter last,
Dif n, const value_type&val, const Pred&pred,
std::random_access_iterator_tag)
{
if (n <= 0)
return (first);
iter_dif_t<FIter> count = last - first;//size of [first,ast)
FIter result = first;//may be result
for (Dif mark = n - 1; mark < count; mark += n)
{
if (pred(first[mark], val))
{//[ret,first+mark] may be satisifyed
for (Dif cur = 0;; ++cur)
if (cur == n)
return (result);
else if (!pred(result[cur], val))
{//adjust mark
mark -= (n - cur - 1);
break;
}
}
result = first + mark + 1;//update ret
}
return (last);
}
不同于<<stl源码剖析>>的代码.我使用其代码和std进行测试后发现要慢很多.
那std一定使用了完全不同的方法,经过一段时间的调试我写出了这个算法.最后和
std比对,虽然没有理清源码,但从注释上看它使用了和我一样的算法.我自认为
我的代码比std源码更加简洁.
假设pred为等于操作符:
因为是随机迭代器,首先记录可能的序列首元素位置为result,而后测试这个可能序列
的最后一个元素的下标为mark,如果mark与val不等,表明result到(first+mark)的元素
不可能为所求结果,跳跃调整result=first+(mark+1),mark+=n.重新进行以上测试.
如果mark所指向的元素与val相等,便开始测试[result,first+mark],如果里面的值全为
val便返回result.否则记不等于val的元素距离result的相对距离的为cur,
首先调整mark到cur所指元素到first的绝对距离,这里之所以不能远距离跳跃的原因在于
虽然result不是符合区间的首元素,但是[result,first+mark](里面的mark为未调整前的)
可能具有符合条件的首元素.
期望复杂度可以达到O(n/k+k).其中n为序列的长度,k为查找的长度.