C ++ лямбда-выражения для std :: sort и std :: lower_bound / equal_range для элемента структуры в отсортированном векторе структур

Question

У меня есть std :: vector этой структуры:

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

который я хочу использовать как std :: sort, так и std :: lower_bound / equal_range и т. Д. *

Мне нужно уметь сортировать и искать по любому из первых двух элементов структуры. Итак, на данный момент у меня есть это:

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. Для сортировки это относительно просто, так как лямбда примет два объекта типа MS в качестве аргументов.

А как насчет нижнего_блика и других алгоритмов бинарного поиска? Они должны иметь возможность вызывать компаратор с (MS, двойной) аргументами, а также наоборот, (двойной, MS), верно? Как я могу наилучшим образом обеспечить их лямбда при вызове lower_bound? Я знаю, что мог бы создать фиктивный объект MS с искомым требуемым значением ключа, а затем использовать ту же лямбду, что и в std :: sort, но есть ли способ сделать это без использования фиктивных объектов?

Answer 1

Это немного неловко, но если вы проверите определения lower_bound и upper_bound из стандарта, вы увидите, что определение lower_bound ставит разыменованный итератор как first параметр сравнения (и значение second), тогда как upper_bound помещает разыменованный итератор second (и значение first).

Итак, я не проверял это, но думаю, вы захотите:

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) должно быть LessThanComparable, за исключением того, что T должен быть сопоставим с типом значения итератора в любом конкретном порядке.

Так что я думаю, что лучше просто использовать лямбду (или функтор), которая сравнивает две структуры MS, и вместо того, чтобы передавать значение типа double в качестве значения, передайте фиктивную 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;
}

Действительно, теперь, когда есть лямбды, для этой работы нам нужна версия бинарного поиска, которая использует унарный «компаратор»:

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

C ++ 0x этого не обеспечивает.

Answer 2

Алгоритмы std :: sort, std :: lower_bound и std :: binary_search принимают предикат, который сравнивает два элемента контейнера. Любая лямбда, которая сравнивает два объекта MS и возвращает true, когда они в порядке, должна работать для всех трех алгоритмов.

Answer 3

В определении для lower_bound и других алгоритмов STL функция сравнения такова, что первый тип должен соответствовать типу прямого итератора, а второй тип должен соответствовать типу T (т. Е. Значения) .

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

Так что действительно можно сравнивать вещи из разных объектов (делая то, что в другом ответе называется Унарный компаратор). В C ++ 11:

vector<MS> v = SomeSortedVectorofMSByFieldaT();
double a_key;
auto it = std::lower_bound(v.begin(), 
                           v.end(), 
                           a_key, 
                           []{const MS& m, const double& a) {
                             m.aT < a; 
                           });

И это также может быть использовано с другими функциями алгоритма STL.

Answer 4

У меня была такая же проблема для std::equal_range, и я нашел альтернативное решение.

У меня есть коллекция указателей на объекты, отсортированные по полю типа.Мне нужно найти диапазон поиска объектов для данного типа.

const auto range = std::equal_range (next, blocks.end(), nullptr,
    [type] (Object* o1, Object* o2)
{
    return (o1 ? o1->Type() : type) < (o2 ? o2->Type() : type);
});

Хотя это менее эффективно, чем выделенный предикат, поскольку он вводит ненужный тест nullptr для каждого объекта в моей коллекции, он обеспечиваетинтересная альтернатива.

Кроме того, когда я использую класс, как в вашем примере, я склонен делать следующее.Кроме того, это позволяет мне добавлять дополнительные типы только с 1 функцией на тип, а не с 4 операторами на тип.

class MSbTLess 
{
private:
    static inline const double& value (const MS& val)
    {
        return val.bT;
    }

    static inline const double& value (const double& val)
    {
        return val;
    }

public:
    template <typename T1, typename T2>
    bool operator() (const T1& lhs, const T2& rhs) const
    {
        return value (t1) < value (t2);
    }
};

Answer 5

Не имеет прямого отношения к тому, что вы говорите о лямбдах, но это может быть идеей для использования функций двоичного поиска:

#include <iostream>
#include <algorithm>
#include <vector>

struct MS
{
    double aT;
    double bT;
    double cT;
    MS(double a, double b, double c) : aT(a), bT(b), cT(c) {}
};

// template parameter is a data member of MS, of type double
template <double MS::*F>
struct Find {
    double d;
    Find(double d) : d(d) {}
};

template <double MS::*F>
bool operator<(const Find<F> &lhs, const Find<F> &rhs) {
    return lhs.d < rhs.d;
}
template <double MS::*F>
bool operator<(const Find<F> &lhs, const MS &rhs) {
    return lhs.d < rhs.*F;
}
template <double MS::*F>
bool operator<(const MS &lhs, const Find<F> &rhs) {
    return lhs.*F < rhs.d;
}

int main() {
    std::cout << (Find<&MS::bT>(1) < Find<&MS::bT>(2)) << "\n";
    std::cout << (Find<&MS::bT>(1) < MS(1,0,0)) << "\n";
    std::cout << (MS(1,0,0) < Find<&MS::bT>(1)) << "\n";

    std::vector<MS> vec;
    vec.push_back(MS(1,0,0));
    vec.push_back(MS(0,1,0));
    std::lower_bound(vec.begin(), vec.end(), Find<&MS::bT>(0.5));
    std::upper_bound(vec.begin(), vec.end(), Find<&MS::bT>(0.5));
}

По сути, используя Find в качестве значения, нам не нужно предоставлять компаратор, потому что Find сравнивается с MS, используя указанное нами поле. Это то же самое, что и ответ, который вы видели здесь: как отсортировать вектор STL , но с использованием значения, а не компаратора, как в этом случае. Не уверен, что все это было бы здорово, но это возможно, поскольку он указывает значение для поиска и поле для поиска в одном коротком выражении.