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

Question

A short version of my problem: Is it possible to use an array data structure, for example, treats x[0] to x[10] as a normal array, and some other point value, x[15], x[20] as a map? Reasons: I do not calculate or store any other value bigger than index 11, and making the whole thing a map slows down the calculation significantly.

My initial problem: I am writing a fast program to calculate a series, which has 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, and my target is to list numbers from x(10^12) to x(2*10^12)

I am listing and storing the first 10^8 value with normal array,

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

listing those numbers takes me around 2s and 750MB of memory.

And I am planning to store specific values for example x[2*10^8], x[4*10^8] without calculating and storing other values for further optimization. But I have to use map in this situation. However, after I convert the declaration of x from array to map, it took me 90s and 4.5GB memory to achieve the same listing. So I am now wondering if it is possible to use index under 10^8 as an array, and the remaining part as map?

Answer 1

Simply write a wrapper class for your idea:

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

Answer 2

TL;DR

Why not create a custom class with an std::array of size 10 and an std::map as members and override [] operator to check index and pick value from either array or map as per the need.