c++ - 如何在 C++ 中混合使用数组和映射？

Question

我的问题的一个简短版本:是否可以使用数组数据结构，例如，将 x[0] 到 x[10] 视为正常数组，和一些其他点值，x[15]，x[20] 作为 map ？原因:我不计算或存储任何其他大于索引 11 的值，并使整个事物成为 map 会显着减慢计算速度。

我最初的问题:我正在编写一个快速程序来计算一个序列，其中有 x(0)=0、x(1)=1、x(2k)=(3x(k)+2x(楼层(k/2)))mod2^60, x(2k+1)=(2x(k)+3x(楼层( k/2)))mod2^60，我的目标是列出从 x(10^12) 到 x(2*10^12) 的数字>

我用普通数组列出并存储第一个 10^8 值，

for (unsigned long long int i = 2; i<=100000000;i++){
    if (i%2==0) {
        x[i] =(3*x[i/2] + 2*x[(unsigned long long int)(i/4)])&1152921504606846975;
    }
    else{
        x[i] =(2*x[(i-1)/2] + 3*x[(unsigned long long int)((i-1)/4)])&1152921504606846975;
    }

 }//these code for listing
unsigned long long int xtrans(unsigned long long int k){
    if (k<=100000000)return x[k];
    unsigned long long int result;
    if (k%2==0) {
        result =(3*xtrans(k/2) + 2*xtrans((unsigned long long int)(k/4)))&1152921504606846975;
    }
    else{
        result =(2*xtrans((k-1)/2) + 3*xtrans((unsigned long long int)((k-1)/4)))&1152921504606846975;
    }
    return result;
}//These code for calculating x

列出这些数字需要大约 2 秒和 750MB 的内存。

我打算存储特定值，例如 x[2*10^8]、x[4*10^8]，而不计算和存储其他值进一步优化。但是在这种情况下我必须使用 map 。但是，在我将 x 的声明从数组转换为映射后，我花了 90 秒和 4.5GB 内存来实现相同的列表。所以我现在想知道是否可以使用10^8以下的索引作为数组，其余部分作为映射？

Answer 1

简单地为您的想法编写一个包装器类:

class MyMap {
    ...
    operator[](size_t i) {
        return ( i <= barrier_ ) ? array_[i] : map_[i];
    }
}