Hi Igor, ________________________________________ De: boost-users-bounces@lists.boost.org [boost-users-bounces@lists.boost.org] En nombre de Igor R [boost.lists@gmail.com] Enviado el: domingo, 13 de julio de 2008 14:12 Para: boost-users@lists.boost.org Asunto: [Boost-users] [boost-users][multi-index] hashed identity: lookup by hash value
Hello,
Given a multi_index_container with 1 hashed unique identity key (kind of unordered set) - is there a "trivial" way to find a value by its hash-code?
There is a trivial method but it relies on undocumented implementation features of hashed indices: std::size_t h=boost::hash<Element>()(...); std::size_t n=h%elementSet.bucket_count(); // the element lies in the range [first,last). In most cases (i.e. if the hash // function is doing a good job), this range only contains one element. ElementSet::iterator first=elementSet.begin(n), last=elementSet.end(n); As I said, this relies on the knowledge that an element with hash value h goes to the bucket in the position h%bucket_count. So, my strong advise is *not to use this*. The correct approach is the one you are already exploring below.
Currently, I'm using a trick with supplying custom hashing/equality functors, but probably there's some more straightforward way? [...] struct ElementEq { bool operator()(size_t x, const Element &y) const { return x == boost::hash<Element>()(y); } };
Strictly speaking, your ElementEq struct has to provide also the operator()(const Element&,size_t): struct ElementEq { bool operator()(const Element &x, size_t y) const { return boost::hash<Element>()(x) == y; } bool operator()(size_t x, const Element &y) const { return x == boost::hash<Element>()(y); } }; (In practice it works with the second oeprator() only, but this is again undocumented). [...]
int main() { ElementSet elementSet; //.... // I've got here a hash-value of an element, and I wish to find it in the set. ElementSet::iterator pos = elementSet.find(hashValue, ElementHashHasher(), ElementEq()); }
You have to take into account that there is a possibility that find() gets you a distinct element with the same hash value, so you'd better use equal_range() and postprocess the obtained range to find the exact element you're after. Other than this, the technique you describe is absolutely OK and the one I'd recommend to do what you want. Is it not working for you? I've written a small code snippet to try it myself and everything seems to work OK (attached). Joaquín M López Muñoz Telefónica, Investigación y Desarrollo