Почему unordered_set использует значительно больше ОЗУ, чем содержащиеся в нем данные?

Question

У меня есть относительно большой файл, который мне нужен, чтобы содержать только уникальные строки. Файл составляет всего 500 МБ. Я понимаю, что накладных расходов много, но я видел около 5 ГБ оперативной памяти. Я мог бы сделать это, используя внешнюю сортировку слияния и поддерживая небольшой объем оперативной памяти, но это выглядело быстрее, чем код.

Я использую 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; 
} 

В чем причина того, что оперативная память увеличится в 10 раз?

Answer 1

unordered_set - это контейнер на основе узлов. В прошлый раз, когда я проверял, MSVC использует дважды связанный список для хранения элементов и вектор итераторов в этот связанный список, чтобы очертить ведра. По умолчанию max_load_factor() из unordered_set равно 1, поэтому в качестве узлов имеется по меньшей мере множество ведер. И он хранит примерно один итератор list - который является одним указателем - за ведро. Таким образом, для каждого узла у вас есть две накладные расходы из двусвязного списка, плюс по крайней мере один указатель из ведра, для трех указателей.

Затем std::string добавляет свои собственные накладные расходы сверху. MSVC std::string, я считаю, два указателя + 16 байт SSO buffer. Строки длиной более 15 символов будут использовать динамическое распределение, которое стоит больше.

Таким образом, каждая строка в наборе стоит как минимум 5 указателей + буфер с буфером 16 байт, по 8 байт на указатель, что 56 байтов на строку минимально. С 55-миллиметровыми струнами размером около 3 ГБ. И мы не учитывали более длинные, чем 15-символьные строки, а также накладные расходы на память для каждого узла, что может легко довести его до 5 ГБ.

Answer 2

Накладные расходы связаны с данными, независимо от того, какая реализация предоставляется поставщиком вашего компилятора C++.

Если вы следуете дискуссиям в this question других подобных объектов, вы обнаружите, что большинство поставщиков, скорее всего, будут использовать хэш-таблицы для реализации неупорядоченного набора, а хеш-таблицы должны быть изменены и расти смешными способами, если у вас есть значительное количество записей добавляется динамически. Вы должны выделить таблицу в нужном размере спереди, а не рассчитывать на динамическое изменение размера.

Однако это просто предположение, поскольку я не знаю, какая реализация используется в вашей системе.