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

  • Employees must exchange sensitive emails with customers and partners. These emails might contain protected health information, protected financial information, or corporate information that should not be made public. Globalscape® Mail Express® allows you to encrypt the emails that it manages so that no one but the sender and recipient--not even the administrator--can view the contents of the email. "Secure the Transfer of Sensitive Emails" is the property of GlobalSCAPE

  • IBM Worklight is a mobile application development platform that lets you extend your business to mobile devices. It is designed to provide an open, comprehensive platform to build, run and manage HTML5, hybrid and native mobile apps.

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date