C实现区别地图和unorderd_map

我正在重写一个小的C++程序为普通的C，它是非常简单的程序，它使用map来统计输入中字的出现次数。我使用散列表（包含大小和指向链接节点列表的指针数组）的静态大小。我无法与重写以下部分到CC实现区别地图和unorderd_map

#if 1  // switch between 1 and 0 
# include <tr1/unordered_map> 
    typedef std::tr1::unordered_map<std::string,int> map_t; 
#else 
# include <map> 
    typedef std::map<std::string,int> map_t; 
#endif

我已经使用散列函数主要实现的无序的版本，我用这种方式

#if 1 // switch between 1 and 0 
    int hash_function(const char *key, int size); 
#else 
    #define hash_function(key, size) ....... 
#endif

，但现在我不知道应该怎样该宏看起来像是因为我想要对表进行排序，并且我有静态大小的表。因为我没有使用地图的经验，所以我不知道是否有任何传统的方法来实现这一点。

我有一个使用表格作为二维数组作为简单矩阵的想法，并从上到下逐列填充它。

那么，有没有更好的常规方法呢？

来源

2012-04-22 rivfaader

据我所知，你的缺陷正在超越这个问题。 Maps和unordered_maps解决了完全不同的问题集，并且您试图使无序地图解决（有序）地图问题？ – 2012-04-22 21:15:40

std :: map通常使用与哈希表完全不同的平衡二叉树（例如红黑树）实现，并且当然不使用哈希函数。 – kennytm 2012-04-22 21:16:11

如果你想要订购表格，你不能使用unordered_map – 2012-04-22 21:16:43

有序哈希表的一个非常典型的实现只是一个常规的哈希表，其中有一个额外的链表，它按顺序遍历所有元素。诀窍是每次插入和删除都要正确维护这个链表。哈希函数不需要（需要）改变黑白和有序哈希映射。

你的2D阵列想法的主要问题是它消耗了n*sizeOfHashTable空间，其中大部分空间被浪费了。

如果你正在实现一个有排序的映射，你通常会采用任何有序的数据结构，如二叉搜索树，并让键（这是你所排序的）也具有与它们相关的值。那么你根本不使用哈希函数。

来源

2012-04-22 21:18:53 trutheality

因为它是一个学校作业，我不能添加任何结构/列表，所以我想我必须解决浪费的空间......感谢您的答案 – rivfaader 2012-04-22 21:29:33

C实现区别地图和unorderd_map

回答

相关问题