结构体排序向量中结构体元素上 std::sort 和 std::lower_bound/equal_range 的 C++ lambda [英] C++ lambdas for std::sort and std::lower_bound/equal_range on a struct element in a sorted vector of structs

问题描述

我有一个 std::vector 这个结构体:

I have a std::vector of this struct:

struct MS
{        
  double aT;
  double bT;
  double cT;
};

我想使用 std::sort 以及 std::lower_bound/equal_range 等...

which I want to use std::sort on aswell as std::lower_bound/equal_range etc...

我需要能够对它进行排序并在结构的前两个元素中的任何一个上查找它.所以目前我有这个:

I need to be able to sort it and look it up on either of the first two elements of the struct. So at the moment I have this:

class MSaTLess 
{
public:
  bool operator() (const MS &lhs, const MS &rhs) const
  {
    return TLess(lhs.aT, rhs.aT);
  }
  bool operator() (const MS &lhs, const double d) const
  {
    return TLess(lhs.aT, d);
  }
  bool operator() (const double d, const MS &rhs) const
  {
    return TLess(d, rhs.aT);
  }
private:
  bool TLess(const double& d1, const double& d2) const
  {
    return d1 < d2;
  }
};


class MSbTLess 
{
public:
  bool operator() (const MS &lhs, const MS &rhs) const
  {
    return TLess(lhs.bT, rhs.bT);
  }
  bool operator() (const MS &lhs, const double d) const
  {
    return TLess(lhs.bT, d);
  }
  bool operator() (const double d, const MS &rhs) const
  {
    return TLess(d, rhs.bT);
  }
private:
  bool TLess(const double& d1, const double& d2) const
  {
    return d1 < d2;
  }
};

这允许我使用 MSaTLess() 调用 std::sort 和 std::lower_bound 以基于 aT 元素进行排序/查找，并使用 MSbTLess() 基于 bT 元素进行排序/查找.

This allows me to call both std::sort and std::lower_bound with MSaTLess() to sort/lookup based on the aT element and with MSbTLess() to sort/lookup based on the bT element.

我想摆脱函子并使用 C++0x lambdas 代替.对于相对简单的排序，因为 lambda 将采用两个 MS 类型的对象作为参数.

I'd like to get away from the functors and use C++0x lambdas instead. For sort that is relatively straightforward as the lambda will take two objects of type MS as arguments.

但是，lower_bound 和其他二分查找算法呢?他们需要能够使用 (MS, double) 参数调用比较器，也可以使用相反的 (double, MS) 参数，对吗?我怎样才能在调用lower_bound时最好地提供这些与lambda?我知道我可以创建一个 MS 虚拟对象，并搜索所需的键值，然后使用与 std::sort 相同的 lambda，但有没有办法在不使用虚拟对象的情况下做到这一点?

What about for the lower_bound and other binary search lookup algorithms though? They need to be able to call a comparator with (MS, double) arguments and also the reverse, (double, MS), right? How can I best provide these with a lambda in a call to lower_bound? I know I could create an MS dummy object with the required key value being searched for and then use the same lambda as with std::sort but is there a way to do it without using dummy objects?

推荐答案

有点别扭，但是如果你查看标准中lower_bound和upper_bound的定义，您会看到 lower_bound 的定义将取消引用的迭代器作为比较的 first 参数(以及第二个值)，而 upper_bound将解除引用的迭代器 second(和值放在首位).

It's a little awkward, but if you check the definitions of lower_bound and upper_bound from the standard, you'll see that the definition of lower_bound puts the dereferenced iterator as the first parameter of the comparison (and the value second), whereas upper_bound puts the dereferenced iterator second (and the value first).

所以，我还没有测试过这个，但我想你会想要:

So, I haven't tested this but I think you'd want:

std::lower_bound(vec.begin(), vec.end(), 3.142, [](const MS &lhs, double rhs) {
    return lhs.aT < rhs;
});

和

std::upper_bound(vec.begin(), vec.end(), 3.142, [](double lhs, const MS &rhs) {
    return lhs < rhs.aT;
});

这太糟糕了，如果不查看更多内容，我不确定您是否真的有权假设该实现仅以文本中描述的方式使用比较器 - 这是结果的定义，不是到达那里的手段.它对 binary_search 或 equal_range 也没有帮助.

This is pretty nasty, and without looking up a few more things I'm not sure you're actually entitled to assume that the implementation uses the comparator only in the way it's described in the text - that's a definition of the result, not the means to get there. It also doesn't help with binary_search or equal_range.

在 25.3.3.1 中没有明确说明迭代器的值类型必须可以转换为 T，但是算法的要求是 T(在这种情况下)这一事实暗示了这一点, double) 必须是 LessThanComparable，而不是 T 必须以任何特定顺序与迭代器的值类型进行比较.

It's not explicitly stated in 25.3.3.1 that the iterator's value type must be convertible to T, but it's sort of implied by the fact that the requirement for the algorithm is that T (in this case, double) must be LessThanComparable, not that T must be comparable to the value type of the iterator in any particular order.

所以我认为最好总是使用比较两个 MS 结构的 lambda(或函子)，而不是将双精度值作为值传递，而是传递一个将正确字段设置为您正在查找的值的虚拟 MS对于:

So I think it's better just to always use a lambda (or functor) that compares two MS structs, and instead of passing a double as a value, pass a dummy MS with the correct field set to the value you're looking for:

std::upper_bound(vec.begin(), vec.end(), MS(3.142,0,0), [](const MS &lhs, const MS &rhs) {
    return lhs.aT < rhs.aT;
});

如果你不想给 MS 一个构造函数(因为你希望它是 POD)，那么你可以写一个函数来创建你的 MS 对象:

If you don't want to give MS a constructor (because you want it to be POD), then you can write a function to create your MS object:

MS findA(double d) {
    MS result = {d, 0, 0};
    return result;
}
MS findB(double d) {
    MS result = {0, d, 0};
    return result;
}

真的，现在有了 lambda，对于这项工作，我们想要一个使用一元比较器"的二分搜索版本:

Really, now that there are lambdas, for this job we want a version of binary search that takes a unary "comparator":

double d = something();
unary_upper_bound(vec.begin(), vec.end(), [d](const MS &rhs) {
    return d < rhs.aT;
});

C++0x 不提供它，但是.

C++0x doesn't provide it, though.

这篇关于结构体排序向量中结构体元素上 std::sort 和 std::lower_bound/equal_range 的 C++ lambda的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！