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

Question

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

我最初的问题：我正在编写一个快速程序来计算一个序列，其中有 x(0)=0、x(1)=1、x(2k)=(3x(k)+2x(Floor(k/2)))mod2^60、x(2k+1)=(2x(k)+3x(Floor(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]，而不计算和存储其他值以进一步优化。但是在这种情况下我必须使用地图。但是，在我将 x 的声明从数组转换为映射后，我花了 90 秒和 4.5GB 内存来实现相同的列表。所以我现在想知道是否可以使用10^8以下的索引作为数组，其余部分作为映射？

Answer 1

TL;DR

为什么不创建一个自定义 class，其中 std::array 大小为 10，std::map 作为成员，并覆盖 [] 运算符以检查索引并从中选择值根据需要排列或映射。

Answer 2

只需为您的想法写一个包装器class：

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

Answer 3

理论上，您可以使用 ArrayWithHash 库来存储您的词典。它将字典存储为数组和哈希的混合体 table 类似于 lua 解释器中的 table 实现。

Awh::ArrayWithHash<uint64_t, uint64_t> x;
dict.Reserve(100000000, 0);   //preallocate array part
for (uint64_t i = 2; i <= 100000000; i++) {
    if (i % 2 == 0) {
        x.Set(i, (3 * x.Get(i/2) + 2 * x.Get(i/4)) & 1152921504606846975ULL);
    }
    ...

不幸的是，内存消耗是 ArrayWithHash 的缺点之一。它将数组填充为二次方大小，因此数组部分会占用 1 GB。至于散列 table 实现，它的内存效率更低：它占用的内存可能是存储 key/value 对所需内存的三倍。

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

How can I use a mixture of array and map in C++?

c++

arrays

optimization

dictionary