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

  • The first phase of API management was about realizing the business value of APIs. This next wave of API management enables the hyper-connected enterprise to drive and scale their businesses as API models become more complex and sophisticated. Today, real world product launches begin with an API program and strategy in mind. This API-first approach to development will only continue to increase, driven by an increasingly interconnected web of devices, organizations, and people. To support this rapid growth, …

  • Packaged application development teams frequently operate with limited testing environments due to time and labor constraints. By virtualizing the entire application stack, packaged application development teams can deliver business results faster, at higher quality, and with lower risk.

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds