Jump to content
  • Advertisement
Sign in to follow this  
MetaKnight

Insert a list into a list

This topic is 4612 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I put this here because I really should know this by now but: Using STL vectors, how do I insert a vector into another? is there any way of doing this without having to transverse the whole list? so V1 : 1 3 5 V2 : 2 4 6 V1.insert(v2) V1: 1 2 3 4 5 6

Share this post


Link to post
Share on other sites
Advertisement
You can use the insert() function with a range in order to insert the contents of one vector into another. ex:

vector1.insert(vectorn1.end(), vector2.begin(), vector2.end());

If you want it sorted afterwards call sort() on the vector.

Share this post


Link to post
Share on other sites
Iterators are wonderful! There is a form of the insert function that takes three iterators: The iterater before which everything is inserted, the iterator that marks the beginning of the data to be inserted, and the iterator that marks the end of the data to be inserted. And a vector has .begin() and .end() functions that return iterators for the beginning and end of the list. So if you wanted to insert vector VecB at the end of VecA, you could do:
VecA.insert(VecA.end(), VecB.begin(), VecB.end());

However, this will simply insert a copy VecB's contents into VecA. Not always a super quick process. If you want it to be a very quick process, and the trade-offs for using a linked-list (std::list) rather than a contiguous chunk of memory (std::vector) aren't a problem, then you can call std::list::splice() to very quickly move the contents of a portion (or all) of one list into some location (beginning, middle, or end) in another list.

[edit]Could I be any slower, and try to answer any more questions that weren't asked? [smile][/edit]

Share this post


Link to post
Share on other sites
Of course the speed of that insert depends on the ammount of space you have reserved for your vector (the capacity). I recommend doing a reserve first, for example:


VecA.reserve( VecA.size() + VecB.size() );
VecA.insert( VecA.end(), VecB.begin(), VecB.end() );


Of course the fewer resizes the vector has to do the better. So if you can afford to reserve extras when allocating A do it then!

Share this post


Link to post
Share on other sites
It's actually not that useful to call reserve before calling the insert() in this case. Since std::vector supplies random access iterators, the insert() operator knows how many elements will be inserted so will only expand the vector once if there is insufficient capacity.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
If you want it sorted afterwards call sort() on the vector.
Or, if performance is an issue and both input vectors are pre-sorted like the example, use a parallel traversion approach when inserting.

Share this post


Link to post
Share on other sites
AFAICT from SGI's doc you'll have to merge into a new container, but you can do what doynax said with the standard library as well:


#include <algorithm>
#include <vector>

std::vector<int> v1, v2, v3;
// put stuff into v1 and v2; leave v3 empty

std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3));

Share this post


Link to post
Share on other sites
You can do it with just the two containers, but it'd be O(n2) compared to O(n lg n) for the insert/sort (assuming the two containers are roughly equal in size).

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
You can do it with just the two containers, but it'd be O(n2) compared to O(n lg n) for the insert/sort (assuming the two containers are roughly equal in size).
I don't quite see why, isn't it just a matter of sorting backwards (or allocating the new elements at the front of the destination array)?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!