A better vector trim with move semantics

[monarch_dodra]

I love having trimmed vectors. If there is one thing that makes me feel more smug than using reserve before inserting, its trimming when I can't know in advance how much to reserve. I've always had this useful function in my personal library:

template <typename T>
void trim_vector(std::vector<T>& io_vector)
{
  if(io_vector.size() == io_vector.capacity())
    {return;}

  std::vector<T>(io_vector).swap(io_vector);
}

If you are not familiar with vector trimming, then you can look here, or read yourself some Scott Meyers Effective STL. Basically, It copy constructs a brand new vector of the right size, and then swaps the contents.

I've been playing around with move recently, and while I've always considered trim to be expensive, it now looks to me to be excessively expensive. Why make a copy of each element, when you could be moving them?

The problem is that the solution is not trivial: Simply moving the vector will not have the desired effect, as the new vector will just be the old vector. You want to move all the elements of the old vector into the new one, without touching the allocated space in which the elements are.

So I rewrote my vector_trim. The trick is to use the iterator constructor, as well as some move_iterator magic:
EDIT: More optimization

template <typename T>
void trim_vector(std::vector<T>& io_vector)
{
  if(io_vector.size() == io_vector.capacity())
    {return;}

  io_vector = //Since the temporary vector is an R-value, this will call operator(std::vector&&), ie, a move
    std::vector<T>(
      std::make_move_iterator(io_vector.begin()),
      std::make_move_iterator(io_vector.end()),
      io_vector.get_allocator()
    );
}

This code has strictly no overhead compared to the old one in regards to non-move-able objects, but is magnitudes faster for move-able objects.

A very interesting side effect is that it allows the trimming of vectors whose objects are not copy constructable (think vector<unique_ptr>), which was not the case with the old code.

There, I hope whoever reads this will find it useful.

[kempofighter]

Something like this would be better as an article submission or frequently asked STL question. If you can figure out how to do that, then it won't get buried so deeply within the general C++ forums.

[kempofighter]

Wait - what is a make_move_iterator? I don't see that in my copy of the ISO/IEC 14882:2003(E) C++ standard. Is this something that is added to the latest standard? Please clarify.

[Chris_F]

Wait - what is a make_move_iterator? I don't see that in my copy of the ISO/IEC 14882:2003(E) C++ standard. Is this something that is added to the latest standard? Please clarify.

It's available in MSVC 2010. Pretty sure since it pertains to moving and Rvalue references, that this is a C++0x addition. You should consider updating your compiler.

[monarch_dodra]

Something like this would be better as an article submission or frequently asked STL question. If you can figure out how to do that, then it won't get buried so deeply within the general C++ forums.

Yeah, that's what I thought, but I didn't feel like writing an actual article. I thought I'll just start a thread, and if a few people see it, that's already pretty good. Plus, its cheap pear review in case I wrote something wrong Thanks for your feed back, I may try to write an actual article then.

Wait - what is a make_move_iterator? I don't see that in my copy of the ISO/IEC 14882:2003(E) C++ standard. Is this something that is added to the latest standard? Please clarify.

Yeah, it pertains to the new R-value references and move semantics in the upcoming C++0x standard. The can get the latest draft here:
http://www.open-std.org/jtc1/sc22/wg...2010/n3126.pdf
As always, the standard isn't the best place to learn though...

A (very) quick intro is available at wikipedia, or you can read this article. They are hard to wrap your head around at first, but once you understand, they are an incredibly powerful (and fun) tool to use.

[JohnW@Wessex]

I've not really delved into R-Value references much yet (no supporting compiler available to me) but could 'move' be used instead of 'swap'? I don't know whether std::move would be optimal for vector. Does the new vector API have a 'move' member?

[monarch_dodra]

I've not really delved into R-Value references much yet (no supporting compiler available to me) but could 'move' be used instead of 'swap'? I don't know whether std::move would be optimal for vector. Does the new vector API have a 'move' member?

You are correct. I changed the code to reflect this. vector move is implemented by a swap, but that is an implementation detail. The vector API does not have an actual move member because that's not really the way R-values references are meant to be used. It does though have:

std::vector(std::vector&& i_other);
std::vector& operator=(std::vector&& i_other);

To move an object into another, you just need to make sure the passed object is an r-value reference. From there, the type of the object and the function overloads will do the rest. The standard does provide "T&& move<T>(T& object)". It takes an object, and changes it into an r-value reference.

Little example:

template <typename T>
void move vector(std::vector<T>& origin, std::vector<T>& destination)
{
   destination = std::move(origin);
}

Here, origin is turned into an r-value reference, and the move overload of operator= is resolved, effectively moving origin into destination. After the operation, the state of origin is unknown, but is guaranteed destructible.

I went ahead and wrote an article. I link it back here when it gets posted.

[superbonzo]

I've not really delved into R-Value references much yet (no supporting compiler available to me) ...

I'm also cautious on using the new move semantics, at least until the new standard gets in a sufficiently "stable" state...

just consider that the draft linked to by monarch_dodra still admits the compiler implicitly generated move ctor/assignment, whilst at the same time guys like Dave Abrahams are strongly advocating their removal from the final standard document ( although, as far as I know, VS2010 already does not provide them ) ...

[monarch_dodra]

I'm also cautious on using the new move semantics, at least until the new standard gets in a sufficiently "stable" state...

just consider that the draft linked to by monarch_dodra still admits the compiler implicitly generated move ctor/assignment, whilst at the same time guys like Dave Abrahams are strongly advocating their removal from the final standard document ( although, as far as I know, VS2010 already does not provide them ) ...

I agree that the draft still isn't final, but it won't undergo massive changes either. While I haven't fully moved to C++0x either for several reasons, I also think it is important to learn about C++0x and see if it is even worth it.

Plus, I find the move semantics to be incredibly fun.

[superbonzo]

... I also think it is important to learn about C++0x and see if it is even worth it. Plus, I find the move semantics to be incredibly fun.

I totally agree !

... but it won't undergo massive changes either.

this is more debatable; for example, if the implictly generated move ctors will be accepted in the final document then existing code relying on certain class invariants would break ( silently resulting in UB in some cases ) ... conversely, if they are dropped code relying on them would not compile anymore or would behave differently performance-wise ...

[ninja9578]

Very nice, having trimmed vectors was the sole reason for me to write my own vector class. I added a shrink() method to mine, but it would be nice to use std::vector and be able to keep it trim.

Correct me if I'm wrong though, but not all objects are movable correct?

[Lindley]

Correct me if I'm wrong though, but not all objects are movable correct?

Objects may be described as explicitly non-movable in the same way they may be described as explicitly non-copyable, but such objects have no business being in a vector anyway.

Other objects may not have explicit move semantics, but will simply default to normal copy semantics when you attempt to move them. This shouldn't be a problem if the copy operation is sane.

[monarch_dodra]

It is not the objects in and out of themselves that are movable. It is the presence (or abscence) of functions that take r-value references to those types that makes them movable, or not.

In the same way you make an object non-copyable by not implementing the copy constructor (and copy assign operator), you can make an object copyable by implementing a move constructor (and move assign operator).

[Lindley]

I would personally expect attempt to move an object without explicit move semantics to simply copy it. That is what makes sense in my mind.

[superbonzo]

I would personally expect attempt to move an object without explicit move semantics to simply copy it. That is what makes sense in my mind.

but this is not what the current draft is saying, amd this is a big problem for legacy code; consider the following code snippet by Scott Meyers

#include <iostream>
#include <vector>
struct X
{
    // invariant: v.size() == 5
    X() : v(5) {}

    ~X()
    {
        std::cout << v[0] << std::endl;
    }

 private:
    std::vector<int> v;
};

int main()
{
    std::vector<X> y;
    y.push_back(X()); // X() rvalue: copied in C++03, moved in C++0x
}

the push_back in main will give UB in C++0x. Here is the article by Dave Abrahams where he concludes that implicit move semantics should be removed by the next draft.