appending/joining STL::deque/list containers in constant time

[Carter]

This is probably somewhat of a beginners question but I am unfamiliar
with alot of aspects of C++. What is the correct way to append
multiple STL containers together in constant time. Obviously you can
do this with a linked list but is it possible to do the same thing
with the standard containers?

Thanks in advance,

Carter.

 

[Christopher]

This is probably somewhat of a beginners question but I am unfamiliar
with alot of aspects of C++. What is the correct way to append
multiple STL containers together in constant time. Obviously you can
do this with a linked list but is it possible to do the same thing
with the standard containers?

Thanks in advance,

Carter.

If they both contain the same data type, then iterate through one
while pushing onto the other?
a linked list is a standard STL container btw. All STL containers
provide an iterator which allows access to the underlying data and all
STL container have some kind of insertion method. Depending on the
containers in question, some allow a range of iterators for insertion.

 

[Carter]

If they both contain the same data type, then iterate through one
while pushing onto the other?
a linked list is a standard STL container btw. All STL containers
provide an iterator which allows access to the underlying data and all
STL container have some kind of insertion method. Depending on the
containers in question, some allow a range of iterators for insertion.

Well this works in time proportional to the lengths of the lists in
question. I was hoping for something which could like a hand coded
link list do a bit better. i.e. be proportional to the number of
merged lists. i.e. if for example I crafted a hand coded container
like this

template<typename T>
struct elem
{
T data;
elem* prev, next;
};

template<typename T>
struct
{
elem<T>* head, tail;
};

I could just set tail->next of list A to head of B and head->prev of
list B to tail of A. etc. which seems like a much faster operation
than manually inserting each element.

Regards,

Carter.

 

[Jerry Coffin]

This is probably somewhat of a beginners question but I am unfamiliar
with alot of aspects of C++. What is the correct way to append
multiple STL containers together in constant time. Obviously you can
do this with a linked list but is it possible to do the same thing
with the standard containers?

If you're using std::list, you can use list::splice to do the job. I
don't believe any of the other standard containers offers an equivalent.

 

[Christopher]

Well this works in time proportional to the lengths of the lists in
question. I was hoping for something which could like a hand coded
link list do a bit better. i.e. be proportional to the number of
merged lists. i.e. if for example I crafted a hand coded container
like this

template<typename T>
struct elem
{
T data;
elem* prev, next;

};

template<typename T>
struct
{
elem<T>* head, tail;

};

I could just set tail->next of list A to head of B and head->prev of
list B to tail of A. etc. which seems like a much faster operation
than manually inserting each element.

Regards,

Carter.

No you couldn't.
Because anyone performing a subsequent operation on A would then be
altering B and vica versa. you know longer have two independant
objects. It would indeed be very bad if you did not make a copy and
started having internals of an independent object pointing to memory
used by another. Shallow copy vs Deep copy, you want the latter.

 

[Carter]

If you're using std::list, you can use list::splice to do the job. I
don't believe any of the other standard containers offers an equivalent.

--
Later,
Jerry.

The universe is a figment of its own imagination.

I will give this a try thanks. It seems to be an interesting
limitation that
for the std::deque you cannot do the same thing. In my cast a
std::list should do
the trick though. I understand the objection raised too- but it seems
a bit
unfortunate that given we have library of linked and doubly linked
lists that
you cannot perform shallow merging in cases where the containers being
merged from
are being discarded.

Regards,

Carter.

 

[Jerry Coffin]

(e-mail address removed)>, (e-mail address removed)
says...

[ ... ]

I understand the objection raised too- but it seems a bit
unfortunate that given we have library of linked and doubly linked
lists that you cannot perform shallow merging in cases where the
containers being merged from are being discarded.

That's exactly what list::splice does -- a destructive movement of
elements from one list to another in constant time.