Re: [boost] [multi_index] User-defined indices

From: Andrey Semashev (andysem_at_[hidden])
Date: 2007-06-12 12:05:00

Hello Joaquín,

Tuesday, June 12, 2007, 5:33:41 PM, you wrote:

> Andrey Semashev ha escrito:
> [...]

>> But there may be ways of decoupling indices. For example, you may
>> implement these final_* functions so they call each index's protected
>> function separately. There would be no need to call base class
>> recursively in each index and I don't think it's going to make a
>> performance impact. This is essentially what I was writing above.
>> In addition this might help to encapsulate exception safety burden
>> in these final_* functions instead of distributing it in indices.

> I thought about this more decoupled approach when first designing the
> lib, but it presents serious problems. Let me elaborate: suppose we
> implement final_insert_() like this (pseudocode follows):

[snip]

> This is suboptimal because when a given index bans an insertion we have to
> undo all the previous work by calling erase_() on the preceding indices.
> We can try to remedy this by writing the code as follows:

[snip code with can_insert_]

> But then another problem pops up: the code in can_insert_() performs some
> calculations that must be repeated when doing the insertion proper. It'd be
> so much better if we can somehow store this info as some sort of local data
> that can later be used by insert_()...

Yes, I'm aware of this problem. I solved it in my implementations by
introducing special members of the index class. They are not
seen to user and only participate as a temporary storage in these
operations. In fact, insertions seems to be the only operation where
the problem arises, and in most cases the storage needed is quite
small (either an iterator hint or a hash result), so it doesn't make
the container significantly larger.
I understand that this solution looks awkward, but that's just an
optimization, after all. And it allows to simplify indices, which I
consider as a great advantage.

> and the simplest way to do this is
> to let the insert_() functions the responsibility to cascade the call by
> themselves:

[snip]

> I don't know if the explanation is clear enough... Basically, there might be
> conceptually cleaner ways to implement the backbone functionality of
> a multi_index_container, but I doubt they can compare to the current one
> in terms of efficiency. The drawback is that writing an index becomes an
> admittedly arduous task.

Well, that's your call. I can only hope then that your current
interface will be documented some day.

-- 
Best regards,
 Andrey                            mailto:andysem_at_[hidden]