为什么 unordered_set 使用的 RAM 比它包含的数据多得多？

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

无论您的 C++ 编译器供应商提供哪种实现，数据结构都会产生开销。

如果您关注其他类似性质的讨论，您会发现大多数供应商可能会使用散列 tables 来实现无序集，而散列 tables如果您动态添加了大量条目，则需要重新调整大小并以有趣的方式增长。您应该预先将 table 分配到正确的大小，而不是指望动态调整大小。

但是，这只是一个猜测，因为我不知道您的系统中使用的是什么实现。

Answer 2

一个unordered_set是一个基于节点的容器。上次我检查时，MSVC 使用双向链表存储元素，并将迭代器向量放入该链表中以描述存储桶。 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。

为什么 unordered_set 使用的 RAM 比它包含的数据多得多？

Why does unordered_set use significantly more RAM than data it contains?

c++

unordered-set

c++11