3d Game Walkman

3d图形渲染,网络引擎 — tonykee's Blog
随笔 - 45, 文章 - 0, 评论 - 309, 引用 - 0
数据加载中……

今天找到一个不得不用deque的理由

过去总以为vector和deque差不多,效率方面deque和vector接近,那干脆用效率高的vector好了。
但我忽略了另一方,一个事务存在就有它的理由,今天找到程序里面隐藏的bug给了我不得不用deque的理由,
deque和vector的结构很类似,但它是多段连续空间,如果vector空间不够的时候,要重新分配空间,并把所有的数据复制到新的空间中去,
deque不会这么做,它会去另外开辟一块连续空间去存放数据,所以存储效率方面deque高于vector,但deque又不同于链表,它可以说是顺序存储结构和链式存储结构的一个折中方案把,今天我写了段代码,是这样的结构

vector<SerializedEntity> archiveEntities; //也许你要问问什么不用vector<SerializedEntity*>,我这里比较特别,因为要读写磁盘的数据,序列化存储                                            //回避了指针的数据读写方式,所以用的vector<SerializedEntity>
那么:Entity * ent = &archive[0];          //看似没问题,其实里面暗藏杀机
这个archiveEntities 如果不改变是没有问题,但如果序列集又动态添加了数据,恰好没有预留空间,那么将导致整个集合重新分配连续空间了,所以那个引用也将“失效了”,这让我很头疼,这个时候让我想起了deque,它真的很棒,不会去重整空间,需要的时候再开辟其他连续的空间,虽然读的效率降低了,但
这点损失对于我的程序基本可以忽略不计的,IO数据本身就很少去遍历访问,却能给程序很好的去“引用”,不用担心引用失效的情况,这方面deque确实是个很好的选择
找到一篇文章与大家分享一下,也是应证我的观点的:

operator[]

  operator[] 是指通过下标取数据。显然 list 的复杂度为O(N),非常慢。而 vector、deque 均为 O(1)。让我们想象下 deque::operator[] 的实现:

 

 _E deque::operator[](int i)
{
  return m_storage[i/BlockSize][i%BlockSize];
} 

 

  可以看出,deque 只比 vector 多了一次内存访问。

  空间性能分析

  push_back

  vector

  很不幸,如果 vector 采用 N*2 的内存增长模型(通常如此),那么在最差的情况下,空间复杂度就是 2*N ,最好的情况下为 N(所有的内存都用上了)。平均来讲,空间复杂度为 1.5*N .也就是说,通常差不多有一半的内存是被浪费的。

  list

  list 的空间浪费与 vector 相比不遑多让。它的空间复杂度为 (1 + sizeof(pointer)*2/sizeof(_E))*N.如果我们让 list 存储的元素为 pointer(即 _E = pointer),那么空间复杂度为 3*N,比 vector 还浪费。

  deque

  deque 的最差情况下的空间复杂度为 N + sizeof(pointer)*2*N/(BlockSize*sizeof(_E))(这里假设vector也采用 2*N 增长模型,平均复杂度则将式中2改为1.5即可)。如果我们保存的元素为 pointer(即 _E = pointer),并且BlockSize取512,那么空间复杂度为 N + N/256.也就是说最差情况下只浪费了 N/256 的内存。

  deque的其他特性

  元素地址不变

  由于 deque 并不进行数据搬移,带来一个有意思的特性,就是 deque 的元素地址在只有 push_back/push_front,没有 insert/erase 时,可保持元素地址不变。

  需要注意的是,vector 并不具备这样的特性。如下的代码是不合法的:

 

std::vector<int> vec;
...
int& elem = vec[i];
vec.push_back(100);
elem = 99; // error: can't access elem since vec was changed! 

 

  由于取得 elem 之后存在 push_back 操作,所获得的元素地址(&elem)可能会由于内存搬移而失效。但是如果我们将容器换为 std::deque,则这个代码不会有任何问题。

 

 std::deque<int> dq;
...
int& elem = dq[i];
dq.push_back(100);
elem = 99; // ok! 

 

  另外需要注意的是,元素地址不变,并不代表 iterator 不变,如下的代码 deque 并不支持:

 

std::deque<int> dq;
...
std::deque<int>::iterator it = dq.begin() + i;
dq.push_back(100);
*it = 99; // error: can't access iterator since deque was changed!

 

  结论

  通过 vector, list, deque 的时间、空间性能对比,我们可以看出,应该提倡尽可能使用 deque 这个容器。特别是,如果要承受海量数据,deque 是最合适的人选了。


posted on 2009-05-24 13:25 李侃 阅读(8123) 评论(15)  编辑 收藏 引用 所属分类: 杂谈

评论

# re: 今天找到一个不得不用deque的理由[未登录]  回复  更多评论   

只能说你对vector没有认识清楚而以,一般也都使用iterator
2009-05-24 13:36 | 关中刀客

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

我现在讨论的不是迭代,任何集合都能迭代,光用一个iterator去遍历,任何集合都没有差别了。那一个vector就够了还要list和deque做什么?

我现在讨论的是它们的内部结构的差别,根据不同的场景而要用出这些集合的差别才是真道理,楼上看清楚,我现在就是想在外部指针去引用集合内部的元素,就是不想每次访问的时候都去迭代,集合如果只增不减的情况下,用deque是稳定的,而vector是不稳定的,vector存在空间重排,deque不存在空间重排,这是我要阐述的观点
2009-05-24 14:01 | 李侃

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

用deque是稳定的
2009-05-24 15:38 | 九久读书人

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

我试了试,似乎erase中间的元素以后,各元素的地址依然稳定,vc自带的的deque 是这样的,不知道其他版本的deque会不会也是这样?

我已经深深的爱上deque了 ^^
2009-05-24 15:52 | 李侃

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

std::deque<int> dq;
...
int& elem = dq[i];
dq.push_back(100);
elem = 99; // ok!

这样的代码对deque即使正确也还是不要用吧。
2009-05-24 16:55 | 阿淡

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

后面的部分是我摘录网上的文章,觉得好像也没什么不妥
当然了如果元素被移除了,这样去访问那会是危险的。
2009-05-24 17:32 | 李侃

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

个人意见是,不要直接引用容器内的元素地址,特别是长期引用
就算你知道自己在做什么,别人也不知道
2009-05-24 18:01 | LOGOS

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

依赖于一个容器是否分配内存本身就是你的问题,不是该不该vector还是queue的问题。如果想避免分配内存带来的问题,请用vector<shared_ptr<OBJ>>。
2009-05-24 21:25 | 陈梓瀚(vczh)

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

我明白,如果是vector<Entity*>的方式,根本不用去讨论该去用vector还是queue,重排就重排了,指针不会变
但如果是vector<Entity> 的形式情况就不同了

这样的类别的集合确实就不该直接去引用集合中元素的地址,这不是一个好的习惯。

主要是:我的序列化存储层只能支持 集合<entity>的形式
不支持 集合<Entity*>的形式,想引用从文件读取的集合数据又不想做太多的拷贝,迫于无赖。

只好回头再想想看有没有更好的折中方案了。

2009-05-24 22:34 | 李侃

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

不想拷贝又不想自己释放,用智能指针。
2009-05-25 10:28 | 陈梓瀚(vczh)

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

deque 不能 memcpy
2009-05-26 21:21 | lovelypig

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

STL只是一份标准还不是实现,作为vector来讲,它设计目标应该是作为一个大小伸缩的数组,比如&v[0]可以当作一个数组的指针(如果!v.empty()的话),而deque则不行;deque为了能够以常数时间在顺序容器的头部及尾部进行push操作而设计的,但这个设计的代价通常很大,应该并不是你所想像的二维数组的形式,比如SGI的deque设计就采用了一种类似于文件系统中二级表的方式,其直接结果就是迭代器操作的代价很高。现实程序中你会发现很少有人会用deque,这固然有书中介绍比较少的原因,但也与其操作代价较高是分不开的。
我的意见是,除非不得以,否则使用vector而不要用deque;
你的这种情况,我建议你可以自己写一个容器,那怕是用memove,通常也会比std::vector快很多的
2009-08-09 19:58 | 李现民

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

deque用的不当,会造成内存急剧消耗!
2009-09-25 20:39 |

# re: 今天找到一个不得不用deque的理由  回复  更多评论   

本来就是各有所长的设计,vector设计规范就是连续,引用元素说得清清楚楚就是即时有效,不能缓存,你就要违背规范使用,还要说它不好,那是你愚蠢还是它不对呢?
各种容器就是为了满足不同需求设计的,各有所长各取所需,但不要说一个取代另一个的蠢话,如果你觉得要取代了,说明你还认识不够,也说明你起初选择的时候是愚蠢的。
2012-05-10 13:07 | oldworm

# re: 今天找到一个不得不用deque的理由[未登录]  回复  更多评论   

@李侃
STL用迭代器隐藏了线性容器间的区别,但这不代表因此各容器就没区别吧?
每个容器都有自己的特点,不同应用场合性能是有差异的,所以才提供这么多线性表容器吧?
遍历STL线性表还是用迭代器,C语法和C++语法混合起来用是不安全的。
2012-07-06 14:27 | Sine

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理