Q:

Move constructor for a map

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? 

A:

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.

A:

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

