unordered_map 个存储桶的节点大小

Question

我有一个程序，我想在其中存储 kmers（大小为 k 的子字符串）和它们出现的次数。对于这个特定的应用程序，我正在读取一个包含这些值的文件，如果它们出现的次数 > 255，则可以向下舍入到 255。我认为如果我将键值对存储为（字符串, unsigned char) 与将键值对存储为 (string, int) 相比可能节省 space，但是当我通过运行检查最大驻留大小时似乎并非如此 /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). However, I don't understand how the amount of space to store a value is determined, and it seems like it must also be flexible to accommodate larger values. I also tried looking at the 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 中的指针就不会对齐。那将是一场灾难。

unordered_map 个存储桶的节点大小

Node size for unordered_map buckets

c++

unordered-map

memory-alignment