[containers] defining the insertion point of non-unique keys
Hi @boost, I'm looking for the solution to the following problem: there is a collection of objects and I want to find a particular object by two different keys. The first key is unique, so there is no problem. The second key however is non-unique and if I search for an object using this key I want to find the element that was inserted last in that sequence. Neither boost::multindex nor boost:intrusive seems to have solutions right at hand. If using boost::multindex I could try to insert a new element in the non-unique sequence using the lower_bound iterator of that sequence as a hint. However it is not documented that in that case the element is always inserted before the hint. Same is true for boost:intrusive::multi_set/multi_map. And I'm not able to swap the position of two adjacent elements in a multi_set or multi_map, if they have equal keys. To illustrate the problem, here is some code: struct A { int a; // non-unique key void* b; // unique key // stuff }; using namespace boost::multi_index; typedef multi_index_container<A, indexed_by< ordered_non_unique<member<A,int,&A::a> >, ordered_unique<member<A,void*,&A::b> > > > tCollection; void foo(tCollection& collection, int key) { typedef tCollection::nth_index<0>::type tItByInt; tItByInt i = collection.get<0>().lower_bound(key); // use the current lower bound as a hint: tItByInt insertPos = collection.get<0>.insert(i, getObject(key)); // the big question: does the assertion holds? assert(collection.get<0>().lower_bound(key) == insertPos); } Best regards Olaf Krzikalla
Olaf Krzikalla escribió:
Hi @boost,
I'm looking for the solution to the following problem: there is a collection of objects and I want to find a particular object by two different keys. The first key is unique, so there is no problem. The second key however is non-unique and if I search for an object using this key I want to find the element that was inserted last in that sequence. Neither boost::multindex nor boost:intrusive seems to have solutions right at hand. If using boost::multindex I could try to insert a new element in the non-unique sequence using the lower_bound iterator of that sequence as a hint. However it is not documented that in that case the element is always inserted before the hint. [...]
Hi Olaf, Starting with Boost 1.35, Boost.MultiIndex ordered indices guarantee that hinted insertion takes place as close as possible to the hint, please take a look at http://www.boost.org/libs/multi_index/doc/release_notes.html#boost_1_35 . But you're right this is not stated in the docs. I'll change that. It'd help if you can file a ticket for the issue so that I don't forget. Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Hi Joaquin,
Starting with Boost 1.35, Boost.MultiIndex ordered indices guarantee that hinted insertion takes place as close as possible to the hint, please take a look at http://www.boost.org/libs/multi_index/doc/release_notes.html#boost_1_35 . But what means "as close as possible"? Is "before the hint" closer then "after the hint" by definition? I doubt it. DR233 and the resolution isn't more clear in that respect too and I'm going to raise the question in csc++ if I don't find a clarification elsewhere. boost::intrusive has introduced insert_before (@Ion: the function is nowhere stated in the release notes for 1.41 but I didn't found it in 1.40), which does exactly what I need. However using boost::intrusive is somewhat more difficult (even if for a particular reason I know how to use it ;-)
But you're right this is not stated in the docs. I'll change that. It'd help if you can file a ticket for the issue so that I don't forget. I'll do that.
Best regards Olaf
Hi again, I think I got it. I overread the "prior" in: "t is inserted as close as possible to the position just prior to p." To a certain degree the position described above can be seen as the position between p and its predecessor (if it exists), can't it? Thus boost:multindex complies to N1780(?). Best regards Olaf
Olaf Krzikalla <olaf.krzikalla <at> tu-dresden.de> writes:
Hi again,
I think I got it. I overread the "prior" in:
"t is inserted as close as possible to the position just prior to p."
To a certain degree the position described above can be seen as the position between p and its predecessor (if it exists), can't it?
No, it's more general than this: assume we've got a container with elements a1, a2, ... , an, k1, k2, ... , km, b1, b2, ... , bl where k1, ... , km are equivalent (and the rest are not equivalent to these). Put A=[a1,k1), K=[k1,b1), B=[b1,end]. Now if we insert an element equivalent to these in K using hint p, then: * if p is in A, insertion takes place before k1, * if p is in K, insertion takes place before p, * if p is in B, insertion takes place before b1.
Thus boost:multindex complies to N1780(?).
Yes. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Joaquin M Lopez Munoz schrieb:
No, it's more general than this: assume we've got a container with elements
a1, a2, ... , an, k1, k2, ... , km, b1, b2, ... , bl
where k1, ... , km are equivalent (and the rest are not equivalent to these). Put A=[a1,k1), K=[k1,b1), B=[b1,end]. Now if we insert an element equivalent to these in K using hint p, then:
* if p is in A, insertion takes place before k1, * if p is in K, insertion takes place before p, * if p is in B, insertion takes place before b1. That was clear to me. However thanks for the example. I can use it to describe the point of my uncertainty: assume our hint points to k2 and we want to insert an element with key k (say kn). If "the position just prior to k2" means k1, then it's unclear whether kn is inserted before k1 or after k1 - both positions are equal close to k1. However if "the position just prior to k2" means the position between k1 and k2, then all is well defined and works as intended.
Thus boost:multindex complies to N1780(?). Yes. Wonderful :-)
Best regards Olaf
Joaquin M Lopez Munoz schrieb:
No, it's more general than this: assume we've got a container with elements
a1, a2, ... , an, k1, k2, ... , km, b1, b2, ... , bl
where k1, ... , km are equivalent (and the rest are not equivalent to these). Put A=[a1,k1), K=[k1,b1), B=[b1,end]. Now if we insert an element equivalent to these in K using hint p, then:
* if p is in A, insertion takes place before k1, * if p is in K, insertion takes place before p, * if p is in B, insertion takes place before b1. That was clear to me. However thanks for the example. I can use it to describe the point of my uncertainty: assume our hint points to k2 and we want to insert an element with key k (say kn). If "the position just prior to k2" means k1, then it's unclear whether kn is inserted before k1 or after k1 - both positions are equal close to k1. However if "the position just prior to k2" means the position between k1 and k2, then all is well defined and works as intended.
Thus boost:multindex complies to N1780(?). Yes. Wonderful :-)
Best regards Olaf
Olaf Krzikalla <olaf.krzikalla <at> tu-dresden.de> writes:
Joaquin M Lopez Munoz schrieb:
* if p is in A, insertion takes place before k1, * if p is in K, insertion takes place before p, * if p is in B, insertion takes place before b1.
That was clear to me. However thanks for the example. I can use it to describe the point of my uncertainty: assume our hint points to k2 and we want to insert an element with key k (say kn). If "the position just prior to k2" means k1, then it's unclear whether kn is inserted before k1 or after k1 - both positions are equal close to k1. However if "the position just prior to k2" means the position between k1 and k2, then all is well defined and works as intended.
It is the latter --the position between k1 and k2. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
2009/12/18 Joaquin M Lopez Munoz <joaquin@tid.es>:
No, it's more general than this: assume we've got a container with elements
a1, a2, ... , an, k1, k2, ... , km, b1, b2, ... , bl
where k1, ... , km are equivalent (and the rest are not equivalent to these). Put A=[a1,k1), K=[k1,b1), B=[b1,end]. Now if we insert an element equivalent to these in K using hint p, then:
* if p is in A, insertion takes place before k1, * if p is in K, insertion takes place before p, * if p is in B, insertion takes place before b1.
Looking at n3000, only associative containers' 'insert' is specified this way. For 'emplace_hint', it says: equivalent to a.emplace(std::forward<Args>(args)...). [...] Implementations are permitted to ignore the hint. which I think means that the element is placed at the end of the equivalent elements. There are similar definitions for unordered containers' 'insert' with hint and 'emplace_hint'. Presumably this is a defect? Daniel
Daniel James <daniel_james <at> fmail.co.uk> writes:
2009/12/18 Joaquin M Lopez Munoz <joaquin <at> tid.es>:
No, it's more general than this: assume we've got a container with elements
a1, a2, ... , an, k1, k2, ... , km, b1, b2, ... , bl
where k1, ... , km are equivalent (and the rest are not equivalent to these). Put A=[a1,k1), K=[k1,b1), B=[b1,end]. Now if we insert an element equivalent to these in K using hint p, then:
* if p is in A, insertion takes place before k1, * if p is in K, insertion takes place before p, * if p is in B, insertion takes place before b1.
Looking at n3000, only associative containers' 'insert' is specified this way. For 'emplace_hint', it says:
equivalent to a.emplace(std::forward<Args>(args)...). [...] Implementations are permitted to ignore the hint.
which I think means that the element is placed at the end of the equivalent elements. There are similar definitions for unordered containers' 'insert' with hint and 'emplace_hint'. Presumably this is a defect?
I think you've spotted a defect in the case of associative containers. As for the unordered associative containers I don't see an issue, since insert in this case does not specify in any case the point of insertion (except to the extent that equivalent elements must stay together.) Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
participants (4)
-
Daniel James -
Joaquin M Lopez Munoz -
joaquin＠tid.es
-
Olaf Krzikalla