代码之家 › 专栏 › 技术社区 › Ben Hymers

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

sorting c++

Ben Hymers · 技术社区 · 16 年前

有谁能推荐一个漂亮整洁的方法来实现这一点:

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 与其他元素相比,如果价格昂贵。我可以再创造一个 std::vector 只是为了存储收视率和然后重新安排 things

编辑:抱歉,我应该说没有修改 ,否则这是一个相当容易解决的问题:)

5 回复 | 直到 16 年前

Matthieu M. 16 年前

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

Brian R. Bondy 16 年前

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

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

Community Mohan Dere 9 年前

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

jk. 16 年前

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

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

suszterpatt 16 年前

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