ptr_container: splice function in ptr_list

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

ptr_container: splice function in ptr_list

Detlef Mages
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. 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).

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

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

Detlef

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: ptr_container: splice function in ptr_list

Thorsten Ottosen
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
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users