Re: [Boost-users] ptr_container: splice function in ptr_list

From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2006-04-18 06:52:42

Detlef Mages wrote:
> Hi there,
> 
> I am using a ptr_list as a (huge) container where I can store objects 
> (different types of a single interface). I am using a ptr_list as I need to 
> store iterators to elements that do not invalidate when reordering the 
> structure.

Just remember that non of the pointer containers invalidate references 
or pointers when reordering the elements. So it might be that ptr_vector
or ptr_deque is *much* faster for you.

> Though a standard function of the STL list is missing: "splice".
> 
> I know, I can mimic "splice" by "transfer", though I think that this results 
> in a runtime complexity of O(N) whereas "splice" would be O(1). 

True. But this big-O notation is less precise here than normally. See below.

> Is there a way to add splice to ptr_list? Or will there be problems I haven't 
> thought of? 

I can't think of any reason I havn't added splice() for pointer list 
currently. I suspect it is because transfer() was intended to provide 
the same functionality ... though it should be optmized for ptr_list 
using splice() (when both source and target are ptr_list).

> If you give me some hint I could take a shot on this functionality.

Please consider if ptr_list really is the right choice here: is 
insertion in the middle of the container a frequent operation? And is 
the container fairly large (eg. > 500 elements).

If not, ptr_vector is probably a better choice. And transfer() is an 
O(n) operation, but

1. it only copies n pointers (not objects)

2. it maximally lead to one heap-allocation to expand the buffer 
(possibly none with use of reserve())

So ptr_vector can give you a somewhat efficient splice

-Thorsten