std::bsearch
| Definiert in Header <cstdlib> |
||
| void* bsearch( const void* key, const void* ptr, std::size_t count, std::size_t size, /* c-compare-pred */* comp ); |
(1) | |
| extern "C" using /* c-compare-pred */ = int(const void*, const void*); extern "C++" using /* compare-pred */ = int(const void*, const void*); |
(2) | (nur Exposition*) |
Sucht ein Element, das gleich dem Element ist, auf das von key gezeigt wird, in einem Array, auf das von ptr gezeigt wird. Das Array enthält count Elemente mit jeweils size Bytes und muss in Bezug auf das Objekt, auf das von key gezeigt wird, partitioniert sein, d. h., alle Elemente, die kleiner sind, müssen vor allen Elementen erscheinen, die gleich dem Schlüsselobjekt sind, und diese müssen vor allen Elementen erscheinen, die größer als das Schlüsselobjekt sind. Ein vollständig sortiertes Array erfüllt diese Anforderungen. Die Elemente werden mithilfe der Funktion verglichen, auf die von comp gezeigt wird.
Das Verhalten ist undefiniert, wenn das Array nicht bereits aufsteigend in Bezug auf den Schlüssel partitioniert ist, gemäß demselben Kriterium, das comp verwendet.
Wenn das Array mehrere Elemente enthält, die comp als gleich dem gesuchten Element angeben würde, ist es nicht spezifiziert, welches Element die Funktion als Ergebnis zurückgibt.
Inhalt |
[bearbeiten] Parameter
| key | - | Zeiger auf das zu suchende Element |
| ptr | - | Zeiger auf das zu untersuchende Array |
| zählt | - | Anzahl der Elemente im Array |
| size | - | Größe jedes Elements im Array in Bytes |
| comp | - | Vergleichsfunktion, die einen negativen ganzzahligen Wert zurückgibt, wenn das erste Argument kleiner als das zweite ist, einen positiven ganzzahligen Wert, wenn das erste Argument größer als das zweite ist, und Null, wenn die Argumente äquivalent sind. key wird als erstes Argument übergeben, ein Element aus dem Array als zweites. Die Signatur der Vergleichsfunktion sollte äquivalent zu Folgendem sein int cmp(const void *a, const void *b); Die Funktion darf die ihr übergebenen Objekte nicht ändern und muss konsistente Ergebnisse zurückgeben, wenn sie für dieselben Objekte aufgerufen wird, unabhängig von ihrer Position im Array. |
[bearbeiten] Rückgabewert
Zeiger auf das gefundene Element oder Nullzeiger, wenn das Element nicht gefunden wurde.
[bearbeiten] Hinweise
Trotz des Namens erfordern weder die C- noch die POSIX-Standards, dass diese Funktion mithilfe einer binären Suche implementiert wird, noch machen sie Komplexitätsgarantien.
Die beiden von der C++-Standardbibliothek bereitgestellten Überladungen sind unterschiedlich, da die Typen des Parameters comp unterschiedlich sind (die Sprachbindung ist Teil seines Typs).
[bearbeiten] Beispiel
#include <array> #include <cstdlib> #include <iostream> template<typename T> int compare(const void *a, const void *b) { const auto &arg1 = *(static_cast<const T*>(a)); const auto &arg2 = *(static_cast<const T*>(b)); const auto cmp = arg1 <=> arg2; return cmp < 0 ? -1 : cmp > 0 ? +1 : 0; } int main() { std::array arr{1, 2, 3, 4, 5, 6, 7, 8}; for (const int key : {4, 8, 9}) { const int* p = static_cast<int*>( std::bsearch(&key, arr.data(), arr.size(), sizeof(decltype(arr)::value_type), compare<int>)); std::cout << "value " << key; if (p) std::cout << " found at position " << (p - arr.data()) << '\n'; else std::cout << " not found\n"; } }
Ausgabe
value 4 found at position 3 value 8 found at position 7 value 9 not found
[bearbeiten] Siehe auch
| sortiert einen Bereich von Elementen unbekannten Typs (Funktion) | |
| gibt den Bereich von Elementen zurück, die einem bestimmten Schlüssel entsprechen (Funktionstemplate) | |
| C-Dokumentation für bsearch
| |
