unordered_map与map与array-内存分析

Question

unordered_map与map与array-内存分析

3

如标题所述，我想了解unordered_map、map和array之间的内存差异。

示例：

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

和各有1000000个存储元素。我想尽可能简单地处理它。我在互联网上搜索了一下，但没有找到合适的答案。我发现map和unordered_map比array使用更多的内存，但我不知道如何处理它。编辑：如何处理内存差异，例如如果我存储完全相同的2个元素，内存差异是什么。

- Sochu

2

“我不知道该如何着手处理它。” 究竟是如何着手处理什么呢？ - undefined

内存映射和无序映射（unordered_map）使用多少内存是一个实现细节。如果你想用大O符号来表示，它们都是等价的。 - undefined

1

你可以实现一个自定义的分配器。它被指定为模板参数，例如 std::vector<int, custom_allocator>。 - undefined

当然，c是最小的，因为它只存储了一半的数据。它存储了1000000个long long实例，而a和b则存储了这些实例加上1000000个int实例。 - undefined

@IgorTandetnik 是的，但我知道存储的元素是相同的。 - undefined

由于您的目标是存储a、b和c的1000000个元素，您可以将数组c仅设置为int类型，并且与其他情况相比，在b中使用键访问元素较慢。 - undefined

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dietmar Kühl · Accepted Answer

自C++11以来，标准库容器支持有状态的分配器：您可以传递一个记录已分配数据量和跟踪最大用途的分配器类型。对于数组，您还需要考虑对象大小，因为数组不是内置实体，因此没有真正的分配器。

这里是一个示例：这里。

#include <iostream>
#include <functional>
#include <memory>
#include <map>
#include <unordered_map>
#include <vector>

using namespace std;

static constexpr long total_size = 1000000;

template<typename T>
class CountingAllocator
{
public:
    shared_ptr<size_t> d_max = make_shared<size_t>(0u);
    using value_type = T;
    using pointer = T*;

    CountingAllocator() = default;
    template <typename S>
    CountingAllocator(CountingAllocator<S> const& other): d_max(other.d_max) {}
    size_t size() const { return *d_max; }
    T* allocate(size_t size) {
        size *= sizeof(T);
        *d_max += size;
        return reinterpret_cast<T*>(operator new(size));
    }
    void deallocate(void* ptr, size_t) {
        operator delete(ptr);
    }
    friend bool operator== (CountingAllocator const& c0, CountingAllocator const& c1) {
        return c0.d_max == c1.d_max;
    } 

    friend bool operator!= (CountingAllocator const& c0, CountingAllocator const& c1) {
        return !(c0 == c1);
    }
};

template <typename T>
void size(char const* name) {
    CountingAllocator<typename T::value_type> allocator;
    T m(allocator);
    for (int i = 0; i != total_size; ++i) {
        m[i] = i;
    }
    cout << name << "="  << allocator.size() << "\n";
}

int main() {
    size<map<long, long long, less<int>, CountingAllocator<pair<long const, long long>>>>("map");
    size<unordered_map<long, long long, hash<long>, equal_to<long>, CountingAllocator<pair<long const, long long>>>>("unordered_map");
    cout << "array=" << sizeof(long long[total_size]) << "\n";
    return 0;
}

在ideone上使用clang编译器，这段代码输出结果如下（我将大小对齐了，不过保留了HTML标签）：

map=          48000000
unordered_map=40654880
array=         8000000

当然，数组的占用空间最小（每个元素没有开销）。我很惊讶使用unordered_map与map相比，平均每个元素的开销更小。除数据外再使用5个字似乎有点过多。