C++ Lambda-Ausdrücke für std::sort und std::lower_bound/equal_range auf ein struct-element in einen sortierten Vektor von structs

Es ist ein wenig umständlich, aber wenn man sich mal die Definitionen von lower_bound und upper_bound von der Norm ab, werden Sie sehen, dass die definition von lower_bound stellt der dereferenziert den iterator als ersten parameter der Vergleich (und der zweite Wert), in der Erwägung, dass upper_bound setzt den iterator dereferenziert zweiten (und der Wert zuerst).

So, ich noch nicht getestet, aber ich denke, Sie würde wollen:

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

und

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

Diese ist ziemlich böse, und ohne den Blick ein paar Dinge, die ich bin mir nicht sicher, du bist tatsächlich berechtigt, anzunehmen, dass die Implementierung verwendet der Komparator nur in der Art, wie es im text beschrieben - das ist eine definition das Ergebnis, nicht das Mittel, um dorthin zu gelangen. Es hilft auch nicht mit binary_search oder equal_range.

Es ist nicht ausdrücklich in 25.3.3.1, dass der iterator den Wert geben müssen, sein Cabrio zu T, aber es ist eine Art STILLSCHWEIGENDE durch die Tatsache, dass die Voraussetzung für den Algorithmus ist, dass T (in diesem Fall double) muss LessThanComparable, nicht, dass T müssen vergleichbar sein, um den Wert Art von iterator in einer bestimmten Reihenfolge.

Also ich denke, dass es besser ist, sich einfach immer mit einem lambda (oder Funktor) vergleicht zwei MS-Strukturen, und statt der übergabe eines Doppel-als Wert übergeben Sie eine dummy-MS mit dem richtigen Feld auf den Wert, den du suchst:

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

Wenn Sie nicht möchten, dass MS einen Konstruktor (weil Sie es sein wollen-POD), dann schreiben Sie eine Funktion zum erstellen von MS-Objekt:

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

Wirklich, jetzt, es sind Lambda-Ausdrücke, die für diese Aufgabe wollen wir eine version der binären Suche, dauert ein unärer "Komparator":

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

C++0x nicht bieten, obwohl.

Nicht direkt relevant, was du sagst über lambdas, aber das könnte eine Idee für die Nutzung des binary-search-Funktionen:

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

Grundsätzlich durch die Verwendung von Find als der Wert, haben wir nicht zu liefern, einen Komparator, weil Find im Vergleich zu MS mit dem Feld, die wir angeben. Dies ist die gleiche Art der Sache, wie die Antwort, Sie sahen mehr hier: wie zu Sortieren STL-Vektor, sondern mit dem Wert, anstatt den Komparator wie in diesem Fall. Nicht sicher, ob es wäre so toll zu bedienen, aber es könnte sein, denn es gibt den Wert zu suchen und die Suchbegriffe in das Feld in einem einzigen kurzen Ausdruck.

In der definition von lower_bound und andere STL-Algorithmen, die die Compare-Funktion ist derart, dass der erste Typ muss übereinstimmen, dass der Forward-Iterator und der zweite Typ müssen übereinstimmen, die von T (D. H., der Wert).

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

So dass man tatsächlich vergleichen können, die Dinge aus verschiedenen Objekten (tun, was die anderen Antwort genannt einen Einfachen Komparator). In 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; 
                           });

Und dies kann verwendet werden, mit anderen STL-Algorithmus Funktionen.