Access flattened2d without iterating

Question

I have a

flattened2d<VecType> bids;

that I would just like to access using the [] operator without using an iterator. I don't want to copy the vector. Is there an efficient way to get an index (e.g., 0) of a flattened2d?

Answer 1

There are no random access methods for flattened2d. You can build your own similar data structure with a random-access operator[]. For n sub-containers, construct two vectors.

• A[k] should point to the kth sub-container.
• B[k] should contain the sum of A[j]->size() for 0<=j

Given those vectors, operator[] can be computed as

// Find j such that A[j] is the subcontainer containing element [i]
size_t j = lower_bound(B.begin(),B.end(),i)-B.begin();
// Index the subcontainer. 
return A[j][i-B[j]]

Note that the access time will be O(P), where P is the number of subcontainers. If there are many accesses, you're better off copying the the subcontainers into a single contiguous container anyway.