地图数据结构优化图

Question

我想为每个 x、y 坐标存储一个 2D 点向量，以用作查找 table 光线跟踪器某个方面的预先计算值。

为此，我创建了以下类型的数据结构：

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

为了了解数据结构的复杂性，映射和向量各包含 32 个条目。

我可以通过以下方式找到 x、y 坐标的下限值：

// 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};

这一切都按预期工作，但出奇地慢。我只需要在每条光线中调用这两个值一次，这意味着对于下一条光线，它将破坏并再次创建这一切。

关于如何加快这个过程的任何建议？我想为初学者使用无序映射，但我需要找到非精确键，我想我只能使用 lower/upper 边界吗？如果有更快的方法，我也不会依附于这个特定的数据结构。

Answer 1

这一行：

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

它制作了内部地图的完整副本。要么更改该行以使 internal_map 成为对 it->second 的引用，要么完全删除该行并更改以下行以直接使用 it->second。

地图数据结构优化图

Optimising map of map data structure

c++

optimization

stdmap