昨天傻掉了，是策略没搞好

2009-10-01 20:17:00

我作了双向扩充实现。昨天的方案是：

先判断插入的元素靠前还是靠后，靠哪边就准备往哪边挪旧元素，然后检查那头有没有空，没空换另一头，要是都没空但两头加起来却有空，那就重新调整位置，最后才重新分配空间。

我原以为考虑得好周到，可是实现起来却傻了眼。往末尾插入10万数据，有9万多次发生移动元素，不慢才怪。

调整了下，变成：

先判断考前还是靠后，靠哪边就往哪边挪旧元素，如果那头没空，直接重新分配空间，空间按每次*3增长直至足够。

这样，push_back 的性能与 std::vector 以及 std::deque 的粗略比较如下（图中的单位写错了，全是秒）：

insert(begin(), i) 比较：

（vector 参与这项比较果然是不公平的，呵呵）

insert 到 begin + size() / 2 处：

resize 至固定大小，然后用 iterator 遍历赋值：

（今天回家了。以上测试都在家里的机器上做的，配置： AMD SP2500+ 1.4GHz，512MB RAM。）

这样的结果还算满意的。不知道 vector 为什么能保持 push_back 如此高效~

还有个挺奇怪的现象，使用 deque 的时候，如果数据量到百万，临退出前有好长一段时间要等待，难道是 deque 在做某些析构动作？

再呢。。貌似 deque 的 push_front 并没有 vector 的 push_back 神么、、

嗯……我的本意不是为了着重性能，而是尝试些有着那么一套接口的东西出来，同时也给自己用。现在来比性能只是为了论证一下实用程度如何，如此而已。

具体实现代码就不贴了，基本接口和上上篇里没多少变化。等以后这方面的东西做完了再一起拿出来。