Mit lower_bound, upper_bound und binary_search zu finden, das Objekt mit einer gleich member-Bereich

Habe ich ein struct, das so aussieht,

struct Foo {
    int a;
};

Ich habe einen Vektor, der diese Strukturen, die so Aussehen,

vector<Foo> foos;

Alle Foos sortiert werden, die integer a in aufsteigender Reihenfolge mit Hilfe der STL-sort () - Funktion. Jetzt möchte ich, um die Foo Objekt, die Mitglied Bereich a weniger als oder gleich einer gegebenen Zahl ist, wie die STL-lower_bound () - Funktion. Das problem ist, dass die STL-lower_bound-Funktion-Deklaration sieht wie folgt aus:

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

Während ich also etwas tun wollen wie,

lower_bound(foos.begin(), foos.end(), 5, custom_comp);

Kann ich nicht, wegen der int, ich bin auf der Suche nach (in diesem Fall 5) ist nicht der Typ Foo. Ich habe dieses Problem mit lower_bound(), upper_bound(), und binary_search(). custom_comp definiert nur die Reihenfolge und nicht definieren, dass ein Objekt mit a = 5 tatsächlich entspricht der int-5.

Gibt es eine elegante Möglichkeit dies zu tun, mit STL?

Edit:

Mir bewusst, dass mein Beispiel nicht vollständig darstellen mein problem. Das, was ich eigentlich habe, ist, dass Foo enthält zwei ints a und b. Wenn ich Anrufe, lower_bound, ich habe keinen Zugriff auf b (weil ich don ' T care about it). Jetzt das Problem mit billz Antwort ist, dass ich definieren einen Konstruktor, nur a als parameter, das ist nicht sehr elegant aus meiner Meinung nach (denn b ist nicht definiert oder frei wählbare, und dieser Konstruktor kann verwendet werden überall im code). Aber wenn dies die einzige Möglichkeit ist, werde ich es nehmen.

Es ist eine bessere Lösung in [stackoverflow.com/questions/5072257/..., und diese Frage ist eine mögliche doppelte dieser Frage. Zusammenfassung: In die lower_bound-Vorlage, Klasse T, die nicht den Datentyp der container-Inhalte reichten von den beiden iterator [first, last). Das heißt, T kann nur eine Ganzzahl verglichen werden. Sie können schreiben Sie einfach den Komparator zu bool Compare(Foo & f, int value) { return f.a < value; }. Und es funktioniert seit C++03.

InformationsquelleAutor gsingh2011 | 2012-11-13

c++search stl

3

Können Sie eine Konstruktor Ihre struct Foo
```
struct Foo {
  Foo(int x):a(x){
  }
    int a;
};
```
können Sie jetzt rufen:
```
std::lower_bound(foos.begin(), foos.end(), 5, custom_comp);
```
oder
```
std::lower_bound(foos.begin(), foos.end(), Foo(5), custom_comp);
```
oder
```
Foo f(5);
std::lower_bound(foos.begin(), foos.end(), f, custom_comp);
```
Den vorgeschlagenen Weg ist:
```
struct Foo {
  explicit Foo(int x):a(x){
  }
    int a;
};

std::lower_bound(foos.begin(), foos.end(), Foo(5), custom_comp);
```
- Würde ich dann definieren Sie einen operator== für Foo?
- Nein, ein operator<, aber nur, wenn Sie nicht verwenden custom_comp die nicht die gleiche Sache.
- Was ist der Punkt dass der Konstruktor explicit?
- manchmal implizite Konvertierung ist schmerzhaft
- Problem 1: Foo mit nur einem int Staat kann nicht eine gültige Foo. Problem 2: Foo könnte teuer zu machen. Problem 3: Sie sind Hacker die Daten-Struktur, so dass Sie kann einige Algorithmus auf der Datenstruktur nicht erforderlich ist, alle hacken auf die Datenstruktur.
InformationsquelleAutor billz

In C++11, können Sie die folgenden verwenden:

std::lower_bound(foos.begin(), foos.end(), Foo{5},
    [](const Foo& f1, const Foo& f2) { return f1.a < f2.a; });

Oder in C++03:

Foo f = {5};
std::lower_bound(foos.begin(), foos.end(), f, custom_comp);

InformationsquelleAutor Jesse Good

0

Haben Ihre custom_comp akzeptieren sowohl foo und int als Argumente. Das bedeutet, dass es entweder braucht, um sein Funktor, oder es könnte foo_sort_helper Argumente (auf die aufgebaut werden kann, von einem int oder eine foo) und bestellen diese.

Oder, expliziter:
```
struct FooSortHelper
{
  int ordering;
  FooSortHelper( Foo const& foo ):ordering(foo.value) {}
  FooSortHelper( int i ): ordering(i) {}
  FooSortHelper( FooSortHelper const& other):ordering(other.ordering) {}
  bool operator<( FooSortHelper const& other ) { return ordering < other.ordering }
};

auto lower = std::lower_bound( vec.begin(), vec.end(), 5,
  []( FooSortHelper left, FooSortHelper right ) {
    return left < right;
  }
);
```
Du sehen, wie ich die Kapseln wie Foo sortiert in den FooSortHelper? Und dadurch, dass es gebaut werden können, von einem int-Datentyp, Erlaube ich Foo verglichen werden int nahtlos.

Die alternative, die ich erwähnt ist das erstellen einer Klasse mit dem operator() überladen auf jedes paar von Foo und int (alle 4). Ich finde das obige einfacher.

Wenn der Typ(s), die Sie Sortieren, ist teuer zu kopieren (wie std::string) die FooSortHelper können, speichern Sie einen Verweis auf die besagten Felder.
- Aber lower_bound würde versuchen, vorbei Foo custom_comp... Es würde nicht wissen, übergeben Sie die int-innen Foo.
- Genau. So custom_comp nimmt beide Foos und ints. Dies erfordert entweder einen Funktor struct custom_comp { bool operator()(int, Foo const&) const; bool operator()(Foo const&, int) const; bool operator()(int, int) const; bool operator()(Foo const&, Foo const&) const; };, das finde ich anstrengend, oder die oben genannten Helfer-trick. Die Helfer können so konstruiert werden, indem entweder eine Foo oder eine int und speichert nur die Teile der Foo, die erforderlich sind für die Sortierung. Ich habe es mit einen lambda-Ausdruck, aber man könnte ein custom_comp Funktion oder Funktor, wenn Sie bevorzugen.
InformationsquelleAutor Yakk - Adam Nevraumont

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.