CODEWITHSUNDEEP
c++optimizationstdmap
zeno
zeno

Reputation: 81

Optimising map of map data structure

I want to store a vector of 2D points for every x, y coordinate, to be used as a lookup table with pre-calculated values for a certain aspect of a raytracer.

For this, I created a datastructure of the following type:

std::map<float, std::map<float, std::vector<vec2>>> apertureMap;

To give an idea of the complexity of the datastructure, the maps and vector will each hold 32 entries.

I can find lower bound values for x, y coordinates by:

// find lowest bound x value
std::map<float, std::map<float, std::vector<vec2>>>::iterator it;
it = apertureMap.lower_bound(someInputValueX);
float value1 = it->first;

// find lowest bound y value
std::map<float, std::vector<vec2>>::iterator it2;
std::map<float, std::vector<vec2>> internal_map = it->second;
it2 = internal_map.lower_bound(someInputValueY);
float value2 = it2->first;

vec2 vertex = {it2->second[randomNumber].x, it2->second[randomNumber].y};

This all works as expected, but is surprisingly slow. I need to call these two values only once per ray, which means for the next ray it will destroy and create this all again.

Any recommendations on how to speed up this process? I would like to use an unordered map for starters, but I need to find non-exact keys, which I think I can only do using lower/upper bounds? I also am not attached to this particular data structure if there would be a faster way.

Upvotes: 1

Views: 69

Answers (1)

IanM_Matrix1
IanM_Matrix1

Reputation: 1594

This line:

std::map<float, std::vector<vec2>> internal_map = it->second;

it makes a full copy of the inner map. Either change that line to make internal_map a reference to it->second , or remove that line entirely and change the following line to use it->second directly.

Upvotes: 3

Related Questions