binary_search - an welchem Index gefunden?
-
std::binary_search gibt einen bool zurück, ob das Element gefunden wurde, aber nicht, an welcher Position.
gibt es eine equivalente Funktion, oder muß ich die Suche selbst implementieren?
Ich habe einen sortierten Vektor, und benötige einen Iterator zu dem gefundenen Element.
-
std::find
-
sucht linear, oder?
(will ich natürlich nicht...)
-
namespace stdext { template<class _FwdIt, class _Ty, class _Pr> inline _FwdIt binary_search( _FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Pr _Pred) { // find first [_First2, _Last2) satisfying _Pred _First = std::lower_bound(_First, _Last, _Val, _Pred); if (_First != _Last && !_Pred(_Val, *_First)) return _First; else return _Last; } }
-
-
@ssm: danke, war ich auch schon dabei, nehme aber erstmal lower_bound.
Da kann ich noch ne optimierung reinbasteln (mein Suchwert ist "kleiner" als der zu findende)
jetzt ärgere ich mich nur noch mit vector<pair<const X, X> >.swap() rum -
typedef std::pair<const int, int> T; std::vector<T> v1, v2; v1.push_back(std::make_pair(1,1)); v1.swap(v2);geht natürlich nicht
(dachte erst, ist die blöde VC6 - STL, aber nee, ist die swap-implementaiton für verschiedene allocators)
-
peterchen schrieb:
jetzt ärgere ich mich nur noch mit vector<pair<const X, X> >.swap() rum -
typedef std::pair<const int, int> T; std::vector<T> v1, v2; v1.push_back(std::make_pair(1,1)); v1.swap(v2);geht natürlich nicht
(dachte erst, ist die blöde VC6 - STL, aber nee, ist die swap-implementaiton für verschiedene allocators)typedef std::pair<const int, int> T; T p1 = std::make_pair(1,1); T p2; p2 = p1;
benutz std::pair<int, int>
-
Ich will mir die Kopie sparen (deswegen swap), und pair::first ist das Sortierkriterium, deswegen wollt' ich es const haben. (mit dem const geht aber auch das p2=p1 nicht).
Hab das pair erst einmal non-const, muß der client halt aufpassen...
-
wieso einfach std::map<int, int> nicht benutzen
-
da komm ich her
Mein leidensweg:
map, die einmal aufgebaut sich nicht mehr ändert, mehrere Instanzen mit vielen kleinen Einträgen (ID --> Index/Pointer/o.ä.), und custom allocator kannst' vergessen.
-
peterchen schrieb:
map, die einmal aufgebaut sich nicht mehr ändert
meinst du, dass du sort predicat ändern willst?
peterchen schrieb:
mehrere Instanzen mit vielen kleinen Einträgen (ID --> Index/Pointer/o.ä.), und custom allocator kannst' vergessen.
map hat doch auch einen allocator
-
meinst du, dass du sort predicat ändern willst?
Nein, ich habe eine (unsortiertze) liste mit Wertepaaren, und brauche (z.T. bidirektionalen) schnellen Zugriff. Die Elemente sind z.T. Indizees / Referenzen mit relativ teuren Vergleichsoperatoren, daher binäre Suche.
Die Elemente pro Liste sind bekannt, also könnte ich pro liste im Prinzip mit einer einzigen Allokation arbeiten.allocator hat die map schon - aber der ist per Standard stateless. Der Standard läßt zwar ein paar Schlupflöcher (weswegen z.B. das swap nicht geht), und ein paar STL-Implementationen erlauben state explizit. Das ist aber ein Minenfeld sondergleichen, außerdem soll das ganze auch unter ne mickrigen STL ohne rebind laufen.
-
[quote="peterchen]Nein, ich habe eine (unsortiertze) liste mit Wertepaaren, und brauche (z.T. bidirektionalen) schnellen Zugriff. [/quote]
-
Danke - ich kenne Joaquíns Multi-Index-Container, hab' ich aber das gleiche problem mit dem Allocator.