关于在内存中维护数据结构的有关问题
关于在内存中维护数据结构的问题
我需要在内存中维护一个400W的手机号码名单，需要以尽可能快地速度查询一个号码是否出现在这个名单中，而且该守护程序在启动时从文件系统或者是数据库中一次性加载这400w的号码，然后对外提供服务查询号码是否在这个名单里，在服务期间是只读的，不会有插入新号码的动作.
1.因为是只读的，我查了查书，好像使用插入，删除性能差，但是查找性能很好的avl树比较合适，还不太了解stl中的那些容器都是用什么实现的，所以请兄弟们给看看这种情况是使用stl中的容器合适(使用哪种？)，还是找个avl树的源码改改合适.
2.我简单测试了一下内存占用，插入了400w的不重复的char buf[14],使用了stl中的两种容器:
vector <string> : 大概107M
set <string> : 大概186M
set好像是树，vector是链表吗？为什么vector这个剩地方?
------解决方案--------------------
这样大的数据量,还是用数据库吧...
除非对自己非常有信心或有写数据库的想法.否则,纠缠于这个上意义不大
------解决方案--------------------
set好像是树，vector是链表吗？为什么vector这个剩地方?
------------------------------------------------
set的确是树，而且是一颗平衡树；vector的底层是动态分配的数组，连续存放的。
------解决方案--------------------
为了节省空间使用非链式结构，
为了查询速度快，使用二分查找，同时考虑使用散列技术
------解决方案--------------------
嵌入式内存数据库。。。
------解决方案--------------------
hashset/set/排序vector/排序deque 都可以满足你的要求。优先考虑排序vector吧。
------解决方案--------------------
先对号码进行排序预处理
以后查询采用折半查找
我需要在内存中维护一个400W的手机号码名单，需要以尽可能快地速度查询一个号码是否出现在这个名单中，而且该守护程序在启动时从文件系统或者是数据库中一次性加载这400w的号码，然后对外提供服务查询号码是否在这个名单里，在服务期间是只读的，不会有插入新号码的动作.
1.因为是只读的，我查了查书，好像使用插入，删除性能差，但是查找性能很好的avl树比较合适，还不太了解stl中的那些容器都是用什么实现的，所以请兄弟们给看看这种情况是使用stl中的容器合适(使用哪种？)，还是找个avl树的源码改改合适.
2.我简单测试了一下内存占用，插入了400w的不重复的char buf[14],使用了stl中的两种容器:
vector <string> : 大概107M
set <string> : 大概186M
set好像是树，vector是链表吗？为什么vector这个剩地方?
------解决方案--------------------
这样大的数据量,还是用数据库吧...
除非对自己非常有信心或有写数据库的想法.否则,纠缠于这个上意义不大
------解决方案--------------------
set好像是树，vector是链表吗？为什么vector这个剩地方?
------------------------------------------------
set的确是树，而且是一颗平衡树；vector的底层是动态分配的数组，连续存放的。
------解决方案--------------------
为了节省空间使用非链式结构，
为了查询速度快，使用二分查找，同时考虑使用散列技术
------解决方案--------------------
嵌入式内存数据库。。。
------解决方案--------------------
hashset/set/排序vector/排序deque 都可以满足你的要求。优先考虑排序vector吧。
------解决方案--------------------
先对号码进行排序预处理
以后查询采用折半查找