Today I Learned: Range Insertions Are Better

Happy fourth-of-July, my American brethren. Sorry Canada, I went home for the weekend!

During my flight home, I started musing some of my unread C++ ebook collection and decided to start with Effective STL by Scott Meyers, the same author as the awesome Effective C++ book I reviewed. One of the first Items covered is how range member functions are better than single elements! I find this extremely intriguing. I never heard of this and I sure wasn’t taught this amazingly simple and clearly superior concept in school.

So I’ll run with the book’s example.

Say you have two vectors (for those not familiar with C++, vectors are essentially dynamic size arrays of awesome) and you want to make vector 1 (v1) the end half of vector 2 (v2).

Now while I was primarily brought up with Java (-.-) where these kinds of minute concepts are not the same, it seems like something that could be very important to at least mention that simply doing a for loop or some regular iteration to solve this problem is not only messier, but inefficient to boot.

typedef vector<Foo>::iterator FooIt;
FooIt it = v2.begin() + v2.size() / 2;
for( ; it != v2.end(); ++it)

That is messy. Even if we were dealing with a primitive array here, for loop iterations like that are just messy. Now, in Java you can just use the copyOfRange from the Utils. From what I’ve been told though at school and from what I’ve read, there is pretty much no difference between a regular for loop and copyOfRange.

In other languages, like C++, this isn’t true. My mind is blown. Its actually cleaner, but more importantly, faster to do it with something like copyOfRange.

v1.assign(v2.begin() + v2.size() /2, v2.end());

Easy. Clean. And apparently faster. Why?
Besides additional function calls in our for loop with the regular iteration which could be inlined, moving elements around the vector in C++ is more costly with the regular for loop. You’re shifting elements differently. The result is the same, but the way elements shift on each insert is different. The range insertion puts elements directly into their final positions with no shifting of elements or even any additional allocation of memory. The for loop would require the vector to constantly increase size with each new element added (n times) doubling the memory needed. The assign does it once (1), all at once, saving what could be a huge amount of performance depending on what kind of element <Foo> is.

Now it seems obvious to me! I already kind of knew about the inserting elements and memory allocation for vectors each time, but I had no idea something like assign pumps it in one shot with ranged functions. And this applies to strings too! I was under the belief that something like a vector construction, assign, insert, and even erase were exactly the same whether you did it with a for loop or with these ranged overloads. They just looked prettier I thought. I’m shocked that they actually function differently here! And apparently, this concept even dips into Python too  (as well as other languages I’m sure) because of the way it (used) to handle xrange and range. Now I believe xrange is range in the latest Python versions, which enforces what the book talked about here with how it handles the memory.

Leave a Reply

Your email address will not be published. Required fields are marked *