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

Introduction

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);
  io_vector.swap(tmp_copy);
}

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(
    std::make_move_iterator(io_vector.begin()),
    std::make_move_iterator(io_vector.end())
  )

  io_vector.swap(io_vector);
}

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 =       
    std::vector<T>(
      std::make_move_iterator(io_vector.begin()),
      std::make_move_iterator(io_vector.end()),
      io_vector.get_allocator()
    );
}
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.

Conclusion

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.



Comments

  • 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.

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

Top White Papers and Webcasts

  • Today's agile organizations pose operations teams with a tremendous challenge: to deploy new releases to production immediately after development and testing is completed. To ensure that applications are deployed successfully, an automatic and transparent process is required. We refer to this process as Zero Touch Deployment™. This white paper reviews two approaches to Zero Touch Deployment--a script-based solution and a release automation platform. The article discusses how each can solve the key …

  • On-demand Event Event Date: December 18, 2014 The Internet of Things (IoT) incorporates physical devices into business processes using predictive analytics. While it relies heavily on existing Internet technologies, it differs by including physical devices, specialized protocols, physical analytics, and a unique partner network. To capture the real business value of IoT, the industry must move beyond customized projects to general patterns and platforms. Check out this webcast and join industry experts as …

Most Popular Programming Stories

More for Developers

RSS Feeds