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

问题描述

我有一个此结构的std :: vector:

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

我想在std :: lower_bound/equal_range等上同时使用std :: sort ...

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

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

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

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

那么lower_bound和其他二进制搜索查找算法又如何呢?他们需要能够使用(MS，double)参数以及反向(double，MS)来调用比较器，对吗?如何在调用lower_bound时为它们最好提供一个lambda?我知道我可以创建一个MS虚拟对象，并搜索所需的键值，然后使用与std :: sort相同的lambda，但是有没有一种方法可以不使用虚拟对象呢?

解决方案

有点尴尬，但是如果您从标准中检查lower_bound和upper_bound的定义，您会发现将取消引用的迭代器作为比较的 first 参数(第二个值)，而upper_bound将取消引用的迭代器作为比较的 second (值第一)./p>

因此，我尚未对此进行测试，但我认为您想要这样做:

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，它也无济于事.

在25.3.3.1中没有明确声明迭代器的值类型必须可转换为T，但是这种隐含的事实是算法的要求是 T (在这种情况下， ，double)必须小于可比较，而不是T必须以任何特定顺序与迭代器的值类型可比.

因此，我认为最好始终使用比较两个MS结构的lambda(或函子)，而不要传递双精度值作为值，而应将具有正确字段设置为您要查找的值的虚拟MS传递给用于:

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对象:

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

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

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

但是，

C ++ 0x没有提供它.

I have a std::vector of this struct:

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

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

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.

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.

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?

解决方案

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

and

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

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.

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.

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

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

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 doesn't provide it, though.

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