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

确实clear()被指定为采用线性时间，复杂性要求是根据容器中的元素数量。但更准确地说：复杂性要求指定了对容器元素的操作数。例如，如果一个容器包含 1 个元素，那么容器在clear()被调用时可以对该元素执行的操作数量必须有一个恒定的上限。但是除了这样的操作，容器可以在“簿记”上花费多少时间是没有限制的。因此，clear()对于基于散列的容器来说，很有可能在不违反标准的情况下花费与桶数成线性关系的额外时间。

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