关于list和vector的一点点试验

免费打工仔

map 是红黑树
hash_map 是哈希表
hash_map查找比较快

vector内存是连续储存的 插入和删除需要拷贝内存数据
而list不用 插入删除list比较快
因为我是用来储存每个角色当前的任务的
所以 应该不大 所以不考虑 o(n)这样的影响  因为n不会很大

tarkey

呵呵，说别人前先审视下自己。

你所说的“前提条件”，无非不过在搜索或者插入的时候，是否给出指针位置而已。sgi-stl里面是有hash_map和hash_set的。你要用vector或者list来查找，那没什么可怀疑的，就是O(n)了。当然，你可以argue说插入的时候排序等等之类的，无论如何提高速度，都不可能提高到和HASH表一样的O(1)的速度，最多是O(logn)。

如果你对此有什么疑问的话，尽管举例来讨论，而不是什么都不说的指指点点。另外你的猜测也错了，我不是刚毕业的：）

知川内酷

呵呵
这个以后看了数据结构才能理解

免费打工仔

我想到一句话
“我使用最适合我的，而不是最好的”
vector 和list 的存在都有其价值的
每个版本stl实现也不同， 我有人说vs.2003的hash_map就不很好
效率不高
我本人是拿来主义 基本上很少分析里面的具体结构的
我默认大师们已经做得足够好了。

知川内酷

呵呵
本帖还是很有用的
只是我占时看不懂，1个月后再杀回来@_@嘎嘎

kypck

to tarkey:
真不好意思，开始你没正面回答我的问题，我还以为你是不懂装懂呢。我不知道你说的map就是指的hash_map，因为当前为止hash_XXX还没有列入C++标准，所以说起map我的第一反应还是标准中的那个用红黑树实现的版本，它的那几个insert函数在不同的情况下效率的确是会在O(1)和O(logN)之间变化，如果是hash_map那就象你说的都是时间常量了。另外你说"vector的实现原理跟list一样，都是链表"，我想肯定是笔误，你肯定是想表达：他们都是线形数据结构。
你今年大几了？我还有一年毕业。

知川内酷

。。。。。。。。。。。

kypck

to 免费打工仔:
你说的没错，用最适合需求的东西。比如在对数据的随机访问速度要求很敏感的场合，只要插入/删除/随机访问等不是在某一段里同时使用，就可以尽量的多用vector。其实想了解stl的细节你只需要有足够的耐性去看stl的源码，毕竟那就是在手边的最好的学习资料。

tarkey

我刚开始上大学，以前没读书，在网络游戏公司工作。
我主要是做服务器的，在LINUX系统下编程较多，以前一直都是用的C，去年开始才慢慢的往C++转，对C++的一些标准确实不太熟悉。

知川内酷

楼上的是牛人
有技术 有工作经验
我的偶像