map，hash_map
They are implemented in very different ways.
hash_map (unordered_map in TR1 and Boost; use those instead) use a hash table where the key is hashed to a slot in the table and the value is stored in a list tied to that key.
map is implemented as a balanced binary search tree (usually a red/black tree).
std::set and std::map are usually implemented as red-black trees
只要能给自定义数据结构指定选择一个良好的key，就可以插入。并且插入自定义数据结构仅和选择的key有关，和自定义数据结构无关。
对于map而言，STL 默认提供了 int，char*,string等作为key。 当选择int, char*，string等的时候，直接使用即可。
对于hash_map而言，STL默认提供了 int, char*作为key；STL提供了这些key的hash函数和==比较函数。
但是若要使用自定义的key呢？
自定义Key需要满足什么要求呢？
对于map而言，自定义key需重载<算符。满足可以比较大小。因为map内部使用红黑树实现，插入节点时需要比较大小。 STL为map默认提供了int，char*,string这些类型的比较大小函数。 对于hash_map而言，自定义key需满足： 1）重载()算符，并返回int行的hash函数 2）重载==算符。当发生hash冲突时，或查找时有用。 STL为hash_map默认提供了 int, char*作为key；STL提供了这些key的hash函数和==比较函数。 也就是说，如果你的key使用的是以上类型中的一种，你都可以使用缺省的hash函数。当然你自己也可以定义自己的hash函数。对于自定义变量，你只能如此，例如对于string，就必须自定义hash函数。例如： struct str_hash{ size_t operator()(const string& str) const { unsignedlong __h = 0; for (size_t i = 0 ; i < str.size() ; i ++) __h = 5*__h + str[i]; return size_t(__h); } }; //如果你希望利用系统定义的字符串hash函数，你可以这样写：struct str_hash{ size_t operator()(const string& str) const { returnreturn __stl_hash_string(str.c_str()); } };
They are implemented in very different ways.
hash_map (unordered_map in TR1 and Boost; use those instead) use a hash table where the key is hashed to a slot in the table and the value is stored in a list tied to that key.
map is implemented as a balanced binary search tree (usually a red/black tree).
std::set and std::map are usually implemented as red-black trees
只要能给自定义数据结构指定选择一个良好的key，就可以插入。并且插入自定义数据结构仅和选择的key有关，和自定义数据结构无关。
对于map而言，STL 默认提供了 int，char*,string等作为key。 当选择int, char*，string等的时候，直接使用即可。
对于hash_map而言，STL默认提供了 int, char*作为key；STL提供了这些key的hash函数和==比较函数。
但是若要使用自定义的key呢？
自定义Key需要满足什么要求呢？
对于map而言，自定义key需重载<算符。满足可以比较大小。因为map内部使用红黑树实现，插入节点时需要比较大小。 STL为map默认提供了int，char*,string这些类型的比较大小函数。 对于hash_map而言，自定义key需满足： 1）重载()算符，并返回int行的hash函数 2）重载==算符。当发生hash冲突时，或查找时有用。 STL为hash_map默认提供了 int, char*作为key；STL提供了这些key的hash函数和==比较函数。 也就是说，如果你的key使用的是以上类型中的一种，你都可以使用缺省的hash函数。当然你自己也可以定义自己的hash函数。对于自定义变量，你只能如此，例如对于string，就必须自定义hash函数。例如： struct str_hash{ size_t operator()(const string& str) const { unsignedlong __h = 0; for (size_t i = 0 ; i < str.size() ; i ++) __h = 5*__h + str[i]; return size_t(__h); } }; //如果你希望利用系统定义的字符串hash函数，你可以这样写：struct str_hash{ size_t operator()(const string& str) const { returnreturn __stl_hash_string(str.c_str()); } };
发表于 2014-10-25 00:26:04
回复(1)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
冯诺依曼理论的要点是：数字计算机的数制采用二进制；计算机应该按照程序顺序执行。
其主要内容是：
1.计算机由控制器、运算器、存储器、输入设备、输出设备五大部分组成。
2.程序和数据以二进制代码形式不加区别地存放在存储器中，存放位置由地址确定。
3.控制器根据存放在存储器中地指令序列（程序）进行工作，并由一个程序计数器控制指令地执行。控制器具有判断能力，能根据计算结果选择不同的工作流程。