C++ лямбда-выражения для std::sort и std::lower_bound/equal_range для элемента структуры в отсортированном векторе структур
У меня есть 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, но есть ли способ сделать это без использования фиктивных объектов?
5 ответов
Это немного неловко, но если вы проверите определения lower_bound а также upper_bound из стандарта, вы увидите, что определение lower_bound помещает разыменованный итератор в качестве первого параметра сравнения (а в качестве значения второго), тогда как upper_bound ставит разыменованный итератор вторым (и значение первым).
Итак, я не проверял это, но я думаю, что вы хотите:
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 этого не обеспечивает.
Алгоритмы std::sort, std::lower_bound и std::binary_search принимают предикат, который сравнивает два элемента контейнера. Любая лямбда, которая сравнивает два объекта MS и возвращает true когда они в порядке, должны работать для всех трех алгоритмов.
Не имеет прямого отношения к тому, что вы говорите о лямбдах, но это может быть идеей для использования функций бинарного поиска:
#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, но с использованием значения, а не компаратора, как в этом случае. Не уверен, будет ли это все так здорово использовать, но это может быть так, поскольку он указывает значение для поиска и поле для поиска в одном коротком выражении.
В определении lower_bound и других алгоритмов STL функция Compare такова, что первый тип должен соответствовать типу прямого итератора, а второй тип должен соответствовать типу 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.
У меня была такая же проблема для 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);
}
};