c++ - 为什么 unordered_set 使用的内存比它包含的数据多得多？

Question

我有一个相对较大的文件，我需要确保只包含唯一的行。该文件只有 500MB。我知道有很多开销，但我看到了将近 5GB 的 RAM 使用率。我本可以使用外部合并排序并保持少量 RAM 来完成此操作，但这似乎可以更快地编写代码。

我正在使用 VC++14。

#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_set>

using std::vector;
using std::string;
using std::unordered_set;

class uniqify {
    unordered_set<string> s;
public:
    auto exists(const string &filename) const -> bool {
        std::ifstream fin(filename);
        bool good = fin.good();
        return fin.close(), good;
    }

    void read(const string &filename) {
        std::ifstream input(filename);
        string line;
        while (std::getline(input, line))
            if (line.size())
                s.insert(line);
    }

    void write(const string &filename) const {
        std::ofstream fout(filename);
        for (auto line : s)
            fout << line << "\n";
        fout.close();
    }
};

int main(int argc, char **argv) {
    uniqify u;
    string file("file.txt");
    if(u.exists(file))
        u.read(file);
    u.write("output_file.txt");
    return 0;
}

是什么导致 RAM 飙升 10 倍以上？

Answer 1

unordered_set 是一个基于节点的容器。上次我检查时，MSVC 使用双向链表存储元素，并将迭代器 vector 放入该链表中以描述存储桶。 unordered_set 的默认 max_load_factor() 为 1，因此至少有多个桶作为节点。它在每个桶中存储了大约一个 list 迭代器——这是一个指针。因此，对于每个节点，您有来自双向链表的两个指针的开销，加上至少一个来自桶的指针，总共三个指针。

然后 std::string 在上面添加它自己的开销。我相信 MSVC 的 std::string 是两个指针 + 16 个字节 SSO buffer .超过 15 个字符的字符串将使用动态分配，这会花费更多。

因此集合中的每个字符串至少需要 5 个指针 + 16 个字节的 SSO 缓冲区，每个指针 8 个字节，即每个字符串最少 56 个字节。有 5500 万个字符串，大约有 3GB。我们没有计算超过 15 个字符的字符串，也没有计算每个节点的内存分配开销，这很容易达到 5GB。