循环遍历以结构为键的地图。

Question

我有一个结构

struct key
{
  int x;
  int y;
  int z;
 };

假设 x、y、z 可以取 1 到 10 之间的值。

我也有地图

std::map<key,double> myMap;

我用不同的键值填充。

有没有一种方法可以遍历 z=5 的所有键值。即（以伪代码的形式）

 loop over myMap
   double v += myMap.find({x=anything,y=anything,z=5})->second;

如果有人可以提供一些关于这是否可以实现的评论（我不想使用 boost 容器），那就太好了。

Answer 1

标准关联容器使用一维排序，即它们只知道一个键是小于、等于还是大于另一个。所以这是不可能有效的。您可以使用 std::find_if().

在线性时间内实现此类过滤

保持 O(log n) 查找时间，但是可以创建多个地图，使用不同的索引方式；例如一个以 X 为键，一个以 Y 为键，一个以 Z 为键。如果值是大对象，您可以使用指针来避免不必要地复制它们。当然，这一切都可以隐藏在封装 class 后面，它向外部提供基于轴的排序。

另一种适用于小空间（例如从 1 到 10 的 x、y、z）的方法是不使用 std::map，而是使用 3D array/matrix。这可以使用 1D std::vector 来实现，方法是将索引从 3 维映射到 1.

Answer 2

如果您首先使用 z 对 key 结构进行排序，您可以这样做：

bool operator<( const key &k1, const key &k2 )
{
    return std::make_tuple( k1.z, k1.x, k1.y ) < std::make_tuple( k2.z, k2.x, k2.y ); // z must be first
}

auto min = std::numeric_limits<int>::min();
auto end = map.lower_bound(  key{ min, min, 6 } );
for( auto it = map.lower_bound(  key{ min, min, 5 } ); it != end; ++it ) {
   ...
}

但是如果您还需要对 x 或 y 进行迭代，则必须使用指向结构的指针为每个坐标创建单独的多图或使用 boost::multiindex.

Answer 3

#define ARRAY_SIZE 2500 // 2500 is the size of the array

为什么不像

那样创建一个数组数组

double map[2][ARRAY_SIZE];
// map[0][x] - the key of Xth value in the array (example - 10th/1st/2nd ...)
// map[1][x] - the value of Xth value in the array

就是说，不复杂就好！

循环遍历以结构为键的地图。

Looping through a map with structure as a key.

c++

struct

stdmap