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

  • On-demand Event Event Date: September 10, 2014 Modern mobile applications connect systems-of-engagement (mobile apps) with systems-of-record (traditional IT) to deliver new and innovative business value. But the lifecycle for development of mobile apps is also new and different. Emerging trends in mobile development call for faster delivery of incremental features, coupled with feedback from the users of the app "in the wild." This loop of continuous delivery and continuous feedback is how the best mobile …

  • Is your IT Automation strategy saving you money or just becoming more complex and costly? With the right unified strategy, IT Automation can pay for itself and deliver far more business value. Watch this on-demand webinar, "New Strategies to Manage IT Automation Complexity" and learn how to: Reduce costs by integrating automation for servers, middleware, networks and databases Eliminate manual and tedious IT Operations tasks with both new and existing technology Save time and money by consolidating …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds