Move constructor for a map

Question

I think I do understand "the basic IDEA" of move semantics, but now when I'm on the stage of implementing my own map I stopped and started to think about it when I was going to write a use case and walk through for move ctor of map. Correct me if I'm wrong but what I do understand how the whole business of move semantics works is that they suppose to help in avoiding unnecessary copying? Right? Now, take a map for example and just for the purpouse of this example assume that my map is modeled as:

class Map
{
Link* impl_;//THIS IS A POINTER TO A LINK WHICH HAS A parent, left and right (of Link type)
Map(Map&& tmp);//move ctor
//unnecessary code ommited
};

And here is the snag: When I'm trying to think of move ctor for my map I cannot see a way of avoiding allocating a new space for all those links which needs to be created and then their pointers swapped with those from a tmp Map object (passed as a arg to my move ctor).
So I do have to allocate space anyway, or don't I?

Answer 1

All you have to do is reassign the Link pointer, since all the other Link pointers are attached to it, they will now be part of the new Map.

Map(Map&& tmp) :impl_(tmp.impl_) { tmp.impl_ = nullptr; }

This is assuming no other data members.

Answer 2

Aside from the standard disclaimer not to reinvent existing containers, wouldn't it be sufficient to simply assign the root node pointer without doing any allocation?

Answer 3

You need five operations total: the classic "big three" (copy constructor, copy assignment operator, destructor) and the two new move operations (move constructor, move assignment operator):

// destructor
~Map();

// copy constructor
Map(const Map& that);

// move constructor
Map(Map&& that)
{
    impl_ = that.impl_;
    that.impl_ = 0;
}

// copy assignment operator
Map& operator=(const Map& that);

// move assignment operator
Map& operator=(Map&& that)
{
    using std::swap;
    swap(impl_, that.impl_);
    return *this;
}

The basic idea behind the move assignment operator is that swap(map1, map2) has the same observable side effect as map1 = map2 if you don't inspect map2 again after performing the swap. Recall that an rvalue is either a prvalue or an xvalue. By definition, a client cannot inspect an object designated by a prvalue twice, because evaluating a prvalue always leads to the creation of a new object. The only way to observe this trick is to move from an xvalue such as std::move(map_variable), but then it is obvious that map_variable is potentially modified.

If you want exception safe assignment even when copying, you can combine both the copy assignment operator (taking const Map&) and the move assignment operator (taking Map&&) to a generalized assignment operator (taking Map). Then you only need four operations total:

// exception safe copy/move assignment operator
Map& operator=(Map that)
{
    using std::swap;
    swap(impl_, that.impl_);
    return *this;
}

Note that this variant of the assignment operator takes its argument by value. If the argument is an lvalue, the copy constructor initializes that, and if the argument is an rvalue, the move constructor does the job. (Also note that specializing std::swap is unlikely to result in further significant performance gains if you already provide the move operations.)

Answer 4

There is an excellent walkthrough of move semantics from @FredOverflow here.

Answer 5

It is possible to implement move semantics with old C++ (not 0x) but it has to be done explicitly and is more tricky.

class X
{
// set access specifiers as required
   struct data
   {
      // all the members go here, just plain easy-to-copy members
   } m;

   data move()
   {
      data copy(m);
      m.reset(); // sets everything back to null state
      return m;
   }

   explicit X( const data& d ) : m(d)
   {
   }
  // other members including constructors
};

X::data func() // creates and returns an X
{
  X x; // construct whatever with what you want in it
  return x.move();
}

int main()
{
   X x(func());
   // do stuff with x
}

And X can be made non-copyable and non-assignable in the above, data can have items created on the heap and it is the destructor of X that is responsible for the cleanup. When data is reset by the move() function the parting X will have nothing to clean up because the ownership has been transferred.

Generally the data struct should be public within X but all its members should be private with X a friend. Users therefore do not therefore access anything in there directly.

Note that you are likely to "leak" if you call move() on X without attaching it to another X, thus if you call just func() above you would leak. You should also beware if the constructor of X from data throws (its destructor won't be called so no cleanup will happen automatically). If the copy-constructor of data itself throws you are in even more trouble. Generally none of these should happen as data contains light stuff (pointers and numbers) and not heavy objects.