std::lower_bound
-
Hi,
wie funktioniert lower_bound? ich moechte den nach naechst kleineren oder gleichen key suchen...
#include <iostream> #include <vector> #include <algorithm> using namespace std; auto find_next_smaller(const vector<int> &vec, const int key) { auto it = std::lower_bound(vec.begin(), vec.end(), key); if (it != vec.begin()) { if (*it > key) { it--; } return *it; } return *it; } int main() { vector<int> a; a.push_back(1); a.push_back(5); a.push_back(6); for (int i = 0; i <= 7; i++) { cout << "i=" << i << ": " << find_next_smaller(a, i) << endl; } return 0; }
ausgabe:
i=0: 1 i=1: 1 i=2: 1 i=3: 1 i=4: 1 i=5: 5 i=6: 6 i=7: 0 <--- warum 0, sollte 6 sein...?
LG
-
http://en.cppreference.com/w/cpp/algorithm/lower_bound
Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value.
Da du kein element >=7 hast, ist die range leer und std::lower_bound gibt a.end() zurück, das heißt du greifst gerade auf ein element ausserhalb des vectors zu - und was das gibt ist undefiniertes Verhalten.
-
Die elegantere Lösung wäre wohl, von rbegin() nach rend() zu laufen und operator> als Vergleichsoperator zu wählen.
-
da meine sequenz sortiert ist koennte ich eine modifizierte binary search implementieren? gibt es schon sowas in der STL?
-
dein code ist fast richtig, du must nur den fall abfangen, dass lower_bound dir end zurückgibt.
auto find_next_smaller(const vector<int> &vec, const int key) { auto it = std::lower_bound(vec.begin(), vec.end(), key); if (it == vec.end()) return vec.back(); if (it != vec.begin() && *it > key) { it--; } return *it; }
-
@otze: danke! nimmt lower_bound eine binary search wenn der vector sortiert ist?
#include <iostream> #include <vector> #include <algorithm> using namespace std; auto find_next_smaller(const vector<int> &vec, const int key) { auto it = std::lower_bound(vec.begin(), vec.end(), key); if (it != vec.begin()) { if (*it > key) { it--; } return *it; } else if (it == vec.end()) { it = vec.rbegin().base(); } return *it; } int main() { vector<int> a; a.push_back(1); a.push_back(5); a.push_back(6); for (int i = 0; i <= 7; i++) { cout << "i=" << i << ": " << find_next_smaller(a, i) << endl; } return 0; }
-
siehe die referenz: lower_bound hat garantierte komplexität O(log(n)) -> ja
//edit dein Code ist genau falsch rum! im ersten if zweig geht er rein weil end!= begin
-
otze schrieb:
dein code ist fast richtig, du must nur den fall abfangen, dass lower_bound dir end zurückgibt.
auto find_next_smaller(const vector<int> &vec, const int key) { auto it = std::lower_bound(vec.begin(), vec.end(), key); if (it == vec.end()) return vec.back(); if (it != vec.begin() && *it > key) { it--; } return *it; }
Und den Fall, dass vec leer ist. Und den Fall, dass key kleiner als alle Elemente von vec ist. Es erscheint mir schlauer, einen Iterator zurückzugeben.
-
ok.
wie kann ich folgendes verwenden? ich weiss es gibt std::less...
auto my_less = (auto &lhs, auto &rhs) -> bool { return lhs < rhs; }; auto it = std::lower_bound(vec.begin(), vec.end(), key, my_less);
-
there we go:
auto my_less = [](const auto &lhs, const auto &rhs) -> bool { return lhs < rhs; };
hat dieser generic Lambda einen nachteil?
-
so gehts auch:
auto find_next_smaller(const vector<int> &vec, const int key) { auto my_less = [&key](const auto &rhs) -> bool { return key <= rhs; }; auto it = std::find_if(vec.begin(), vec.end(), my_less); if (it == vec.end()) { it = (vec.rbegin()+1).base(); } return *it; }
-
newbieeee1 schrieb:
so gehts auch:
auto find_next_smaller(const vector<int> &vec, const int key) { auto my_less = [&key](const auto &rhs) -> bool { return key <= rhs; }; auto it = std::find_if(vec.begin(), vec.end(), my_less); if (it == vec.end()) { it = (vec.rbegin()+1).base(); } return *it; }
Was auch immer du unter "Gehen" verstehst...
find_next_smaller({1,5},4)
liefert 5 zurück.
-
@m.e.: ich gehe davon aus das der vector sortiert ist
-
{1,5}
ist sortiert. Ganz abgesehen von den ganzen Spezialfällen, die du immer noch nicht behandelst. Aber ich wiederhole mich.