Re: [boost] [multi_index] feature request

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2005-08-26 02:26:13

Hello Maxim, excuse my answering so late.

Maxim Yegorushkin ha escrito:

> [multi_index] feature request
>
> In my code I often use collections of noncopyable objects and yet I need
> to have
> them indexed. The usual solution is to store pointers to the objects in the
> index (be it a std::set/map or boost::multi_index). This leads to two
> allocations: the first for the object and the second for the index node.
> For me
> it would be more natural and effective to embed the index node in the
> object, so
> that the container is obviated from allocating nodes and only maintains
> indexes. This also would make all container operations nothrow, since
> element
> insertion and removal requires only node pointer manipulations and using
> the
> comparer object which is typically nothrow.
>

In most cases, but not always: for instance, hashed indices maintain
other internal data structures apart from the nodes themselves
(namely a bucket array), so you cannot get rid of the allocator entirely.

>
> In my work I use my own intrusive_list which has proved itself quite
> useful and
> effective. The syntax is:
>
>      struct noncopyable_object;
>      typedef intrusive_list<noncopyable_object> list;
>      struct noncopyable_object
>          : list::node // embed the list node in the class
>      {
>          // ...
>      };
>
> Will such a feature ever make it to multi_index?
>

Seems like it could be implemented in principle: it would require
some sort of policy design on the indices to indicate whether
internal allocation is performed or not. Apart from this, some other
tweakings might be necessary.
I've been reading Olaf Krzikalla's intrusive containers proposal to gather
some ideas, maybe it would be a good idea to wait to see how far Olaf's
work goes and then try to copy his design into Boost.MultiIndex.

Apart from this, I'm not sure this intrusive idea will raise much interest
(well, at least there's one interested party:). Also, my current roadmap
includes random access indices (http://tinyurl.com/bnscx), ranked indices
and, maybe, a dynamic multi_index_container, so I'll probably
be pretty busy for half a year or so.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo