我正在寻找一种在我的 C++ 程序中计算和存储 2D 函数样本的有效方法。
为了具体起见，让我从一维的问题开始，这很容易，然后解释为什么我不能将它推广到二维：
一维版本如下：我们以下列方式计算函数 z = f(x) 的样本。我们从输入中读取数据，并对应于每个输入，计算 x 和 z = g(x) 的值。现在，我们有一个 (x,z = g(x)) 对的表。如果对于任何给定的 x，只有一个条目，那么我们有 f(x) = z。否则，f(x) = z1 + z2 + ...（其中 z1、z2、... 是特定 x 的对应 z 条目）。
上述过程可以简单地使用std::multimap. 即在第一阶段，我们只是将结果存储在地图中（以x作为键）。最后，我们可以遍历地图，如果两个相邻元素足够接近，我们只需通过添加它们对应的值来合并它们。假设计算 x 和 z = g(x) 的复杂度是常数，我们可以在 O(N log N) 时间复杂度内计算 N 个样本。
现在，我想将算法概括为二维。也就是说，我们首先从输入计算 (x,y,z=g(x,y)) 对，然后设置 f(x,y) = z1 + z2 + ... （其中对于任何固定的 (x,y) 对, z1, z2, ... 是以 (x,y)) 开头的表条目的对应 z 字段。
前面的解决方案无法推广，原因很简单，即无法在 2D 平面上定义排序（实际上我们可以使用std::multimap<std::pair<double,double>,double>，但没有有意义的比较来查看键是否x1,y1在前面x2,y2）。但是，请注意在 2D 平面上存在紧密度的概念：给定两个点 (x1,y1) 和 (x2,y2)，我们可以准确地判断它们是否应该合并到我们的输出中。
好吧，非常天真的解决方案是实现一个二维链表（在每个维度中分别排序），其中有更好的邻接表示法。但这至少对于插入效率非常低，并且（除了许多其他困难之外）该过程将花费 O(M^2) 时间（其中 M = N * N 是我们要计算的 2D 平面上的样本数）
我想知道是否有一种方法（更准确地说是数据结构）可以让我更有效地解决问题？
我真的很抱歉非常多余而且相当模糊。