Custom Containers in C++11

C++11 has brought us a few significant language and library improvements which can make for greatly increased API ease of use and performance. Several of these features have a huge impact on how we write custom containers. Since I haven't seen any in-depth articles on this topic, and honestly haven't seen any truly in-depth articles on writing custom containers even for older versions of C++, I decided it was time to share some of my recent experience working on a custom high-performance, C++11-friendly container library for my current game project. Be warned: this is a particularly long article and delves into a fair bit of C++ magic.

Introduction

By far the most important new feature of C++11 for container writers is rvalue references. This feature allows containers to efficiently move around objects that might otherwise be very expensive to copy. It's also mandatory for supporting smart pointer classes like std::unique_ptr<>, and containers need to be made aware of rvalue references to be able to hold copies of those smart pointer types. While on the topic of avoiding copies, there's a few template tricks that very few people seem to be directly aware of that are important for making efficient containers. The primary trick I'm going to cover is making sure that objects passed in to methods like find() do not require the creation of unnecessary temporaries or copies.

Simple Container

Let's go ahead and start things out with a container skeleton that we have all probably written at some point. I'm going to ignore the actual data structure of the container, as that's honestly not too important for this discussion; it could be a vector, a hash table, a tree, or whatever is needed. For now, I'll use set operations for the examples.

class MyContainer
{
public:
  // constructors
  MyContainer();
  MyContainer(const MyContainer& source);
  ~MyContainer();

  // assignment operator
  MyContainer& operator=(const MyContainer& source);

  // basic set operations
  void insert(const Type& element);
  void remove(const Type& element);
  bool has(const Type& element);
};

Pretty basic, and gets the job done. Even in the C++98 era, however, there are a couple problems with this implementation. I'm going to cover those now, since the above is how almost all examples on custom containers start and end. The problem is that the operations like remove() and has() may create unnecessary temporaries for their parameters if a conversion is required. Take the following code example:

void do_stuff(MyContainer& string_set)
{
   if (string_set.has("foobar"))
   {
     // ...
   }
}

What's the problem? The problem is that the has() method I created on MyContainer takes a const reference to a std::string, but in the code snippet I passed a string literal (a const char[]) to the has() method. This means that the C++ compiler must construct a temporary std::string, which entails a memory allocation, copy, and eventual deallocation, all just to pass that string in to compare with the std::string contents. Since std::string can be compared with a regular string literal just fine, this copy is unnecessary.

Avoiding Conversions with Templated Methods

The solution is fairly simple, if a little non-obvious. I'm going to declare the has() method as a templated method. That is, the method has its own template parameter, in addition to the template parameters of the container class itself. While I'm at it, I'm also going to do this for remove() since it has a similar problem. I'll handle insert()'s performance issue later when I discuss rvalue references.

class MyContainer
{
public:
  // constructors
  MyContainer();
  MyContainer(const MyContainer& source);
  ~MyContainer();

  // assignment operator
  MyContainer& operator=(const MyContainer& source);

  // basic set operations
  void insert(const Type& element);

  template 
  void remove(const ParamType& element);

  template 
  bool has(const ParamType& element);
};

That's all it takes! Now the object given as a parameter to has() or remove() will be used without any additional conversion operators. Assuming that the parameter can actually be compared with the type stored in the container, this will work perfectly.

Avoiding Conversions with Good API Design

Note that there is still room for problems. In particular, if the type passed in and the type stored in the container required an expensive conversion for the comparison operators, this version will actually be worse, not better, because the conversion will be performed once for each comparison! This is exactly the behavior found with std::find(), so it's something to be aware of in general anyway. There are two easy rules to follow to avoid this problem. First, only define the cheapest possible comparison operators. Comparisons between two std::string's or two int's have simple, obvious, maximally efficient implementations. A comparison operator between std::string and int, however, does not. It either requires converting the string to an integer or the integer to a string, and then calling one of the original same-type comparison operators. Comparison operators between two very similar types with no conversion overhead makes sense (like the built-in comparison operator support for int vs short), but avoid anything else. The second rule is to avoid conversion constructors and conversion operators as much as possible; and when not possible, using the explicit keyword when declaring the conversions. There is absolutely no implicit conversion operator or constructor for turning a float into a std::string, for example, nor for turning a std::vector into a std::list. If it is ever necessary for such a conversion, the programmer can do so manually using library calls, but the language will never do sneaky and expensive things behind the programmer's back. As a side note, the STL and C++ in general does break the rule above in a few places. For instance, C-style strings are implicitly convertible to std::string, which is not particularly nice. In fact, the original problematic example I listed above would have been a lot more obvious if C++ did not allow for this automatic conversion. In games, we frequently write our own string libraries as well as container libraries, so I heartily recommend that any and all custom string classes where explicit conversion from string literals and C-style strings into C++ string classes if any memory allocation or copies are required. All that said, it may seem that I'm being a contradictory, and the fact that STL implementations don't use the performance advice above may seem a bit damning. After all, if the library has a minimal set of cheap comparison operators and conversions, the example above would never have even compiled, much less implicitly inserted inefficient code. The problem comes up from those few instances where one does have comparison operators between different types. For instance, my string library has several types of string classes, with different use cases and performance characteristics. One type of string is for string pooling, and creating an instance of that type requires inserting the string into the string pool. Another type is intended for large or one-off strings that need to stick around for a while, and is basically just a reimplementation of std::string (without all the silliness found in most STL implementations). Yet another type is the string range, which is an efficient and safe way to pass around temporary string data without unnecessary, including slices of other strings. It is equally cheap and efficient to compare all these different string types, just like it's equally cheap and efficient to compare as std::string to a char* as it is to another std::string. Therefor it's quite reasonable even under these rules to have a container of one string type and using methods like has() or find() or remove() with a different string type as a parameter, where a conversion would be required without the above trick. Furthermore, moving into rvalue reference territory, and the concept of "perfect forwarding" (which is one of the many great features that rvalue references unlock), it's important for my container that I pass in parameters to the underlying comparison operators with no imposed conversions or other shenanigans.

Explicit Constructors

There's one example I'd like to go over, as it seems to be poorly understood. Here are three difference ways of creating an initializing an object:

MyType foo1(initial_value);

MyType foo2 = initial_value;

MyType foo3;
foo3 = initial_value;

Novice C++ programmers may not be aware that there's any difference at all between the three, but even experienced C++ programmers may be unaware of some of the differences. Particularly, the first two have some non-obvious behavior. The example with foo1 will allocated storage on the stack and then invoke the the appropriate constructor. The example involving foo3 will allocate storage on the stack, invoke the default constructor, and then invoke the appropriate assignment operator. The example with foo2 is the most tricky. In the case of foo2, there is no invocation of the assignment operator. When a variable is declared and assignment to in the same statement, the copy/conversion constructor is invoked rather than the default constructor. However, unlike the example with foo1, the explicit constructors will not be invoked! This is particularly important when writing containers that respect the programmer's explicit constructors. If the container needs to move around its contents, such as when a std::vector is resized, then it should allocate the necessary space and then the constructor should be explicitly invoked. If the container is simply copying data passed in with a template like I showed above, it should avoid explicitly calling the copy constructor.

Introducing Rvalue References

Moving on, I now have a container that requires no unnecessary copies for searching or removing items, but there's still a lot of wastage when I call insert(). There are two cases where I will make potentially expensive conversions that I don't want to. The first case is identical to the conversion problem with has() or remove(). An example:

MyContainer strings;

strings.insert("foobar");

Once again, a temporary std::string is created for the parameter. This temporary object is not the object that is actually stored in the container. A second copy will be made and inserted into the actual container. This means that I'll get two copies for a single insert when ideally I should only need one. This might not seem too bad with some "expensive" types like std::string, especially when GCC's libstdc++ using reference counting and VC++'s DinkumWare-based STL uses small string optimization. These don't apply to other types, like containers (it's not uncommon to have a container of containers, after all), and honestly both of those string optimizations are really pessimizations in many uses (and reference counted std::string implementations are no longer allowed by C++11 in any case). The second case of unnecessary copies during insert is when an already constructed temporary object is inserted. This is of course the golden example of rvalue reference. Most sites covering rvalue references list only that one use case, in fact. An example:

std::string some_api_call();

void my_function(MyContainer& strings)
{
   strings.insert(some_api_call());
}

The temporary object returned by some_api_call() is called an rvalue, as compared to lvalue. For those wondering, an lvalue is an expression that can be assigned to, while an rvalue is any expression that cannot be assigned to. In other words, the expression "some_api_call()" can be on the right-hand side of an assignment, but not the left-hand side. Notably, rvalues only exist for a single expression: if I call some_api_call() twice, even if inside the same expression, I'm going to get two separate std::string temporary objects returned from each call. The problem with the above code is that I'm going to copy this temporary object into my container, and then throw away the temporary, which is wasteful. Since the compiler knows that nobody else can use that std::string (its an rvalue, and cannot be used or accessed in any way after the call to insert() because it has no name), the compiler should be able to just move that temporary object into the container with no unnecessary copying. Rvalue references facilitate this by providing new syntax, allowing methods to be written that "know" whether their parameter is an rvalue or an lvalue, and which will only bind to non-const rvalues. The naive approach then for my container is to make two versions of insert; one for rvalue references that performs a move and another that makes copies. There's a small trick to that, so an example is in order:

template 
class MyContainer
{
   // ... rest of class

   // copy version of insert
   template 
   void insert(const ParamType& value)
   {
     m_SomeDataStructure->addNode(new Node(value));
   }

   // move version of insert
   template 
   void insert(ParamType&& value)
   {
     m_DataStructure->addNode(new Node(std::move(value)));
   }
};

The copy version looks normal enough. The rvalue reference version has two significant changes. The first is the change to the parameter type. Rvalue references are denoted by using two ampersands && instead of a single ampersand. Also, it makes no sense to declare an rvalue reference as const (the whole point of an rvalue reference is to be able to destructively move the contents out of the object), and only normal references can be declared as const. The second important note in the rvalue reference version of insert() is the use of std::move(). The std::move() function converts any non-const lvalue into an rvalue. At first that may seem redundant, since value was declared as an rvalue reference in the function prototype. However, it's important to understand the precise meaning of the syntax. When a function parameter is declared as an rvalue reference, that means that parameter will accept an rvalue. However, the parameter inside the function itself clearly has a name, and hence it is an lvalue! The parameter type declaration simply said what the function will accept, not how the function will actually use the value once it has it. Note that if the function took a non-const reference, it would not be legal to pass an rvalue to the function. That is, this code does not compile:

void my_func(std::string& string);

my_func("foo");

The reason is that a regular non-const reference can only bind to an lvalue, and the temporary std::string object that must be created to convert the string literal is an rvalue (as are all temporaries). If my_func has been declared as taking an rvalue reference, or if there was an overloaded version taking an rvalue reference, the code would be valid. Of course, in the presence of overloads, rvalues will bind to the overload taking an rvalue reference while, non-const lvalues will bind to the overload taking a non-const reference, and const rvalues and any lvalue will bind to the overload taking a const reference. Examples of what works and what doesn't below. Note that the variable one is an lvalue (it can be assigned to), the variable two is considered a constant (technically an rvalue, but it will not bind to rvalue reference), and that the expression one+two creates a new temporary integer which is an rvalue and not constant (conceptually the value 3 is absolutely constant, but remember that the result of 1 + 2 in C++ is a temporary object that simply contains the value 3).

void take_rvalue_ref(int&& value);
void take_lvalue_ref(int& value);
void take_const_ref(const int& value);

int one = 1;
const int two = 2;

take_rvalue_ref(one); // illegal
take_rvalue_ref(two); // illegal
take_rvalue_ref(one + two); // legal

take_lvalue_ref(one); // legal
take_lvalue_ref(two); // illegal
take_lvalue_ref(one + two); // illegal

take_const_ref(one); // legal
take_const_ref(two); // legal
take_const_ref(one + two); // legal

One more example, showing overloads:

void take_ref(std::string&& str) { std::cout < < str << " is an rvalue reference"; }
void take_ref(std::string& str) { std::cout << str << " is an lvalue reference"; }
void take_ref(const std::string& str) { std::cout << str << " is a const reference"; }

std::string foo = "foo";
const std::string bar = "bar"

std::string baz() { return "baz()"; }
const std::string qux() { return "qux()"; }

take_ref(foo); // prints "foo is an lvalue reference"
take_ref(bar); // prints "bar is a const reference";
take_ref(baz()); // prints "baz() is an rvalue reference";
take_ref(qux()); // prints "qux() is a const reference";

Hopefully that explains all the reference semantics clearly enough. It's pretty confusing at first, but clears up a bit with examples. If the above aren't enough, just try writing some more on your own, and it should start making sense soon enough. I recommend getting a grasp on this now before continuing, as the next part can be particularly tricky and requires a good understanding of the different types of references.

Rvalue References in Templates

Up above when I added rvalue references to the MyContainer class, I said that was a naive approach. The approach I took was to write two different versions of insert(), once that makes copies and that that does not. The problem is that required a lot of duplicate code (or would, in a real implementation at least), and the only part that is actually different inside the implementation is the use of std::move() in the moving version of the method. All that duplication leads to maintenance overhead and large binary code size, neither of which is desirable. Additionally, rvalue references have another important use, which is that of perfect forwarding. The idea of perfect forwarding is that sometimes programmers write functions or methods that are just wrap other functions, and take some or all of their parameters and pass them on to the wrapper functions. In fact, with my container, I have exactly this situation: the value I insert is actually passed on to the constructor for the instance of the object created inside the container. Now consider a wrapped function (or constructor) that takes multiple parameters, such as node type stored inside a key-value container like a map. What happens if this type's constructor accepts an rvalue reference for its first parameter but not its second, or for its second parameter but not its first? Or both? Or neither? I'd have to write four overloaded versions of insert() for each possible combination. For other kinds of functions that may take even more parameters, the number of overloads grows exponentially. This is not good. Thankfully the C++ committee took care of this problem, with a little bit of special magic for rvalue references. In fact, the example above is already using part of that trick, but not all of it. The trick is... tricky. It is this: if a templated parameter is an rvalue reference, the actual type of the parameter is an rvalue reference if the template type is an rvalue, and a regular reference otherwise. That needs an example.

template 
void my_func(Type&& param);

int one = 1;
const two = 2;

my_func(one); // type of param will be: int&
my_func(two); // type param will be: const int&
my_func(one + two); // type of param will be: int&&

It's magic. Normally, I hate magic. It makes code hard to read and maintain. Programmer luminaries such as Linus Torvalds famously despise C++ for the amount of magic it facilities, and its not hard to see their reasoning with features such as these. The feature does facilitate something useful, however, and mostly just works without much special effort. It's important to remember that this works only when the type is a template parameter. There's some relatively straight forward rules explaining how it all works, but it's definitely easier to understand with examples like the one above than it is to try to grok an explanation of the rules. Alright, so now I can get rid of the copy version of my insert(). Well, almost. There's the little problem of the std::move() call. If I try to pass a const reference to std::move(), the compiler will complain. With good reason, too. If the contained type has a move constructor, I only want that called when I'm actually passing an rvalue to the insert() method. What is needed then is a way to select which overloaded constructor to invoke based on the type passed into the insert(), and whether it was an rvalue reference or not. That facility is the std::forward<>() function. It works very similarly to std::move(). However, its return type is an rvalue reference if and only if the input parameter is an rvalue or is an lvalue declared as an rvalue reference. Additionally, due to implementation details of how the template magic works, std::foward<>() requires that the type of the value be specified explicitly, unlike std::move() which can infer the template parameter type.

Correct Use of Rvalue References in Containers

All that explanation and exposition and now we're finally ready for the big reveal: the version of insert() I can use in my container:

template 
class MyContainer
{
  // ...

  // one and only perfect insert function
  template 
  void insert(InsertType&& value)
  {
     m_SomeDataStructure->addNode(new Node(std::forward(value)));
  }
};

There it is. Only one insert() method is needed. This version will bind to rvalue references as well as anything else, and will forward that type perfectly to the Node constructor. If the value passed to insert() is an rvalue, and Node has an rvalue reference constructor, then the value will be moved into the new Node with no additional copies. To summarize what happens, I've got another example:

MyContainer strings;

std::string foo = "foo";
const std::strinf bar = "bar";

std::string baz() { return "baz"; }

strings.insert(foo); // copied
strings.insert(bar); // copied
strings.insert(baz()); // moved; no copies
strings.insert("qux"); // copied

The second two do possibly require some qualification. Technically, baz() makes a copy of a string literal and returns that, so one copy is made. This copy is made by baz() itself and not by the container or its insert() method. It's a bit of a poor example only because it's such a trivial function. Likewise, the fourth insert of the string literal "qux" does make a copy when the literal is constructed, but it's constructed in-place in the container, and does not require two copies like the original version of the container class did. A more reasonable example of where the performance benefit comes in is as follows:

std::vector generate_data(int param)
{
  std::vector result(3000000);

  /* push a couple million calculation into result based on param */

  return result;
}

MyContainer> results;

results.insert(generate_data(123));
results.insert(generate_data(456));
results.insert(generate_data(789));

In C++89, or with a naive container, that code would allocate and copy each of the std::vector's contents several times. With my container and the power of C++11 and rvalue reference, the only allocations made are when the std::vector's are initialize constructed, and the data is never copied.

Using Move Semantics Inside Containers

I've got this great container class that allows me to move expensive objects into it without requiring extra copies. Except, I haven't actually implemented any real container, and it turns out there's some things to know about how to do that. Above I've been using a sort of set container skeleton as an example. From now on, I'm going to use a std::vector type of container as the example, because it's the easier to understand for what I'm going to do. In particular, any container that has to move its elements around internally needs to do a few things specially. This might also include various implementations of hash tables that need to grow, as just one other example besides a vector. I'm going to look specifically at a simple version of the reserve() method on std::vector, which is the function that allocates more memory.

template 
void MyVector::reserve(size_t new_capacity)
{
  if (new_capacity > m_Capacity)
  {
    Type* new_array = operator new(sizeof(Type) * new_capacity);

    for (size_t i = 0; i != m_Size; ++i)
    {
      new (&new_chunk[i]) Type(m_Array[i]);
      m_Array[i]->~Type();
    }

    delete m_Array;

    m_Array = new_array;
    m_Capacity = capacity;
  }
}

Pretty basic. In quick review of std::vector's behavior: reserve() will allocate another memory chunk of the requested size, copy the old data to the new memory area, delete the old memory chunk, and update our internal data. Note that capacity is the number of items the vector can hold without needing to allocate more memory, while size is the number of elements currently in the vector. Size is strictly less than or equal to capacity, and its completely legal for size to be zero while capacity is a large number. Of course, that implementation will make full copies of its elements when it grows. That means making copies of expensive objects like those 3,000,000 element vectors in the previous example. It also means that objects of type std::unique_ptr<>, which do not have a copy constructor, cannot be used with that implementation. The fix is ridiculously simple, and should hopefully be clear at this point. Instead of calling the copy constructor normally inside the loop, the move constructor (if available) should be invoked, letting it optimize things by moving resources instead of copying them. Move constructors are constructors are implemented using rvalue references, which are conceptually temporary objects that won't be used anymore. The std::move() function forces an lvalue to be an rvalue reference. So the fix is to just update the actual copy construction line to use std::move(), resulting in the following loop:

for (size_t i = 0; i != m_Size; ++i)
{
   new (&new_chunk[i]) Type(std::move(m_Array[i]));
   m_Array[i]->~Type();
}

Notice that I did not remove the call to the destructor. This is important. Whether or not an object is passed to a function as an rvalue reference, the destructor is always called for every object when it goes out of scope. The implementation of move constructors and move asssignment operators in most classes will rely on this fact, as I'll go over soon. Short version: the destructor must always be called, always, period. If it's not clear why just yet, read on.

Writing Move-aware Classes

I've got containers that can take advantage of move semantics with rvalue references, but what I haven't done is explain how to actually write types that have move constructors that actually work. I'm coming up on the end of this long-winded article, so bear with me just a bit longer as I explain this final piece of the puzzle. The idea of a move constructor or move assignment operator is that some class "own" other resources which are expensive to duplicate, and which shouldn't be copied unnecessarily. Additionally, some classes have resources which cannot be duplicated at all, and hence it is not legal to copy the object; these types lack copy constructors and assignment operators, but should have move constructors and move assignment operators. A simple example of the former type is std::vector, which owns a pointer to a chunk of memory containing its elements. A good example of the latter type is std::unique_ptr<>, which guarantees that there is just one single handle to an object. A move constructor looks a lot like a copy constructor, except it takes an rvalue reference. Likewise, a move assignment operator looks a lot like a regular assignment operator, but takes an rvalue reference. I'm going to use a simplistic example class to illustrate things. Behold the integer box:

class IntBox
{
public:
  IntBox(int value = 0) : m_Ptr(new int(value)) {}
  IntBox(const IntBox& source) : m_Ptr(NULL) { *this = source; }
  ~IntBox() { delete m_Ptr; }

  IntBox& operator=(const IntBox& source)
  {
    if (this != &source)
    {
      delete m_Ptr;
      m_Ptr = new int(source.get());
    }
    return *this;
  }

  // pre-condition: m_Ptr is never NULL, so this is always safe
  int get() const { return *m_Ptr; }

private:
  int* m_Ptr;
};

I'll clarify what's going on with the copy constructor for anyone not familiar with the trick used. The idea is that we can just default construct the object and then use the assignment operator and have the same result with less effort than if we duplicated the logic in both the copy constructor and assignment operator. Once again, such a trivial piece of code makes for a slightly poor example, but it gets the point across. Also note that while the class has a precondition that m_Ptr never be NULL, and the copy constructor initializes m_Ptr to NULL, it will always be given a real address by the time the constructor ends. I recommend using that trick where possible. I've seen a few people express dismay over the "performance problems" with the code, so I'd like to take a moment to dispel those worries. Thing is, the compiler is very smart. It going to see all the redundancies that I see, and it's going to remove them. But only when optimizations are turned on, and only when there's actually redundancies. Programmers who try to "test" the optimization by setting break points in a debug build (with no optimizations turned on, and hence every empty useless do-nothing redundant line of code is executed as written) are getting misled. Likewise, trying to add output logging by definition makes the functions non-trivial and of course the logging calls are not going to be optimized out. Obvious enough, I'd hope. Getting on to the interesting bit, I'm going to get rid of the inefficiency that IntBox has when it's used inside a std::vector. I certainly don't want the code to allocate a new chunk of memory and copy the value into it just to delete the old chunk of memory afterward. That doesn't accomplish much besides burning cycles.

class IntBox
{
public:
  IntBox(int value = 0) : m_Ptr(new int(value)) {}
  IntBox(const IntBox& source) : m_Ptr(NULL) { *this = source; }
  IntBox(IntBox&& source) : m_Ptr(NULL) { *this = std::move(source); }
  ~IntBox() { delete m_Ptr; }

  IntBox& operator=(const IntBox& source)
  {
    if (this != &source)
    {
      delete m_Ptr;
      m_Ptr = new int(source.get());
    }
    return *this;
  }

  IntBox& operator=(IntBox&& source)
  {
    if (&source != this)
    {
      delete m_Ptr;
      m_Ptr = source.m_Ptr;
      source.m_Ptr = nullptr;
    }
    return *this;
  }

  // pre-condition: m_Ptr is never NULL, so this is always safe
  operator int() const { return *m_Ptr; }

private:
  int* m_Ptr;
};

Not a whole lot to it. The move assignment operator is actually quite a bit simpler than the regular version, and the move constructor is almost identical to the copy constructor. Again, the use of std::move() in the move constructor is because the source parameter is an lvalue (because it has a name and can be assigned to) despite being declared as an rvalue reference. One final example, just showing what happens when each of the

IntBox foo()
{
  return IntBox(42);
}

void test()
{
  // conversion constructor
  IntBox one(1);

  // copy constructor
  IntBox two(one);

  // move constructor;
  // we promise not to use two again, but the compiler won't stop us
  IntBox too(std::move(two));

  // conversion constructor, then move assignment operator;
  // memory from too's old valid is freed
  too = 2;

  // move constructor
  IntBox three(foo());

  // move assignment operator;
  // memory from one's old value is freed
  one = foo();

  // move assignment operator;
  // we promise not to use three again, but the compiler won't stop us;
  // memory from one's old valid is freed
  one = std::move(three);

  // copy constructor
  IntBox four(one);

  // assignment operator
  IntBox five = one;

  // prints 1211
  std::cout << one << too << four << five << std::endl;

  // this will probably crash;
  // we did promise not to do this after using std::move on both of these
  /*std::cout << two << three << std::endl;*/

  // everything goes out of scope;
  // memory from one, too, four, and five is freed;
} 

Default Constructors and Methods

One very final note. All classes by default will have a default copy constructor and assignment operator defined. In the first version of IntBox, if I had omitted my overridden versions of the constructor and assignment operator, the m_Ptr member would be copied by value and the class would likely not work correctly. However, in the second version that has the move constructor and move assignment operator, the default copy constructor and assignment operator would be suppressed. The following class example, for instance, does not allow for copying, but does allow for moving. This is how types like std::unique_ptr are implemented:

template 
class Unique
{
public:
  Unique() : m_Ptr(nullptr) {}
  Unique(Type* ptr) : m_Ptr(nullptr) {}
  Unique(Unique&& source) : m_Ptr(nullptr) { *this = std::move(source); }
  ~Unique() { delete m_Ptr; }

  Unique& operator=(Unique&& source)
  {
    if (this != &source)
    {
      delete m_Ptr;
      m_Ptr = source.m_Ptr;
      source.m_Ptr = nullptr;
    }
    return *this;
  }

  Type* operator->() { return m_Ptr; }
  const Type* operator->() const { return m_Ptr; }

private:
  Type* m_Ptr;
};

Note that while not complete, it does offer most of the basic features of std::unique_ptr. This type can be put into any move-aware container and will guarantee that only one instance of its pointed-to object will exist at any time. Update: Removed the bad advice about "simple" implementations of moving assignment operators per Scott Meyer's excellent advice.