stlab.adobe.com Adobe Systems Incorporated

Move Library
[Utility]

The move library is a collection of utilities for creating and using types that leverage return value optimization (RVO) to avoid unnecessary copies. More...

Classes

class  back_move_iterator< C >
 Similar to std::back_insert_iterator but with move semantics, for movable types, otherwise with copy semantics. More...
struct  copy_sink< T, U, R >
 copy_sink and move_sink are used to select between overloaded operations according to whether type T is movable and convertible to type U. More...
struct  is_movable< T >
 The is_movable trait can be used to identify movable types. More...
struct  move_from< T >
 move_from is used for move_ctors. More...
struct  move_sink< T, U, R >
 move_sink and copy_sink are used to select between overloaded operations according to whether type T is movable and convertible to type U. More...

Functions

template<typename C >
back_move_iterator< C > back_mover (C &x)
template<typename I , typename O >
move (I f, I l, O result)
template<typename T >
T & move (T &x, typename copy_sink< T >::type=0)
template<typename I , typename O >
move (I &in, O out)
template<typename T >
move (T &x, typename move_sink< T >::type=0)
template<typename I , typename O >
move_backward (I &in, O out)
template<typename I , typename O >
move_backward (I f, I l, O result)

Detailed Description

Tutorial

User defined types often have remote parts either because they are implemented using a pointer-to-implementation or are variable sized. Such objects can be expensive to copy and are often copied unnecessarily when they are returned from functions or stored in other objects or containers. The Move Library is a collection of utilities to implement types which can be moved to elide copying in such situations as well as utilities to assist in moving value.

Implementing a Movable Type

A movable type models Movable. There are three components of a movable type:

  • Satisfy the requirements of concept Regular.
  • Implement a move-ctor using move_from<>.
  • Modify the assignment operator to take the operand by value and consume it.

A typical implementation of the move-ctor will simply extract the remote part, leaving the source in a destructible state.

The assignment operator takes the operand parameter by value. Typically the simplest way to destory the local remote part and consume the remote part of the operand is to swap contents with the operand. This is similar to the copy-ctor and swap idiom for implementing assignment.

Listing 1 shows an example movable class that implements a typical pointer-to-implementation (PiPl) idiom and shows that it can be used as any regular type.

#include <iostream>
#include <algorithm>

#include <boost/operators.hpp>

#include <adobe/move.hpp>

using std::swap;

struct implementation : boost::equality_comparable<implementation>
{
    explicit implementation(int x = 0) : member(x) { }
    
    implementation(const implementation& x) : member(x.member)
    { std::cout << "copy remote part: " << member << std::endl; }
    
    implementation& operator=(const implementation& x)
    {
        member = x.member;
        std::cout << "assign remote part: " << member << std::endl;
        return *this;
    }
    
    friend bool operator==(const implementation& x, const implementation& y)
    { return x.member == y.member; }
    
    int member;
};

class movable : public boost::equality_comparable<movable>
{
 public:
// model concept Regular

    explicit movable(int x = 0) : member(new implementation(x)) { }
    ~movable() { delete member; }
    movable(const movable& x) : member(new implementation(*x.member)) { }
    // operator=() implemented below
    
    friend bool operator==(const movable& x, const movable &y)
    { return *x.member == *y.member; }
    
    friend void swap(movable& x, movable& y)
    { swap(x.member, y.member); }
    
// model concept Movable
    
    // move-ctor assumes ownership of remote part
    movable(adobe::move_from<movable> x) : member(x.source.member)
    { x.source.member = 0; }
    
    // operator=() on a movable type takes parameter by value and consumes it
    movable& operator=(movable x)
    { swap(*this, x); return *this; }
    
 private:
    implementation* member;
};

int main()
{
    movable x(10);
    movable y = x;

    return 0;
}
Listing 1
copy remote part: 10
Output of Listing 1
Returning a Movable Type

We can return a movable type from a function by value and unnessary copies will be avoided as Listing 2 illustrates:

//...
movable f(int x, int y)
{ return movable(x * y); }

int main()
{
    movable x = f(10, 5);
    movable y;
    y = f(4, 3);

    return 0;
}
Listing 2

Ouput of Listing 2

In this example it is not necessary to make any copies. The result of f() is constructed directly in place for x through a compiler optimization known as return value optimization or RVO. In the case of assigning to y, the same optimization allows the compiler to construct the operand for assignment as the result of f() which is them moved into y.

Implementing a Sink Function

A sink is any function that copies it's argument, usually for the purpose of storing it. A sink is often a constructor or an insert function on a container. The operator=() on a movable type is a form of a sink function. To implement a sink function pass the argument by value and then use adobe::move() to move the argument into place. Note that this technique cannot be used to implement operator=() on because it relies on assignment. Listing 3 implements an example sink function.

//...

struct sink
{
    explicit sink(movable x) : member(adobe::move(x)) { }
    
    movable member;
};

int main()
{
    movable x = f(10, 5);
    sink y(x);          // must copy.
    sink z(f(20, 2));   // no copy.

    return 0;
}
Listing 3
copy remote part: 50
Output of Listing 3

Here again unnessary copies are eliminated. Although adobe::move() can be used anytime to force the move of an object, it should only be used as part of an explicit sink function otherwise it hinders the understanding of code.

Utilities

There are many utilities as part of the move library which can be used to move elements instead of copying them. These are useful when building containers or dealing with sink operations which must manage a collection of movable objects. Generally these operations parallel the associated copying algorithms from STL. Examples:

MoveCopyComment
adobe::move()std::copyNot to be confused with the single argument adobe::move()
adobe::move_backward()std::copy_backward
adobe::back_move_iterator()std::back_insert_iterator
adobe::back_mover()std::back_inserter
adobe::move_construct()std::construct
adobe::uninitialized_move()std::uninitialized_copy
Advanced Topics

The adobe::move() function is a NOP if the argument is not movable, however, when a non-movable item is passed to a sink this may still result in an unnecessary copy - one to the sink and one to copy the argument of the sink into place. To avoid the additional copy, two forms of a sink function can be provided, one for movable types and one for copyable types. The adobe::move_sink<> and adobe::copy_sink<> tags can be used to select between the two functions. See the implementation of adobe::move_construct() as an example.

If a sink function is a member of a template class, the same issue with regard to unnecessary copies can occur. In this case, it is desirable to distinguish between the a copy and move sink as above but also to allow implicit conversions to the type stored in the container. To allow this use the two argument form of adobe::move_sink<> and adobe::copy_sink<>. See the implementation of adobe::vector::push_back() as an example.

Theory of Operation

to be written

Acknowledgments:
The move library was inspired by the move library written by Dave Abrahams and the work on move done by Dave Abrahams and Howard Hinnant.

Function Documentation

back_move_iterator<C> adobe::back_mover ( C &  x )

Similar to std::back_inserter but with move semantics, for movable types, otherwise with copy semantics.

Definition at line 481 of file move.hpp.

O adobe::move ( f,
l,
result 
)

Iterator pair version of move. Similar to std::copy but with move semantics, for movable types, otherwise with copy semantics.

Definition at line 396 of file move.hpp.

T& adobe::move ( T &  x,
typename copy_sink< T >::type  = 0 
)

This version of move is selected when T is not movable . The net result will be that x gets copied.

Definition at line 385 of file move.hpp.

O adobe::move ( I &  in,
out 
)

ConvertibleToRange version of move. Similar to copy but with move semantics, for movable types, otherwise with copy semantics.

Definition at line 414 of file move.hpp.

T adobe::move ( T &  x,
typename move_sink< T >::type  = 0 
)

This version of move is selected when T is_movable . It in turn calls the move constructor. This call, with the help of the return value optimization, will cause x to be moved instead of copied to its destination. See adobe/test/move/main.cpp for examples.

Definition at line 375 of file move.hpp.

O adobe::move_backward ( I &  in,
out 
)

ConvertibleToRange version of move_backwards. Similar to std::copy_backwards but with move semantics, for movable types, otherwise with copy semantics.

Definition at line 443 of file move.hpp.

O adobe::move_backward ( f,
l,
result 
)

Iterator pair version of move_backwards. Similar to std::copy_backwards but with move semantics, for movable types, otherwise with copy semantics.

Definition at line 425 of file move.hpp.

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google