Insert a list into a list
Author
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
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.
vector1.insert(vectorn1.end(), vector2.begin(), vector2.end());
If you want it sorted afterwards call sort() on the vector.
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:
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]
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]
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:
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!
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!
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.
Quote:Original post by SiCraneOr, if performance is an issue and both input vectors are pre-sorted like the example, use a parallel traversion approach when inserting.
If you want it sorted afterwards call sort() on the vector.
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 emptystd::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3));
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).
Quote:Original post by SiCraneI 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)?
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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
