c++: Random access to Dynamic Array

Question

Following is my scenario:

I am making use of a large 2D dynamic array to store elements with following attributes:

int
vector

Now, the array elements are accessed randomly. As a result, time access to elements greatly varies.

I want time access to elements to be small as well as constant for all the accessions.

Is dynamic array best suitable for my scenario?

I tries using unordered_map of boost but it seems that unordered map takes more time to access elements as compared to dynamic array.

Please give suggestions:

Code:

Code:

for( counter1=0; counter1< sizeof(chunk1); ++counter1)
{
   //code lines skipped
    IndexEntries &data=IndexTable[chunk1[counter1]][chunk1[counter1+1]];
    DoubleTableEntries &GetValue=NewDoubleTable[NextState_chunk1][data.index]; 
    NextState_chunk1= GetValue.Next_State;
    ++Bcount;
    buffer[ Bcount]=NextState_chunk1;
    ++counter1;

    //  Code lines skipped
}  

Here NewDoubleTable is the 2d Array from which I am accessing randomly elements.

Answer 1

There is nothing that can beat an array access in terms of speed, all the higher level containers like unordered_map<> add additional work. When you can use a plain array or vector<>, that is always the fastest you can get.

You need unordered_map<> only if you have a sparsely populated keyspace which prohibits use of a plain array/vector due to space considerations. In that case, the unordered_map<> can translate the keys in the sparse keyspace to a hash index into the tightly populated hash table, which in turn is nothing more or less than an array.

Answer 2

For random access, nothing can beat array (dynamic or not). Only this data structure provides O(1) access time on an average because the it uses consecutive memory.