Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Copying Container Elements From The C++ Library: It's Trickier Than It Looks

May 30, 2013

Last week, I pointed out that putting a new element in a vector might reallocate the vector. As a result of this behavior, we must generally assume that adding elements to a vector will invalidate every reference, pointer, or iterator that refers to a vector element.

More Insights

White Papers

More >>

Reports

More >>

Webcasts

More >>

With this assumption in mind, let's assume that t is a Thing and that v is a vector<Thing>, and consider the function call

 
               v.push_back(t);

Obviously, this call appends a copy of t to v. What is the type of push_back's parameter?

One's first thought is apt to be that the parameter should be a Thing. However, in that case, calling v.push_back(t) would always end up copying t twice: first from t to push_back's parameter, and then from there into v. To avoid this double copying, push_back is actually defined to take a reference parameter. In other words, by definition a call to push_back does not copy the argument directly; any copying must be done explicitly within the body of push_back.

Now consider this call:

 
               v.push_back(v[0]);

We assume that v already has at least one element; otherwise, the mere act of evaluating v[0] is undefined. In this call, push_back's parameter is a reference to v[0]. Like any other reference to an element of v, this reference will become invalid if v is reallocated. This fact leads to a requirement on the implementation of push_back:

push_back must copy its parameter before it invalidates any references to elements of v.

However, in order to copy its parameter, push_back must have some place to copy it. Unless the parameter is to be copied twice, that place must be the element of v in which the copy will eventually live. But that element does not exist until v is reallocated! So we seemingly have a requirement that push_back copy its parameter after reallocating v, even though we have already seen that it must copy it before reallocating v.

Fortunately, there is a way around the seeming contradiction between these requirements: Unlike user code, library routines such as push_back can know about how vectors are implemented. For example, reallocating a vector probably has four phases:

  1. Allocate enough memory to hold the new elements of v.
  2. Move the old elements to the new memory.
  3. Destroy the old elements.
  4. Free the old memory.

Unlike user code, push_back can copy its parameter to the appropriate place in the new memory between phases 1 and 2. At that point in the code, all of v's elements are still in their original places, which means that any references to those elements are still valid. So long as push_back's parameter has been copied to its destination before phase 2 begins, there is no risk of invalidating that parameter before copying its contents.

You should be able to see from even this simple example that it is harder for the C++ library to manipulate vectors than might appear on the surface. This difficulty is yet one more reason to use the library instead of trying to reimplement it.

In fact, this discussion has carefully concealed yet another complexity, which nevertheless peeked out in a single word in phase 2 above. Notice that I said that push_back must move the old elements to the new memory, rather than copying them. This distinction is important, especially where runtime efficiency is concerned. We'll begin exploring the idea of moving data next week.

Related Reading






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