c++ - 在 C++ vector 中平均重复属性的最佳方法

Question

我有一个 std::vector<PLY>拥有许多结构:

struct PLY {
    int x;
    int y;
    int greyscale;
}

一些 PLY 的位置可能是重复的 x和 y但不一定就他们而言 greyscale值(value)。找到那些(位置)重复项并将它们替换为单个 PLY 的最佳方法是什么？具有代表所有拷贝的平均灰度的灰度值的实例？

例如:PLY a{1,1,188}是 PLY b{1,1,255} 的拷贝.相同的 (x,y) 位置可能不同的灰度。

Answer 1

根据您对 Ply 的描述，您需要这些运算符:

auto operator==(const Ply& a, const Ply& b)
{
  return a.x == b.x && a.y == b.y;
}
auto operator<(const Ply& a, const Ply& b)
{
  // whenever you can be lazy!
  return std::make_pair(a.x, a.y) < std::make_pair(b.x, b.y);
}

非常重要:如果定义“如果它们的 x 和 y 相同，则两个 Ply 相同”不是普遍有效的，那么定义忽略 greyscale 的比较运算符是一个坏主意。在这种情况下，您应该定义单独的函数对象或非运算符函数并将它们传递给函数。

有一个很好的经验法则，一个函数不应超过一个循环。因此，我们定义了这个辅助函数，而不是嵌套的 2 个 for 循环，它计算连续重复的平均值并返回连续重复范围的末尾:

// prereq: [begin, end) has at least one element
//         i.e. begin != end
template <class It>
auto compute_average_duplicates(It begin, It end) -> std::pair<int, It>
   // (sadly not C++17) concepts:
   //requires requires(It i) { {*i} -> Ply; }
{
  auto it = begin + 1;
  int sum = begin->greyscale;
  for (; it != end && *begin == *it; ++it) {
    sum += it->greyscale;
  }
  // you might need rounding instead of truncation:
  return std::make_pair(sum / std::distance(begin, it), it);
}

有了这个我们就可以得到我们的算法:

auto foo()
{
  std::vector<Ply> v = {{1, 5, 10}, {2, 4, 6}, {1, 5, 2}};

  std::sort(std::begin(v), std::end(v));

  for (auto i = std::begin(v); i != std::end(v); ++i) { 
    decltype(i) j;
    int average;

    std::tie(average, j) = compute_average_duplicates(i, std::end(v));

    // C++17 (coming soon in a compiler near you):
    // auto [average, j] = compute_average_duplicates(i, std::end(v));

    if (i + 1 == j)
      continue;

    i->greyscale = average;
    v.erase(i + 1, j);
    // std::vector::erase Invalidates iterators and references
    // at or after the point of the erase
    // which means i remains valid, and `++i` (from the for) is correct
  }
}