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