A solution for a fast std::list::size() *and* a fast std::list::splice()

K

Kai-Uwe Bux

Jerry said:
[ ... ]
a) You got distracted by a minor issue that arose from code
simplification for the sake of exposition.

Well, I'll admit about all I can really look at is what's actually in a
post...

True. I just wanted to get the main point across quickly. That failed. Hence
I posted the complete version.
Okay, so with enough extra work you can (to at least some degree) work
around the most obvious shortcomings of using iterators in this way,

I have yet to see the less obvious shortcomings (that you seem to allude
to), and the others are just eliminated, not "(at least to some degree)
worked around". Since you are insinuating the existence of more problems,
please be more specific.

(I actually take some offense in this kind of rhethoric.)

I also should add that the additional work is only needed to _enforce_
contracts (which are stated in the documentation that says, e.g., that
unregistering an action twice is undefined behavior). It does not change
the interface or the way the class can be used. It is purely a means of
debugging, and I am considering to rig it so that the first version will be
used when the code is compiled with NDEBUG defined.

but I'm left wondering whether (and if so how) there's a real advantage.
So far, I haven't seen one...

Advantage compared to what? You have neither offered an alternative
implementation of command_bag nor a class with a different interface that
could serve its purpose. Once you do so, we can discuss relative merits and
shortcomings of both approaches meaningfully.

[ ... ]
b) The drawback of the approach using std::set<> is not so much that it
is marginally less efficient. The major drawback is that it imposes
additional conceptual requirements on the objects you can register: they
must be comparable with one another. This is generally not feasible for
objects of type tr1::function< void( whatever ) >.

I'll admit that when I did it, I was using addresses of functions (this
was a while ago, long before TR1 was written). Offhand, I'm hard put to
see the problem though: instantiations of tr1::function should be
objects with addresses, and std::less is required to support comparison
of addresses, even in cases where the built-in < operator wouldn't (e.g.
separate objects).

If you want to use address comparison to find the registered function and
remove it, the observer and the command_bag need to use the same object
(i.e., one of them at least is using a pointer or a reference). Off hand,
that creates the question who should _own_ that object.

Since in the proposed interface, for the sake of flexibility, you can
register anything that looks like a function

template < typename T >
removal_ticket register ( T const & t );

the function object must be created within the command_bag. Thus, in one
possible interpretation, you are suggesting that instead of an iterator, I
should return a raw pointer to the function object created (otherwise, the
client will never know the address and will never be able to unregister the
command). Since that is in direct contradiction to what you said earlier
about the evil of returning pointers into the innards of a data structure,
I will dismiss this interpretation right away. I just note that this
approach is morally equivalent to the one presented. It can be made safe in
that same way.

So let us assume that the obligation to create the function object lies
within the observer. That is obvious less convenient. Also, in that case, we
have to wonder how to pass the address of said object to the command_bag.

void register ( function_object );

is stupid since address comparison will not work.

void register ( function_object const & );

will not work since the initialization of const references is allowed to
make copies (which then would render address comparison useless). I think,
this will be fixed with the next revision of the standard.

void register ( function_object & );

is not const correct since tr1::function has a const operator() wherefore
command_bag can and should promise not to modify the function object.

void register ( function_object const * );

is the only alternative left. That is ugly, but it will work.

The main problem, however, is the coupling that you get from sharing the
address to a common object. In this setup, the command_bag will just store
pointers to function objects internally and will remove them upon the
request of the obeserver. The observer, however, has to hold onto the
function object and may not forget to unregister this object since the
pointer stored in the command_bag otherwise will be dangling (note that we
cannot make a copy because of address comparison). This creates a coupling
between the command_bag and its users that the return_ticket approach
avoids. (To be fair, depending on what the function objects do, this tight
coupling may exist anyway. However, the command_bag itself should not
introduce the coupling.)

To be more specific, consider:

int main ( void ) {
command_bag the_bag;
{
observer the_obs;
the_bag.register ( the_obs.my_functor() );
}
the_bag.execute();
}

where my_functor() returns the address of a member of the_obs that happens
to be a function object of the right kind. In this case, the observer
better unregister the action in its destructor for otherwise there is
undefined behavior.


It appears that in order to avoid the yet to be seen less obvious
shortcomings of a list based approach you end up with a solution that is
less convenient (clients have to convert their functors into tr1::function
objects) and creates a tighter coupling between command_bag and its
clients. I will note that none of these issues is visible if you ditch the
flexibility of using functors and insist on function pointers.


In short, I would like to actually see (in code!) your non-list based
alternative solution that is as flexible, safe, and convenient as
command_bag.


Best

Kai-Uwe Bux
 
K

Kai-Uwe Bux

Jerry said:
[ ... ]
(I actually take some offense in this kind of rhethoric.)

I apologize -- I intended no offense.

Looking back, I may have overreacted (and probably I was more annoyed than
offended). In any case, I did not think that you _intended_ to offend me.


Thanks and
best regards

Kai-Uwe Bux
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,769
Messages
2,569,581
Members
45,056
Latest member
GlycogenSupporthealth

Latest Threads

Top