Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Why It Is Useful to Move Objects

September 07, 2011

We continue last week's discussion by showing why it is useful to know that an object is about to be recycled.

Fundamental to C++ is the idea that every type has a size that is known during compilation. By implication, a type that represents a variable-length data structure has no choice but to store the variable-length part in dynamically allocated memory, usually with a pointer that keeps track of where that memory is.

Dynamic memory takes a long time to allocate and deallocate because the compiler cannot figure out during compilation where that memory is going to be. As a result, the library has to do work that the compiler would do for variables of fixed-length types. Therefore, a statement such as

string hello = "Hello, world!";

is likely to spend most of its time in memory allocation and deallocation.

Copying an object that represents a variable-length data structure is as slow as creating one, because copying an object means creating a copy of that object. Thus, if we write

string aloha = hello;

the machine must do as much work as it did when it created hello in the first place.

Now let's think about what happens when we erase an element from a vector of strings:

vector<string> v;
 v.push_back("Hello, world!");

 // Put more elements in v here

 v.erase(v.begin());   // Erase the first element

The call to v.erase erases the first element of v, which erase does by copying the second element of v to the first, copying the third element to the second, and so on. The definition of erase says that it is permitted to change the value of the last element of v to whatever it likes; every other element of v will have the value that the succeeding element had before erase.

Think about what happens when we copy the second element of v (v[1]) to the first element (v[0]). The former value of v[0] must be destroyed, of course. After that, if we take seriously the instructions to copy, the library must allocate memory for a copy of v[1]'s contents and put a pointer to that memory in v[0]. Next, it must repeat the process with v[1] and v[2] (assuming v[2] exists): It destroys the contents of v[1], creates a copy of v[2]'s contents, and puts a pointer to that copy into v[1].

In other words, for every element of v except v[0], the library will allocate dynamic memory for a copy of that element, copy the contents of that element into the newly allocated memory, and then deallocate the memory for the original element. Figuratively speaking, the library spends most of its time digging holes and filling them up again.

In C++11, the vector library knows that it doesn't have to work this way. Instead, it can destroy v[0], move v[1] to v[0], move v[2] to v[1], and so on. It will move from the last element of v without moving to it, so that last element will have an unspecified (but valid) value; but that's OK.

This technique can save a surprising amount of time. It is not hard to write programs that run 100 times faster on an implementation that moves vector elements than it does on one that copies them. Moreover, every program that uses vectors of types, such as string, that support movement will gain. Programmers do not have to change their code to benefit from this speed improvement.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video