c++ - 根据在每个元素上计算的值对 vector 进行排序，而无需对每个元素执行多次计算

Question

谁能推荐一个漂亮而整洁的方法来实现这一目标:

float CalculateGoodness(const Thing& thing);

void SortThings(std::vector<Thing>& things)
{
    // sort 'things' on value returned from CalculateGoodness, without calling CalculateGoodness more than 'things.size()' times
}

很明显，我可以将 std::sort 与调用 CalculateGoodness 的比较函数一起使用，但随后每个 Thing 都会调用多次因为它与其他元素相比，如果 CalculateGoodness 很昂贵，这就不好了。我可以创建另一个 std::vector 来存储评级和 std::sort，并以相同的方式重新排列 things，但是我看不到这样做的整洁方法。有什么想法吗？

编辑:抱歉，我应该在不修改 Thing 的情况下说，否则这是一个相当容易解决的问题:)

Answer 1

我可以想到一个简单的转换(好两个)来得到你想要的。你可以使用 std::transform带有合适的谓词。

• std::vector<Thing>至 std::vector< std::pair<Result,Thing> >
• 对第二个 vector 进行排序(之所以有效，是因为一对是按第一个成员排序的)
• 反向转换

他达姆:)

编辑:最小化拷贝数

• std::vector<Thing>至 std::vector< std::pair<Result,Thing*> >
• 对第二个 vector 进行排序
• 转换回二级 vector (本地)
• 交换原始 vector 和局部 vector

这样你只会复制每个 Thing一次。特别要记住 sort进行复制，因此值得使用。

因为我感到很欣慰:

typedef std::pair<float, Thing*> cached_type;
typedef std::vector<cached_type> cached_vector;

struct Compute: std::unary_function< Thing, cached_type >
{
  cached_type operator()(Thing& t) const
  {
    return cached_type(CalculateGoodness(t), &t);
  }
};

struct Back: std::unary_function< cached_type, Thing >
{
  Thing operator()(cached_type t) const { return *t.second; }
};


void SortThings(std::vector<Thing>& things)
{
  // Reserve to only allocate once
  cached_vector cache; cache.reserve(things.size());

  // Compute Goodness once and for all
  std::transform(things.begin(), things.end(),
                 std::back_inserter(cache), Compute());

  // Sort
  std::sort(cache.begin(), cache.end());

  // We have references inside `things` so we can't modify it
  // while dereferencing...
  std::vector<Thing> local; local.reserve(things.size());

  // Back transformation
  std::transform(cache.begin(), cache.end(),
                 std::back_inserter(local), Back());

  // Put result in `things`
  swap(things, local);
}

提供了通常的买者自负:在我的头顶上，可能会杀死小猫......