multi index sidx.relocate(sidx.end(), si) performance, legality
Hi People, Does anybody know if the code below, which relocates an interator to the end() of an index, is legal? I tried delving into the multi_index code but it is over my head. I ask this because begin() is typically valid as an iterator, but end() never is. The code does appear to work. Also, would it be expensive? I think relocating in a sequenced index is about as expensive as swapping pointers, but I'm not sure. The code: typedef multi_index_container< CacheEntry, indexed_by < ordered_unique< composite_key< CacheEntry, member<CacheEntry,string,&CacheEntry::d_qname>, member<CacheEntry,uint16_t,&CacheEntry::d_qtype> > >, ordered_non_unique<const_mem_fun<CacheEntry,uint32_t,&CacheEntry::getTTD> >, sequenced<> >
cache_t; cache_t d_cache;
// i is given and a valid iterator to the composite key typedef cache_t::nth_index<2>::type sequence_t; sequence_t& sidx=d_cache.get<2>(); sequence_t::iterator si=d_cache.project<2>(i); sidx.relocate(sidx.end(), si); // does this work? -- http://www.PowerDNS.com Open source, database driven DNS Software http://netherlabs.nl Open and Closed source services
Hello Bert, bert hubert ha escrito:
Hi People,
Does anybody know if the code below, which relocates an interator to the end() of an index, is legal? I tried delving into the multi_index code but it is over my head.
I ask this because begin() is typically valid as an iterator, but end() never is. The code does appear to work.
sidx.relocate(sidx.end(), si); // does this work? This is perfectly legal and works as you expect. The confusion arises with your claim that end() is not a valid iterator. I'm adopting the following standard terminology: 1. Dereferenceable iterators are those for which *it has defined behavior. 2. Valid iterators are dereferenceable AND past-the-end iterators. So, end() yields a valid iterator, though not a dereferenceable one. If you look at the reference entry for relocate, it carefully states that: "void relocate(iterator position,iterator i); Requires: position is a valid iterator of the index. i is a valid dereferenceable iterator of the index." So, you can use end() as "position", but not as the "i" argument. [Digression: I'd like to refer you to a place in the standard where the definition of "valid iterator" is given, but alas there's no such a place, and iterator validity is thus a concept without a definition. This is IMHO a defect in the standard. You have a concise definition of iterator validty in SGI docs, though: http://www.sgi.com/tech/stl/InputIterator.html (section "Definitions") As for the standard, there is a definition of "singularity" in 24.1/5 and "valid iterator" can be interpreted as meaning "non-singular iterator"; except that a DR resolution of 2000 seems to break this implicit understanding: http://std.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#208 and adds more confussion to the issue. See also http://tinyurl.com/ocvqn End of digression]
Also, would it be expensive? I think relocating in a sequenced index is about as expensive as swapping pointers, but I'm not sure.
This is extremely cheap as it only involves pointer swapping, no elements are copied, assigned or swapped in the process. HTH, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
participants (1)
-
bert hubert -
Joaquín Mª López Muñoz