unordered_map vs map vs array - 内存分析

Question

正如标题所说，我想知道unordered_map、map、 和之间的内存差异array。

例子：

unordered_map <long long , int> a;
map <long long , int> b;
long long c[1000000];

a并b有1000000个存储元素。

我想让它尽可能简单。我在互联网上搜索并没有找到正确的答案。我发现它map比unordered_mapan 使用更多的内存array，但我不知道如何处理它。

编辑：如何处理内存差异，比如如果我存储完全相同的两个元素，内存差异是什么。

Answer 1

从 C++11 开始，标准库容器支持有状态分配器：您可以传递记录分配的数据量并跟踪最大使用量的分配器类型。您还需要考虑对象大小，因为对于数组来说，xe2x80x99t 并不是真正的分配器，因为数组是内置实体。

\n\n

这是一个例子：

\n\n

#include <iostream>\n#include <functional>\n#include <memory>\n#include <map>\n#include <unordered_map>\n#include <vector>\n\nusing namespace std;\n\nstatic constexpr long total_size = 1000000;\n\ntemplate<typename T>\nclass CountingAllocator\n{\npublic:\n    shared_ptr<size_t> d_max = make_shared<size_t>(0u);\n    using value_type = T;\n    using pointer = T*;\n\n    CountingAllocator() = default;\n    template <typename S>\n    CountingAllocator(CountingAllocator<S> const& other): d_max(other.d_max) {}\n    size_t size() const { return *d_max; }\n    T* allocate(size_t size) {\n        size *= sizeof(T);\n        *d_max += size;\n        return reinterpret_cast<T*>(operator new(size));\n    }\n    void deallocate(void* ptr, size_t) {\n        operator delete(ptr);\n    }\n    friend bool operator== (CountingAllocator const& c0, CountingAllocator const& c1) {\n        return c0.d_max == c1.d_max;\n    } \n\n    friend bool operator!= (CountingAllocator const& c0, CountingAllocator const& c1) {\n        return !(c0 == c1);\n    }\n};\n\ntemplate <typename T>\nvoid size(char const* name) {\n    CountingAllocator<typename T::value_type> allocator;\n    T m(allocator);\n    for (int i = 0; i != total_size; ++i) {\n        m[i] = i;\n    }\n    cout << name << "="  << allocator.size() << "\\n";\n}\n\nint main() {\n    size<map<long, long long, less<int>, CountingAllocator<pair<long const, long long>>>>("map");\n    size<unordered_map<long, long long, hash<long>, equal_to<long>, CountingAllocator<pair<long const, long long>>>>("unordered_map");\n    cout << "array=" << sizeof(long long[total_size]) << "\\n";\n    return 0;\n}\n

\n\n

使用 ideone 上的 clang 打印此内容（不过，我在这里对齐了尺寸）：

\n\n

map=          48000000\nunordered_map=40654880\narray=         8000000\n

\n\n

当然，数组的占用空间最小（每个元素开销为零）。我\xe2\x80\x99m 惊讶地发现，每个元素的平均开销比 更unordered_map小map。除了数据之外使用 5 个字似乎有点过多。

\n