std::unordered_map::clear() 是做什么的？

Question

我有一段简单的代码：

#pragma GCC optimize ("O0")
#include <unordered_map>
int main()
{
    std::unordered_map<int, int> map;
        
    static constexpr const int MaxN = 2e6 + 69;
    map.reserve(MaxN);
    
    int t = 1000;
    while (t--)
    {
        map.clear();
    }
    
    return 0;
}

这段代码所做的只是创建一个巨大的std::unordered_map，在堆上保留大量内存，同时仍然保持它为空，然后清除它 1000 次。令我惊讶的是，执行这个程序需要一秒钟多的时间。

根据 cppreference，std::unordered_map::clear 与 元素数 成线性关系，即 0，而不是桶数。因此，这个函数在我的程序中应该什么都不做，并且应该花费不到一毫秒。

为了进一步分析代码，我写了这个：

#pragma GCC optimize ("O0")
#include <chrono>
#include <iostream>
#include <unordered_map>

#include <map>
template <typename T>
struct verbose_pointer
{
    using element_type = T;
    T* value = nullptr;
    static std::map<T*, std::size_t> accessTimes;   
//  T & operator[](std::size_t n)
//  {
//      ++(*count);
//      return value[n];
//  }
    T * operator ->() const
    {
        ++accessTimes[value];
        return value;
    }
//  T & operator *() const
//  {
//      ++(*count);
//      return *value;
//  }
    static void operator delete(void * ptr)
    {
        T * toErase = (static_cast<verbose_pointer *>(ptr))->value;
        std::cerr << "Deleted " << toErase << std::endl;
        std::cerr << "Address " << toErase << " accessed " << accessTimes[toErase] << " times." << std::endl;
        accessTimes.erase(toErase);
        ::operator delete(toErase);
    }
    verbose_pointer(void* ptr) : value(static_cast <T*>(ptr)) 
    {
        std::cerr << "I'm constructed from pointer: " << ptr << std::endl;
    }
    
    static verbose_pointer pointer_to(T & t) { return verbose_pointer(&t); }
    ~verbose_pointer()
    {
    }
};
template <typename T>
std::map<T*, std::size_t> verbose_pointer<T>::accessTimes;
template <typename T>
class verbose_allocator
{
    public:
        using value_type = T;
        using pointer = verbose_pointer<T>;
        constexpr verbose_allocator() noexcept = default;
        constexpr verbose_allocator(const verbose_allocator & other) noexcept = default;
        template <typename U>
        constexpr verbose_allocator(const verbose_allocator<U> & other) noexcept {}
        pointer allocate(std::size_t n)
        {
            std::cout << (n * sizeof(T)) << " bytes allocated." << std::endl;
            return static_cast<pointer>(::operator new(n * sizeof(T)));
        }
        void deallocate(pointer p, std::size_t n)
        {
            std::cout << (n * sizeof(T)) << " bytes deallocated." << std::endl;
            pointer::operator delete(&p);
        }
};
int main()
{
    std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, verbose_allocator<std::pair<const int, int>>>
        verbose_map;
        
    static constexpr const int MaxN = 2e6 + 69;
    verbose_map.reserve(MaxN);
    
    auto start = std::chrono::high_resolution_clock::now(); 
        
    int t = 1000;
    while (t--)
    {
        verbose_map.clear();
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "1000 clear() runs take " << duration.count() << " milliseconds." << std::endl;
    
    return 0;
}

我的代码的输出是：

8579908 bytes allocated.
I'm constructed from pointer: 0xd09020
1000 clear() runs take 1139 milliseconds.
I'm constructed from pointer: 0xd09020
8579908 bytes deallocated.
Deleted 0xd09020
Address 0xd09020 accessed 1 times.

似乎在 reserve() 语句中分配了一次巨大的内存块，并在映射超出范围时释放了一次，就像我预期的那样。而且，指针只被访问一次。

那么为什么 1000 std::unordered_map::clear() 次操作要花这么多时间？ GCC 的实现在这里做什么？

Answer 1

reserve(N) 对于无序关联容器的定义是它分配足够的桶，使得 table 的负载因子将小于或等于最大负载因子，如果有 N容器中的元素。最大加载因子的默认值为 1，因此 reserve 必须至少分配 2,000,069 个桶。

确实clear()指定了线性时间，复杂度要求是容器中的元素个数。但更准确地说：复杂性要求指定了对容器元素的操作数。例如，如果一个容器包含 1 个元素，那么在调用 clear() 时，容器可以对该元素执行的操作数必须有一些恒定的上限。但是容器除了这些操作之外，还能花多少时间在“记账”上是没有限制的。因此，hash-based 容器的 clear() 很可能会花费与桶数成线性关系的额外时间，而不会违反标准。

我看了libstdc++ implementation of clear()。它执行一次遍历所有元素并销毁它们，然后 memset 将所有桶指针重置为空。所以事实上它 always 需要额外的时间与桶的数量成线性关系，即使这是“不必要的”，因为首先没有元素。因此，您的程序的 1000 clear() 次迭代将使用这样的实现执行至少 2,000,069,000 次操作（假设需要一个操作将一个 pointer-sized 内存位置归零）。

std::unordered_map::clear() 是做什么的？

What does std::unordered_map::clear() do?

c++

unordered-map

std