[multi_index] intrusive multi_index poll for interest
Motivation Existing practice have shown the need for intrusive containers. Widely used C++ libraries, such as C++ Standard Library and Boost have long missed such facilities so that users had to refrain from using those due to mandatory element copying or fall back to techniques like two phase construction to insert logically non-copyable elements in containers and initialize them after that or insert pointers to dynamically allocated objects which is rather inelegant and inefficient since containers also dynamically allocate nodes. The most common use cases for intrusive containers are: * when one would like to store non-copyable elements in a container * when it's beneficial to avoid needless data copy in performance critical applications The most prominent example of both the use cases, although written for the most part in C rather than C++, is Linux kernel built solely upon intrusive lists, hash tables and trees. Basic usage An intrusive container is not a container in a stl sense, since it does not own its elements. The sole purpose of an intrusive container is to establish ordering between elements. It's a user responsibility to keep an intrusive container up-to-date by calling replace() to alter fields upon which an order is established as well as erase the nodes from the container prior to node's destruction. Aside from that the look and feel are similar to those of an non-intrusive container. Here is how one would declare an intrusive container, an intrusive node and insert removes nodes: struct record; typedef multi_index_container<intrusive<record> > container; struct record : container::node_type {}; bool operator<(record const& a, record const& b); void insert_sample(container* c) { std::auto_ptr<record> p(new record); if(c->insert(*p).second) p.release(); } void erase_sample(container* c, container::iterator pos) { std::auto_ptr<record const> p(&*pos); c->erase(pos); } Here is how one would make a multi-node, i.e. a node that can be enlisted into several containers simultaneously: struct record; struct tag1; struct tag2; typedef multi_index_container<intrusive<record, tag1> > container1; typedef multi_index_container<intrusive<record, tag2> > container2; struct record : container1::node_type, container2::node_type {}; inline bool operator<(record const& a, record const& b); void insert_sample(container1* c1, container2* c2) { struct guard { container1* c1; container2* c2; std::pair<container1::iterator, bool> i1; std::pair<container2::iterator, bool> i2; std::auto_ptr<record> p; ~guard() { if(i1.second && i2.second) { p.release(); } else { c1->erase(i1.first); c2->erase(i2.first); } } guard(container1* c1, container2* c2, std::auto_ptr<record> p) : c1(c1), c2(c2), i1(c1->end(), 0), i2(c2->end(), 0), p(p) {} } guard(c1, c2, std::auto_ptr<record>(new record)); guard.i1 = c1->insert(*guard.p); guard.i2 = c2->insert(*guard.p); } void erase_sample(container1* c1, container2* c2, record* r) { c1->erase(c1->make_iterator(r)); c2->erase(c2->make_iterator(r)); delete r; } The examples are included in test_intrusive.cpp. Current implementation Current implementation although efficient and mostly functional is a proof of concept only. Further design work is required which we rather unclear about and therefore would like to poll for interest and suggestions. Known limitations: * partial template specialization support is required * dereferencing an intrusive container iterator yields a constant, should probably return non-constant * safe mode is not implemented for make_iterator() exposed api http://www.boost-consulting.com/vault/index.php?action=downloadfile&filename=intrusive_multi_index.tar.bz2&directory=Containers&
On Sat, 31 Dec 2005 18:01:00 -0200, Maxim Yegorushkin <maxim.yegorushkin@gmail.com> wrote:
The most common use cases for intrusive containers are:
* when one would like to store non-copyable elements in a container * when it's beneficial to avoid needless data copy in performance critical applications
For me, it's the ability to get an iterator from a pointer.
An intrusive container is not a container in a stl sense, since it does not own its elements. The sole purpose of an intrusive container is to establish ordering between elements. It's a user responsibility to keep an intrusive container up-to-date by calling replace() to alter fields upon which an order is established as well as erase the nodes from the container prior to node's destruction. Aside from that the look and feel are similar to those of an non-intrusive container.
Frecuently, I have the need to manage elements of some collection that know their place in the collection, and are able to remove themselves when deleted. What does the library do when destroying a non empty collection? An an element of a collection?
struct record;
typedef multi_index_container<intrusive<record> > container;
struct record : container::node_type {};
I like this very much.
Current implementation although efficient and mostly functional is a proof of concept only. Further design work is required which we rather unclear about and therefore would like to poll for interest and suggestions.
I'm interested.
Known limitations: * partial template specialization support is required
I don't care.
* dereferencing an intrusive container iterator yields a constant, should probably return non-constant
I don't know.
* safe mode is not implemented for make_iterator() exposed api
OK. That would be good, but I never used safe mode with multi_index. At least I didn't know I was using it. Bruno
Bruno Martínez ha escrito:
On Sat, 31 Dec 2005 18:01:00 -0200, Maxim Yegorushkin <maxim.yegorushkin@gmail.com> wrote:
The most common use cases for intrusive containers are:
* when one would like to store non-copyable elements in a container * when it's beneficial to avoid needless data copy in performance critical applications
For me, it's the ability to get an iterator from a pointer.
Leaving aside the extra benefits intrusive containers can bring in, the ability of getting an iterator from a pointer to the element is implementable for regular multi_index_containers --matter of fact, this feature is internally used in the preview 1.34 version of Boost.MultiIndex I announced yesterday. * What is the envisioned application scenario for this feature? * Would you advocate having it in Boost.MultiIndex? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Thu, 19 Jan 2006 06:17:02 -0200, Joaquín Mª López Muñoz <joaquin@tid.es> wrote:
Bruno Martínez ha escrito:
On Sat, 31 Dec 2005 18:01:00 -0200, Maxim Yegorushkin <maxim.yegorushkin@gmail.com> wrote:
The most common use cases for intrusive containers are:
* when one would like to store non-copyable elements in a container * when it's beneficial to avoid needless data copy in performance critical applications
For me, it's the ability to get an iterator from a pointer.
Leaving aside the extra benefits intrusive containers can bring in, the ability of getting an iterator from a pointer to the element is implementable for regular multi_index_containers --matter of fact, this feature is internally used in the preview 1.34 version of Boost.MultiIndex I announced yesterday.
Really? Great!
* What is the envisioned application scenario for this feature?
I frequently do something like this: #include <list> struct part; struct whole { std::list<part*> parts; }; struct part { part(whole& w) : my_whole(&w) { me = my_whole->parts.insert(my_whole->parts.end(), this); } ~part() { my_whole->parts.erase(me); } whole* my_whole; std::list<part*>::iterator me; };
* Would you advocate having it in Boost.MultiIndex?
Yes. I would like multi_index to evolve into a solution to representing UML class diagrams in C++, the same way the StateCharts lib does for State Charts. In that case all classes know in which collections they are, so intrusion is natural. I find more natural to just declare in which collections a class is. Bruno
Bruno Martínez ha escrito:
On Thu, 19 Jan 2006 06:17:02 -0200, Joaquín Mª López Muñoz <joaquin@tid.es> wrote:
Bruno Martínez ha escrito:
On Sat, 31 Dec 2005 18:01:00 -0200, Maxim Yegorushkin <maxim.yegorushkin@gmail.com> wrote:
The most common use cases for intrusive containers are:
* when one would like to store non-copyable elements in a container * when it's beneficial to avoid needless data copy in performance critical applications
For me, it's the ability to get an iterator from a pointer.
Leaving aside the extra benefits intrusive containers can bring in, the ability of getting an iterator from a pointer to the element is implementable for regular multi_index_containers --matter of fact, this feature is internally used in the preview 1.34 version of Boost.MultiIndex I announced yesterday.
Really? Great!
* What is the envisioned application scenario for this feature?
I frequently do something like this:
#include <list>
struct part;
struct whole { std::list<part*> parts; };
struct part { part(whole& w) : my_whole(&w) { me = my_whole->parts.insert(my_whole->parts.end(), this); } ~part() { my_whole->parts.erase(me); } whole* my_whole; std::list<part*>::iterator me; };
OK, but seems to me the kind of idioms you propose are best served by an intrusive version of multi_index_container. The "pointer to iterator" feature does not help in isolation, if I'm understanding you right. Joaquín M López Muñoz Telefónica, Investigación y Desarollo
On Thu, 19 Jan 2006 15:39:10 -0200, Joaquín Mª López Muñoz <joaquin@tid.es> wrote:
Bruno Martínez ha escrito:
I frequently do something like this:
#include <list>
struct part;
struct whole { std::list<part*> parts; };
struct part { part(whole& w) : my_whole(&w) { me = my_whole->parts.insert(my_whole->parts.end(), this); } ~part() { my_whole->parts.erase(me); } whole* my_whole; std::list<part*>::iterator me; };
OK, but seems to me the kind of idioms you propose are best served by an intrusive version of multi_index_container. The "pointer to iterator" feature does not help in isolation, if I'm understanding you right.
If I can get an iterator from a pointer, I don't have to store the iterator. I just get an iterator from this. Of course, it's more clear using intrusive containers. Multi_index allows to work with std::set-like containers more easily. For example, you can search for the key, not the whole element. This is sort of intrusive already, and I don't see anything bad in it. Whenever the element knows it's contained, intrusive is clearer. Bruno
Bruno Martínez ha escrito:
On Thu, 19 Jan 2006 15:39:10 -0200, Joaquín Mª López Muñoz <joaquin@tid.es> wrote:
Bruno Martínez ha escrito:
I frequently do something like this:
#include <list>
struct part;
struct whole { std::list<part*> parts; };
struct part { part(whole& w) : my_whole(&w) { me = my_whole->parts.insert(my_whole->parts.end(), this); } ~part() { my_whole->parts.erase(me); } whole* my_whole; std::list<part*>::iterator me; };
OK, but seems to me the kind of idioms you propose are best served by an intrusive version of multi_index_container. The "pointer to iterator" feature does not help in isolation, if I'm understanding you right.
If I can get an iterator from a pointer, I don't have to store the iterator. I just get an iterator from this. Of course, it's more clear using intrusive containers.
Yes, you're right, the "pointer to iterator" feature helps both with intrusive and non-intrusive containers. I got a little confuse in my previous post.
Multi_index allows to work with std::set-like containers more easily. For example, you can search for the key, not the whole element. This is sort of intrusive already, and I don't see anything bad in it. Whenever the element knows it's contained, intrusive is clearer.
OK, you have shown a realistic scenario where the feature is valuable, so I'm putting this into my todo list --probably I can have it in time for 1.34, but I'm very slow writing and checking things :) Any suggestions about the name/syntax? Something like: iterator iter_to(const value_type& x)const; Alas, iterator() can't be used as the name of the member function, since it is already a nested typedef of indices. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Fri, 20 Jan 2006 05:52:22 -0200, Joaquín Mª López Muñoz <joaquin@tid.es> wrote:
OK, you have shown a realistic scenario where the feature is valuable, so I'm putting this into my todo list --probably I can have it in time for 1.34, but I'm very slow writing and checking things :) Any suggestions about the name/syntax? Something like:
iterator iter_to(const value_type& x)const;
iterator_from()? I don't know. I'm spanish speaking too.
Alas, iterator() can't be used as the name of the member function, since it is already a nested typedef of indices.
How is this feature implemented? Substracting char*? Bruno
Bruno Martínez <br1@internet.com.uy> writes:
On Fri, 20 Jan 2006 05:52:22 -0200, Joaquín Mª López Muñoz <joaquin@tid.es> wrote:
OK, you have shown a realistic scenario where the feature is valuable, so I'm putting this into my todo list --probably I can have it in time for 1.34, but I'm very slow writing and checking things :) Any suggestions about the name/syntax? Something like:
iterator iter_to(const value_type& x)const;
iterator_from()?
I don't know. I'm spanish speaking too.
position(const value_type& x) const; or if you are worried about "position" sounding like a verb, get_position(const value_type& x) const; -- Dave Abrahams Boost Consulting www.boost-consulting.com
participants (18)
-
Bruno Martínez -
David Abrahams -
Joaquín Mª López Muñoz -
Maxim Yegorushkin