c++ - unordered_map 桶的节点大小

Question

我有一个程序，我想在其中存储 kmers(大小为 k 的子字符串)和它们出现的次数。对于这个特定的应用程序，我正在读取一个包含这些值的文件，如果它们出现的次数 > 255，则可以向下舍入到 255。我认为如果我将键值对存储为(字符串, unsigned char) 与将键值对存储为 (string, int) 相比可能会节省空间，但是当我通过运行/usr/bin/time 检查最大驻留大小时，情况似乎并非如此。

为了确认，我还尝试运行以下测试程序，其中我在 unordered_map 中交替使用值的类型:

#include <iostream>
#include <unordered_map>
#include <utility>
#include <string>
#include <fstream>

int main() {
    std::unordered_map<std::string, unsigned char> kmap;
    std::ifstream infile("kmers_from_reads");
    std::string kmer;
    int abun;

    while(infile >> kmer >> abun) {
        unsigned char abundance = (abun > 255) ? 255 : abun;
        kmap[kmer] = abundance;
    }

    std::cout << sizeof(*kmap.begin(0)) << std::endl; 
}

这似乎没有影响存储桶中节点的大小(在我的机器上，它为 unsigned char 和 int 值返回 40)。

我想知道每个桶中节点的大小是如何确定的。

我对无序映射的理解是，c++ 标准或多或少需要单独的链接，并且桶中的每个节点必须至少有一个指针，以便元素可迭代并可被删除(http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html)。但是，我不明白存储值的空间量是如何确定的，而且它似乎也必须灵活以容纳更大的值。我还尝试查看 gcc libstc++ unordered_map header ( https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/unordered_map.h )，但很难理解发生了什么。

Answer 1

编译并执行这段代码:

#include <iostream>
#include <unordered_map>
#include <utility>
#include <string>
#include <fstream>

class foo
{
   std::string kmer;
   unsigned char abun;
};

class bar
{
    std::string kmer;
    int abun;
};

int main() {
    std::cout << sizeof(foo) << " " << sizeof(bar) << std::endl;
}

我明白了，您可能也会明白，40 40。这是因为对齐要求。例如，如果 std::string 包含至少一个指针(几乎肯定是这样)，则它必须至少在 4 字节边界上对齐。

想象一下，如果 sizeof(foo) 是 39，并且您有执行 foo foos[2] 的代码。如果 foos[0].kmer 中的指针正确对齐，则 foos[1].kmer 中的指针就不会对齐。那将是一场灾难。