A better vector trim with move semantics

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:

Code:

---

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

Code:

---

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.

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.

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. :confused:

Quote:

---

Originally Posted by 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. :confused:

---

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. ;)

Quote:

---

Originally Posted by 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.

---

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.

Quote:

---

Originally Posted by 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. :confused:

---

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.

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?

Quote:

---

Originally Posted by 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?

---

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:

Code:

---

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:

Code:

---

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.

Quote:

---

Originally Posted by JohnW@Wessex

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

Quote:

---

Originally Posted by superbonzo

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.

Quote:

---

Originally Posted by monarch_dodra

... 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 ! :)

Quote:

---

Originally Posted by monarch_dodra

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

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?

Quote:

---

Originally Posted by ninja9578

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.

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

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.

Quote:

---

Originally Posted by 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.

---

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

Code:

---

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

I'm all for removing implicit move... as long as it can still be explicitly defaulted.

Quote:

---

Originally Posted by monarch_dodra

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

---

I've read the article now,

http://www.codeguru.com/cpp/misc/sam...-Semantics.htm

and I have a question.

The classic swap based shrink-to-fit idiom (described in item #82 in C++ Coding Standards by Sutter & Alexandrescu) looks like this.

Code:

---

template <typename T>
void trim_vector(std::vector<T>& io_vector) {
  std::vector<T>(io_vector).swap(io_vector));
}

---

Now lets say the swap method becomes implemented to take advantage of move semantics allong these lines,

Code:

---

template <class T> swap(T& a, T& b) {
    T tmp(std::move(a));
    a = std::move(b); 
    b = std::move(tmp);
}

---

as suggested here,

http://www.artima.com/cppsource/rvalue.html

How does then the suggestion in your article compare?

In other words, if swap gets move semantics does your suggested new idiom offer any advantage compared with the old idiom? I don't know enougth about move semantics to be able to decide that myself.

Quote:

---

Originally Posted by nuzzle

I've read the article now,

http://www.codeguru.com/cpp/misc/sam...-Semantics.htm

and I have a question.

The classic swap based shrink-to-fit idiom (described in item #82 in C++ Coding Standards by Sutter & Alexandrescu) looks like this.

Code:

---

template <typename T>
void trim_vector(std::vector<T>& io_vector) {
  std::vector<T>(io_vector).swap(io_vector));
}

---

Now lets say the swap method becomes implemented to take advantage of move semantics allong these lines,

Code:

---

template <class T> swap(T& a, T& b) {
    T tmp(std::move(a));
    a = std::move(b); 
    b = std::move(tmp);
}

---

as suggested here,

http://www.artima.com/cppsource/rvalue.html

How does then the suggestion in your article compare?

In other words, if swap gets move semantics does your suggested new idiom offer any advantage compared with the old idiom? I don't know enougth about move semantics to be able to decide that myself.

---

The thing is that "the new swap with r-value semantics" is no different from "the old swap". Indeed, the old swap was specialized to basically move the vectors' internal pointers already. The only difference is that the new swap would still be efficient without the specialization.

In otherwords, the new swap changes nothing to the old idiom. So how is my new idiom different? The main difference is that the old swap made copies of the individual elements, when there was no real need. With my idiom, each of the individual elements are merely moved to their new destination, avoiding the overhead of the individual copies.

The problem with trying to solve this problem is that just plain moving the vectors doesn't solve the problem, as moving a vector merely changes the internal pointer address, but the objects themselves will always be inside an array that is over allocated.

I hope that answers your question.

Quote:

---

Originally Posted by monarch_dodra

I hope that answers your question.

---

Not quite.

I've made a small benchmark where I compare the old idiomatic approach, the new C++0x shrink_to_fit method of vector, and your new approach and there is no difference. They're equally fast.

I'm using the VS2010 compiler from Microsoft and maybe move sematics isn't implemented yet, although I believe it is.

You claim your approach is better but have you actually tested it?

Quote:

---

Originally Posted by nuzzle

Not quite.

I've made a small benchmark where I compare the old idiomatic approach, the new C++0x shrink_to_fit method of vector, and your new approach and there is no difference. They're equally fast.

I'm using the VS2010 compiler from Microsoft and maybe move sematics isn't implemented yet, although I believe it is.

You claim your approach is better but have you actually tested it?

---

I have tested it actually. Using MinGW - GCC 4.5. In release. (And I also did an assembly comparison).

During your test, where the objects inside the vector moveable? The point is that this approach is faster only if the objects are moveable. However, if the objects aren't moveable (ie vector of int), there is no extra overhead (thanks to meta).

My quick benchmarking.

I tested it with simple ints: No difference.
I tested with a simple pimple object (RAII object with pointer to int): 10x speedup.
I tested with vector of vector: speedup depending on the internal size of the stored sub-vectors
I tested with strings: Slight speed up.

I finally tested the shrink to fit method with vector of int, and inspected the resulting assembly, and it was exactly the same in both cases.

VStudio should support C++0x, but I've never found the option that actually enables it.

Quote:

---

Originally Posted by monarch_dodra

During your test, where the objects inside the vector moveable? The point is that this approach is faster only if the objects are moveable. However, if the objects aren't moveable (ie vector of int), there is no extra overhead (thanks to meta).

---

Could you please explain this a little bit further.

I've used this object in my benchmark,

Code:

---

class C {
        std::array<int,5> a;
};

---

If it's not moveable how do I make it moveable?

It's not moveable as the array for the data is defined in the std::array structure. The struct/class would have to have some internal pointer to the array to make moving it more efficient than copying.

Quote:

---

Originally Posted by nuzzle

Could you please explain this a little bit further.

I've used this object in my benchmark,

Code:

---

class C {
        std::array<int,5> a;
};

---

If it's not moveable how do I make it moveable?

---

Moveable objects are class (hereby known as "the_class") objects that implement the methods:

Code:

---

the_class::the_class(the_class&&);
the_class& the_class::operator=(the_class&&);

---

An std::array is not moveable because it does not implement these methods. It does not implement these methods because an std::array would not be efficiently moveable anyways (space is on the stack).

Moveable objects are typically objects that use some sort of pimpl internally: vectors, strings, unique_ptr... Shared pointer is also moveable.

This is a quick test I did with a simple pimpl object. I made a pimpl adaptor, and I used that inside the vector. You can compile activating/deactivating the USE_MOVE_OPERATORS macro switch. The output makes the result pretty clear at what is happening behind the scenes.:

Code:

---

#include <vector>
#include <algorithm>
#include <iostream>

#define USE_MOVE_OPERATORS

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()
    );
}

template <typename T>
class pimpl_object
{
public:
  //Default constructor
  pimpl_object() : _pimpl(new T)
  {
    std::cout << "default constructor: 1 allocation" << std::endl;
  }

  operator T& () {return *_pimpl;}
  operator const T& () const {return *_pimpl;}

  //Parameterized constructor
  template <typename... Args>
  pimpl_object(Args... args)
  : _pimpl(new T(args...))
  {
    std::cout << "parametrized constructor: 1 allocation" << std::endl;
  }

  //copy constructor
  pimpl_object(const pimpl_object& i_other) : _pimpl(0)
  {
    _pimpl = new T(*i_other._pimpl);
    std::cout << "copy constructor: 1 allocation" << std::endl;
  }

  //asignment operator
  pimpl_object& operator=(const pimpl_object& i_other)
  {
    T* old = _pimpl;
    _pimpl = new T(*i_other._pimpl);
    delete old;
    std::cout << "assignment operator: 1 allocation + 1 deletion" << std::endl;
    return *this;
  }

  //destructor
  ~pimpl_object()
  {
    std::cout << "destructor: ";
    if (_pimpl)
    {
      delete _pimpl;
      std::cout << "1 deletion";
    }
    else
    {
      std::cout << "No deletion";
    }
    std::cout << std::endl;
  }

#ifdef USE_MOVE_OPERATORS
  //move constructor
  pimpl_object(pimpl_object&& i_other) : _pimpl(i_other._pimpl)
  {
    i_other._pimpl = 0;
    std::cout << "move constructor: No allocation" << std::endl;
  }

  //move operator
  pimpl_object& operator=(pimpl_object&& i_other)
  {
    std::swap(_pimpl, i_other._pimpl);
    std::cout << "move operator: No allocation" << std::endl;
    return *this;
  }
#endif

private:
  T* _pimpl;
};

int main()
{
  typedef pimpl_object<int> object;
  std::vector<object> vect;
  vect.reserve(20);
  vect.resize(10);
  trim_vector(vect);
}

---

@monarch_dodra, just a side note on your pimpl adaptor:

first, is there any reason why you are not forwarding the arguments in the "parametrized constructor" ?:

Code:

---

//Parameterized constructor
template <typename... Args>
pimpl_object(Args&&... args)
        : _pimpl( new T( std::forward<Args>(args)... ) )
{
        ...

---

second, IMHO a swap based move assignment operator is not correct in this case; quoting Abrahams

Quote:

---

A move assignment operator “steals” the value of its argument, leaving that argument in a destructible and assignable state, and preserves any user-visible side-effects on the left-hand-side.

---

yes, most of the times the to be moved object will be destroyed right away, but in situations like

Code:

---

pimpl_object<T> a = ...;
pimpl_object<T> b = ...;

a = std::move( b );

// ...

---

you will loose control on when the resources owned by a will be actually released which seems unacceptable to me. So, a more correct solution should be releasing a's resources before swapping the pimpl pointers ( plus a check for self move-assignemnt, of course ).

Quote:

---

Originally Posted by superbonzo

@monarch_dodra, just a side note on your pimpl adaptor:

first, is there any reason why you are not forwarding the arguments in the "parametrized constructor" ?:

---

My code is wrong. I wrote it real quick to test a few things. I would not recommend to anyone to use my pimpl adaptor.

Quote:

---

Originally Posted by superbonzo

second, IMHO a swap based move assignment operator is not correct in this case; quoting Abrahams

yes, most of the times the to be moved object will be destroyed right away, but in situations like

Code:

---

pimpl_object<T> a = ...;
pimpl_object<T> b = ...;

a = std::move( b );

// ...

---

you will loose control on when the resources owned by a will be actually released which seems unacceptable to me. So, a more correct solution should be releasing a's resources before swapping the pimpl pointers

---

That is very true, and I had never considered that. I guess the vector's approach to the implementation is better:

Code:

---

my_class& operator=(my_class&& i_other)
{
  this->clear();
  this->swap(i_other);
}

---

One of the reasons I did not do this is that in my vision of a pimpl, there is a class invariant that says a pimpl cannot point to nothing.

That said, a moved object is never supposed to be touched again, except for the destructor, so as long as the destructor can handle it, it should be fine.

Quote:

---

( plus a check for self move-assignemnt, of course ).

---

Actually (apparently), you aren't required to check for self-move assignment. The standard made it explicit in 17.6.3.9, after accepting defect 1204.

Quote:

---

Originally Posted by 1204. Global permission to move

Additionally this clarifies that move assignment operators need not perform the traditional if (this != &rhs) test commonly found (and needed) in copy assignment operators.

---

Quote:

---

Originally Posted by 17.6.3.9 Function arguments

1 Each of the following [US 81] statements applies to all arguments to functions defined in the C++ standard library, unless explicitly stated otherwise.
— If an argument to a function has an invalid value (such as a value outside the domain of the function or a pointer invalid for its intended use), the behavior is undefined.
— If a function argument is described as being an array, the pointer actually passed to the function shall have a value such that all address computations and accesses to objects (that would be valid if the pointer did point to the first element of such an array) are in fact valid.
— If a function argument binds to an rvalue reference parameter, the implementation may assume that this parameter is a unique reference to this argument. [ Note: If the parameter is a generic parameter of the form T&& and an lvalue of type A is bound, the argument binds to an lvalue reference (14.8.2.1) and thus is not covered by the previous sentence. —end note ] [ Note: If a program casts an lvalue to an rvalue while passing that lvalue to a library function (e.g. by calling the function with the argument move(x)), the program is effectively asking that function to treat that lvalue as a temporary. The implementation is free to optimize away aliasing checks which might be needed if the argument was an lvalue. —end note ]

---

The current implementation of move-assign in GCC (see above) leave the current object in an "empty" state after a move assign (this->clear), but don't create un-define behavior, in the sense that the current object is still destroyable.

Quote:

---

Originally Posted by monarch_dodra

One of the reasons I did not do this is that in my vision of a pimpl, there is a class invariant that says a pimpl cannot point to nothing.

That said, a moved object is never supposed to be touched again, except for the destructor, so as long as the destructor can handle it, it should be fine.

---

... and assignment. Actually, this implies that every movable class should support a sort of "empty" state ...

Quote:

---

Originally Posted by monarch_dodra

Actually (apparently), you aren't required to check for self-move assignment. The standard made it explicit in 17.6.3.9, after accepting defect 1204.

---

good to know, thank you ! :)

Turns out, according to 23.4.1.2, that in C++0X, vectors come with a member function called "shrink_to_fit", making this whole ordeal moot. :lol:

To anyone still reading this...