[C++] iterator retourneren bij binary_search

[Postie]

Ik heb een vector, daar zitten CAreaSize objecten in. Deze objecten hebben oa een public variabele size. Nu doorzoek ik met de standaard binary_search of er al een element aangemaakt is waarin size een bepaalde waarde heeft (de vector is gesorteerd). Nu zou ik graag ook de iterator terug willen op welke plek dit object gevonden is, zodat ik het aan kan passen. Is daar een (eenvoudige) oplossing voor? Dus een soort binary_get ipv binary_search.

[remco_k]

C++:

return iterator; ?

Verder zou het makkelijk zijn als je een stukje (psuedo) code post zodat duidelijk word hoe je naar de functie gaat en wat je precies doet.

[.oisyn]

Mijn eerste reactie was: "binary_search returnt toch gewoon een iterator ". Ik zie nu dat ie idd gewoon een bool returnt. Wat ontzettend nutteloos en totaal niet consistent met de overige equivalente functies.

Er zit weinig anders op dan zelf een implementatie maken (vrij simpel), of door een andere datastructuur te gebruiken (bijv. std::set)

remco_k: uhm, z'n post is heel duidelijk hoor. std::binary_search is gewoon een standaard functie.

[ Voor 15% gewijzigd door .oisyn op 19-07-2007 17:34 ]

[Postie]

nou, ik doe dus een binary_search op de vector en deze retourneert een false of true. Maar nu wil ik ook weten waar deze search dan de betreffende waarde gevonden heeft. Ik gebruik de standaard binary_search van de C++ algorithm library. Hieronder wat regels code (niet relevante delen zijn weggelaten):
:

C++:

class CAreaSize
{
public:
  int size;
  int labelIndex;
}

class Areas {

private:
  vector<CAreaSize> AllAreas;

if(binary_search(AllAreas.begin(), AllAreas.end(), index))  {
..
// hier wil ik weten op welke lokatie de waarde 'index' gevonden is in de vector AllAreas
}

bool operator<(const int s, const CAreaSize& a) {
  return s < a.labelIndex;
}

bool operator<(const CAreaSize& a, const int s) {
  return a.labelIndex < s;
}
}

Maar nu wil ik niet alleen true of false maar ook de lokatie waar deze waarde dan gevonden is. Ik ben absoluut niet goed in C++ maar het moest nu eenmaal in die taal.

[JeromeB]

Ik begrijp std::binary_search niet helemaal, maar voldoet std::find in dit geval niet? Of is die niet snel genoeg?

Misschien voldoet std::lower_bound of std::upper_bound. Die doen volgensmij ook een binary-search en geven wel een iterator terug.

[ Voor 51% gewijzigd door JeromeB op 19-07-2007 17:39 ]

[.oisyn]

binary_search is O(log N), find is O(N).

Nu ik erover denk kun je ook gewoon std::lower_bound() gebruiken, en dat is waarschijnlijk ook meteen de reden waarom std::binary_search() een bool returnt. std::lower_bound() geeft namelijk het eerste element dat groter of gelijk is aan het element dat je zoekt. Je kunt ook std::equal_range() gebruiken, die in principe de lower_bound en de upper_bound geeft, oftewel de range van elementen die aan je searchquery voldoen. Zijn beide iterators hetzelfde, dan is er niets gevonden.

[Postie]

bedankt, dan zal ik dat eens gaan proberen maar is wel een omslachtige manier om een element te vinden.

[.oisyn]

Hoezo? Het doet precies wat je wilt. Namelijk een binary search naar een element, die dat element teruggeeft, of het volgende element als je element er niet in staat.