C++ Programming: A Better Vector Trim Algorithm With Move Semantics


Vectors are one of the single most useful and most used objects in the STL. They are easy to use, and remove the burden of memory management from the user. It is possible to partially control memory usage by using functions like reserve, but nothing is provided to free up excess memory. Users have come up with ways to trim a vector by hand, but with the advent of the new C++0x and its move semantics, the classic solution of copy-swaping has become excessively expensive. This article seeks to find a better solution.

The Classic Solution To trimming Vectors

The classic solution to trimming a vector consists in copy constructing a new vector. Your library implementation will create a copy, using minimal memory. You will have two vector with exactly the same, but different capacity. By swaping the contents of both vectors, you end up with the same vector you started with, but less capacity. The trim function is usually implemented like this:
template <typename T>
void trim_vector(std::vector<T>& io_vector)
  std::vector<T> tmp_copy(io_vector);

The Cost of Trimming A Vector

Trimming a vector is not cheap, as a copy constructor is involved. You will need to copy each and every element of your vector into the new one. While this is usually acceptable, with the advent of C++0x's move semantics, this way of doing things might seem excessively expensive. After all, why pay for a copy, when all you need is a move?

The C++0x Solution

The difficulty with finding a solutin is that the trimming of the vector relies on the creation of a brand new copy. Simply moving the vector would short-circuit the copy, and you would end up with a function that does nothing. We need to construct a copy of our vector from a move of the individual elements themselves

Thankfully for us, vector provides the tools to construct a copy from a range, and since that constructor is templated, the move_iterator adaptor will make sure our new vector will move the elements, instead of copying them.

template <typename T>
void trim_vector(std::vector<T>& io_vector)
  std::vector<T> tmp_copy(


This code achieves the desired effect: It trims your vector, using move semantics. It is several magnitudes faster for move-able objects than a classic trim. As for non-move-able objects, this code will execute exactly the same as the old one. Worst case scenario, it is just as fast.

Beneficial Side Effects

An un-expected but beneficial side effect to this new trim is that it now allows the trimming of vectors whose objects are not copy constructable. For example, if you have ventured into the realm of vector-of-unique_ptr, you'll be glad to know you can now trim those too.

Final Code

I purposefully kept the previous code explicit for better understanding, and omitted anything not directly related to the issue at hand. If you would like to copy the final code into your library, this is the one I would recommend:
template <typename T>
void trim_vector(std::vector<T>& io_vector)
  if(io_vector.size() == io_vector.capacity()) {return;}

  io_vector =       
This starts with a quick short-circuit test. It ditches the name of the temporary, as well as switches out the swap for a move. The move is disguised as an operator=, but since the right hand side is an R-value, it will trigger a move. Finally, allocators are put into the picture, just in case you one day want to trim a vector with a stateful allocator.


This little optimization probably won't change the way you code, but I hope it might find its way into your own personal library of helper functions. This kind of optimization can be applied to thousands of little helper functions. The speed up isn't huge, but it does stack up. Finally, the use of move semantics here is purely an implementation details. You can make the change, and obtain the same result without breaking any code, faster. It will be completely transparent for your users.


  • bug in first move_iterator trim_vector?

    Posted by jwbarton on 01/20/2011 01:35pm

    shouldn't the first example with move_iterator use: io_vector.swap(tmp_copy);

    • Correct

      Posted by monarch_dodra on 01/21/2011 03:26am

      Yes, that is a typo. Thanks, sorry about that. I'll try to fix it.

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • "Security" is the number one issue holding business leaders back from the cloud. But does the reality match the perception? Keeping data close to home, on premises, makes business and IT leaders feel inherently more secure. But the truth is, cloud solutions can offer companies real, tangible security advantages. Before you assume that on-site is the only way to keep data safe, it's worth taking a comprehensive approach to evaluating risks. Doing so can lead to big benefits.

  • Savvy enterprises are discovering that the cloud holds the power to transform IT processes and support business objectives. IT departments can use the cloud to redefine the continuum of development and operations—a process that is becoming known as DevOps. Download the Executive Brief DevOps: Why IT Operations Managers Should Care About the Cloud—prepared by Frost & Sullivan and sponsored by IBM—to learn how IBM SmartCloud Application services provide a robust platform that streamlines …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds