根据每个元素上计算的值对向量进行排序,而不对每个元素执行多次计算

std::transform 使用合适的谓词。

• std::vector<Thing> 到 std::vector< std::pair<Result,Thing> >
• 逆变换

编辑 :最小化副本数量

• 标准::向量<事物> 到 std::vector< std::pair<Result,Thing*> >
• 变换回次向量(局部)
• 交换原始向量和局部向量

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

你可以打电话给 CalculateGoodness 在排序之前调用每个元素,然后 只需更新内部成员变量。然后可以根据该成员变量进行排序。

如果不能修改类型,另一种可能是存储某种类型的 std::map

我投了赞成票 Brian's answer 因为它显然是你想要的最好答案。但你应该考虑的另一个解决办法是 用简单的方法写就行了 CalculateGoodness 真的是瓶颈。

我会创建一对评分和一些东西,每件事调用CalculateGoodness一次,然后根据评分进行排序。如果适用的话,你也可以把它从一个等级转移到另一个等级

另一种选择是将CalculateGoodness缓存在事物本身中,要么作为一个简单的字段,要么将CalculateGoodness作为事物的一种方法(确保缓存是可变的,这样const Things仍然可以工作)

也许这是一个整洁的方法 vector vector< pair<float, Thing*> > ,其中第二个元素指向 Thing 对象与相应的 float 价值观。如果你把它分类 矢量 由 浮动 值,可以对其进行迭代并读取 对象的正确顺序,可能将它们播放到另一个 或 list