访问容器元素是否耗时？std::map存储GCD结果效率低是否使用有误？

我需要统计整数的最大公约数（GCD）并保存结果，发现耗时环节并非计算GCD，而是将结果存入std::map中。请问我是否错误使用了std::map？同时想了解访问容器元素是否耗时？

测试代码 #

#include <set>
#include <iostream>
#include <chrono>
#include "timer.h"

using namespace std;

int gcd (int a, int b)
{
    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }
    return(a);
}

int main() {
    map<int,int> res;
    {
        Timer timer;
        for(int i = 1; i < 10000; i++)
        {
            for(int j = 2; j < 10000; j++)
                res[gcd(i,j)]++;
        }
    }

    {
        Timer timer;
        for(int i = 1; i < 10000; i++)
        {
            for(int j = 2; j < 10000; j++)
                gcd(i, j);
        }
    }
}

测试结果 #

存储操作耗时6627099us(6627.1ms)，仅计算GCD耗时0us(0ms)。

问题解答 #

你并没有错误使用std::map，但它不适合这个场景 #

std::map本身的设计没问题，但它是基于红黑树实现的有序容器，每次执行res[key]++时会做两件事：

1. 在红黑树中查找对应的键，复杂度是O(log n)；
2. 如果键不存在，会插入新节点，还要维护红黑树的平衡（涉及旋转操作）。

你这里的循环接近1亿次操作，累计起来的开销自然远超过GCD计算。至于仅计算GCD耗时显示为0us，大概率是编译器优化——因为这段GCD计算没有任何输出或副作用，编译器直接把整个循环删掉了，实际GCD还是有耗时，但和容器操作比可以忽略。

优化方案 #

1. 改用std::unordered_map：它是哈希表实现，平均情况下查找和插入的复杂度是O(1)，能大幅降低耗时，对int类型的键来说哈希冲突概率极低，完全适用。
2. 直接用数组统计：这是最优解。因为i和j都小于10000，它们的GCD结果最大不会超过9999，直接用一个大小为10000的数组计数：

   int res[10000] = {0}; // 初始化所有元素为0
   // 循环内直接执行
   res[gcd(i,j)]++;
   

   数组是连续内存直接寻址，没有任何额外开销，速度比任何关联容器都快。

关于容器元素访问的耗时 #

不同容器的访问开销差异明显：

• std::map的operator[]/at()：都需要先做红黑树查找，开销高，复杂度O(log n)；
• std::unordered_map的operator[]：平均O(1)的查找开销，比std::map快很多；
• 数组/std::vector的下标访问：O(1)复杂度，是最快的访问方式，因为直接对应内存地址的读取。

内容的提问来源于stack exchange，提问作者tom