(Another) MacBook Pro hard drive upgrade (17" model)

In October I performed surgery on my 15" MacBook Pro, to upgrade the hard drive. Today I've been repeating the performance, but on a 17" MacBook Pro.

A few observations on the different models:

• Upgrading the 17" model was easier. (Partly because I've done it once before, and partly because it's generally a more accessible machine.)
• The screw patterns are identical. However, the Phillips screws inside the battery cover are far more accessible than on the 15" model; they're angled so you can get a screwdriver to them without contorting your hand.
  
• The lid seems to crack off of a 17" model with greater ease - less fiddly plastic interlocking.
• There's more use of sticky tape inside a 17" machine!
  
• The nubs that hold the drive in the laptop chassis are different on the 17", asymmetrical in design. I wonder why the two models differ like this?
  

C++: An STL-like circular buffer (Part 7)

Time to air the dirty laundry, and — since every good metaphor must run to the bitter end — to ask a pantomime washer woman to save the day. Or something like that.

In part 6 we identified some serious object management issues with the existing circular_buffer design. Now we understand them, we'll learn how to fix them, and how to use a C++ allocator. This whole sordid tale will show us exactly how useful allocators are.

What is an allocator?

All STL containers take an allocator as a template parameter. The allocator is an abstraction used to allocate and free memory for items held in the container. The allocator interface is described in section 20.1.5 of the C++ standard.

An allocator is itself templated over the type of object it can allocate space for. Every STL container defaults the allocator template parameter to std::allocator, the standard C++ allocator which employs new and delete. You'll rarely specify an allocator by hand in day-to-day C++ code. The std::allocator class is described in section 20.4.1 of the standard.

The allocator interface is pretty straightforward. An allocator provides a number of typedefs, identical to those required of a container:

• value_type
• pointer
• const_pointer
• reference
• const_reference
• size_type
• difference_type

It provides a number of methods, including:

size_type max_size(); // Same as a container

// Allocate memory. The second parameter is an optional "hint"
// to the allocator, the address of the object allocated prior to
// this allocation.
pointer allocate(size_type,
          typename std::allocator<void>::const_pointer = 0);

// Relinquish allocated memory
void deallocate(pointer p, size_type);

// Construct an object at this (allocated) memory location
void construct(pointer p, const T &t);

// Destruct the object that was constructed in this memory location
void destroy(pointer p);

allocate and deallocate, as their names suggest, service requests for memory allocation or deallocation. More interestingly, construct and destroy are used to vivify an object in already-allocated memory (the memory must have originally come from this allocator). The default implementations employ placement new and invoke the object's destructor in place, as below:

void construct(pointer p, const T &t) { new(p) T(t); }
void destroy(pointer p) { p->~T(); }

That's the kind of C++ you'll very, very rarely write, but that is worth understanding all the same.

Adding the allocator to circular_buffer

So let's thread an allocator through our circular_buffer. The first step, naturally, is to add a new template parameter to the class. We'll default this to std::allocator, which will suit 99% of all users.

template <typename T, typename A = std::allocator<T> >
class circular_buffer
{
    // ...

Since the allocator provides a host of useful typedefs related to the object it allocates, we can refine our class' definitions accordingly:

 typedef T                                        value_type;
typedef A                                        allocator_type;
typedef circular_buffer<T,A>                     self_type;
typedef typename allocator_type::difference_type difference_type;
typedef typename allocator_type::reference       reference;
typedef typename allocator_type::const_reference const_reference;
typedef typename allocator_type::pointer         pointer;
typedef typename allocator_type::const_pointer   const_pointer;

We also extend the constructor to take an explicit allocator object (and supply a sensible default), and add get_allocator to retrieve it.

explicit circular_buffer(size_type capacity,
                        const allocator_type &a = allocator_type());
allocator_type get_allocator() const;

We'll need to hold a copy of the allocator alongside the other private data members. But more importantly, we must use the it to allocate the memory for m_buffer and to delete it again afterwards. The boost::scoped_array (which seemed like such a good idea at the time) goes, and we must therefore add a corresponding custom destructor, too.

public:
  ~circular_buffer();

private:
  size_type      m_capacity;
  allocator_type m_allocator;
  pointer        m_buffer;
  pointer        m_front;
  pointer        m_back;

The updated method implementations look like this:

template <typename T, typename A>
inline
circular_buffer<T,A>::circular_buffer
    (size_type capacity, const allocator_type &allocator)
: m_capacity(capacity),
m_allocator(allocator),
m_buffer(m_allocator.allocate(capacity)),
m_front(0),
m_back(m_buffer)
{
}

template <typename T, typename A>
inline
circular_buffer<T,A>::~circular_buffer()
{
  clear(); // Delete all objects before deallocating the buffer
  m_allocator.deallocate(m_buffer, m_capacity);
}

template <typename T, typename A>
typename circular_buffer<T,A>::allocator_type
inline
circular_buffer<T,A>::get_allocator() const
{
  return m_allocator;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::max_size() const
{
  // This is clearly more elegant than the previous implementation!
  return m_allocator.max_size();
}

// This version of push_back must constuct and detroy objects in m_buffer
// using m_allocators methods, rather than traditional construction, copying,
// assignment.
template <typename T, typename A>
inline
bool circular_buffer<T,A>::push_back(const value_type &value)
{
  // If the buffer is full, and data will fall off the back of the
  // buffer - so we must destroy the stale object first.
  // This is an implementation choice, we could instead use operator= on
  // the value_type to replace the item. However, that would require
  // value_type to provide a copy assignment operator.
  if (m_front && m_front == m_back)
      m_allocator.destroy(m_back);

  m_allocator.construct(m_back, value);

  // The rest of push_back is as it was before
  value_type *const next = wrap(m_back+1);
  if (!m_front)
  {
      // first entry in the buffer
      m_front = m_back;
      m_back = next;
      return true;
  }
  else if (m_front == m_back)
  {
      // buffer is full already, throw something away
      m_front = m_back = next;
      return false;
  }
  else
  {
      m_back = next;
      return true;
  }
}

template <typename T, typename A>
inline
void circular_buffer<T,A>::pop_front()
{
  assert(m_front);

  m_allocator.destroy(m_front);
  value_type *const next = wrap(m_front+1);
  if (next == m_back)
      m_front = 0;
  else
      m_front = next;
}

template <typename T, typename A>
inline
void circular_buffer<T,A>::clear()
{
  if (m_front)
  {
      do
      {
          m_allocator.destroy(m_front);
          m_front = wrap(m_front+1);
      }
      while (m_front != m_back);
  }
  m_front = 0;
}

That's everything that needs substantial change. Every other existing method definition gains an additional template parameter (but ignores it). Oh, and wrap() needs the ".get()"s striped from the m_buffer address lookups.

That's it.

We've fixed some nasty, subtle bugs and taken one step closer to STL perfection.

Next time: We begin to iterate. And then we iterate. And then we iterate. And then we...

C++: An STL-like circular buffer (Part 6)

We now have a circular_buffer that you can add data to, read data from, remove data from, and that seems superficially correct. Let's add one extra method, clear(), and then start fretting.

Clear

We can quite easily add clear(), a method that removes all the data from the buffer. (This is what many programmers initially confuse the empty() method for. Obviously empty is a question, and clear is a command. Go figure)

template <typename T>
void circular_buffer<T>::clear()
{
  m_front = 0;
}

That's simple enough, isn't it? We can make the buffer think it is empty again by simply resetting the m_front pointer. Let's test...

  circular_buffer<int> cb(5);

 assert(cb.push_back(7));
 assert(cb.push_back(8));
 assert(cb.push_back(9));
 assert(cb.size() == 3);
 assert(cb.capacity() == 5);
 assert(!cb.empty());
 assert(cb.front() == 7);

 cb.clear();
 assert(cb.size() == 0);
 assert(cb.capacity() == 5);
 assert(cb.empty());

Success. Hurray.

Falling from grace

However, we've ignored the elephant for long enough. This method is the straw that broke the elephant's back. What happened to all the data that was in the buffer? So far, we've only tested with ints, so nothing interesting has happened at all.

But what if you want a circular_buffer of a large user-defined class, Foo? This is what is going to happen:

• The constructor will allocate an array of m_capacity default-constructed Foos. If there isn't a default constructor then constructing the circular_buffer will not compile. An empty buffer should not have constructed anything.
• push_back replaces Foo objects in the array with Foo's assignment operator
• pop_back does not destruct the Foo being removed
• empty does not destruct the Foos that have been put in the buffer

That's not ideal. In fact, it's downright incorrect. Here's a little illustration to prove the point; at the end of IllustrateTheProblem you would have expected no TheProblem objects to have been constructed.

  struct TheProblem
{
    static size_t constructed;
    TheProblem() { ++constructed; }
};

size_t TheProblem::constructed = 0;

void IllustrateTheProblem()
{
    assert(TheProblem::constructed == 0);
    circular_buffer<TheProblem> bufer(5);
    assert(TheProblem::constructed == 0); // this fails
}

There, we've said it. It's out in the open. We'll address this problem when we add allocators to the class design.

Intermission: Posting code on Blogger

The series I'm posting on circular buffers in C++ is a bit of a personal experiment in article writing; attempting to form an article on-line in pieces that can eventually be assembled into a cohesive whole.

Thanks for the feedback you're giving me, in comments and by email. The encouragement is great.

The experience has been an interesting one so far. In fact, it's also been a quite frustrating one. The Blogger editor is supremely unhelpful when you try to enter preformatted text (like C++ code).

• Code with angle brackets (e.g. < and >) is hard to get into Blogger without accidental butchering during editing or display, since you fall into all sorts of complex HTML problems.
• The Blogger editor continually reformats my pre-formatted code, stripping spaces, inserting spaces, realigning things. Every time you open the editor to fix one mistake, it breaks everything you fixed last time. Very frustrating.
  
• The editor window is far too small for anything except the smallest pieces of writing.
• I've attempted using external blog editing software, Quama to sidestep these issues. It's a beta version, and so somewhat buggy. It also has it's own ideas of how to butcher and reformat my code.
  
• The Blogger layout themes don't really help to make code readable at all.
  

If anyone has any cunning solutions to this problem, I would really love to hear them! Otherwise, I'll soldier on fiddling with code by hand and losing what's left of my hair. Please do point out layout issues to me, and I'll do my best to fix them.

C++: An STL-like circular buffer (Part 5)

So far we have created a fairly inert husk of a circular_buffer class. The few methods we've written allow you to easily discover that it doesn't have anything in it. And that's about it. We need to get data in and we need to get data out.

Refining the data representation

But first, let's consider the internal data representation. We originally decided that the buffer is empty when m_front == m_back, and full when 'm_front+1' (modulo m_buffer size) == m_back.

If you're observant you'll notice that this means the m_buffer array will never get completely filled. The circular_buffer will be considered full when there is one space left in m_buffer. Certainly, for a buffer of ints this might be acceptable, but a circular_buffer of a large custom data type might be consuming a lot of memory unnecessarily.

So what can be done about this? A simple mechanism that will work well is to set the m_front pointer to 0 when the buffer is empty. This simple change means the following methods change:

template <typename T>
circular_buffer<T>::circular_buffer(size_t capacity)
: m_capacity(capacity),
buffer(new value_type[capacity]),
m_front(0), //< initialisation change here
m_back(buffer.get())
{
}

template <typename T>
bool circular_buffer<T>::empty() const
{
 return !m_front;
}

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::size() const
{
 return !m_front ? 0
     : (m_back > m_front ? m_back : m_back+m_capacity) - m_front;
}

Getting data in

Following STL traditions, we'll provide a push_back method to push an item onto the back of the circular_buffer. At this point, we must decide what to do when the buffer is full. The options are:

• throw an exception
• return an error code
• silently ignore the data and leave the circular_buffer unchanged
• accept the data and consume the oldest peice of data at the back of the buffer

We'll choose the latter option. It would be perfectly possible provide several options in the future, either by a template traits parameter, a parameter to the push_back method, or a set of overloaded functions. This is left as an excercise for the reader.

Traditionally, a push_back method returns void, but we'll return a boolean value: true normally, or false if the new data has pushed old stale data from the back of the buffer. The signature is in the class declaration is therefore:

bool push_back(const value_type &);

It's basic template-code good practice to pass the parameter as a const reference. We'll not go into the reasons here, but make sure you know why.

Here's our first go at the implementation of push_back...

template <typename T>
bool circular_buffer<T>::push_back(const value_type &value)
{
 *m_back = value;

 value_type *const next = wrap(m_back+1);
 if (!m_front)
 {
     // first entry in the buffer
     m_front = m_back;
     m_back = next;
     return true;
 }
 else if (m_front == m_back)
 {
     // buffer is full already, throw something away
     m_front = m_back = next;
     return false;
 }
 else
 {
       m_back = next;
       return true;
 }
}

You'll notice that I have incanted a new method, wrap. This is a little internal helper that takes a pointer and wraps it around into m_buffer if it falls of m_buffer's bounds. We're going to be doing this quite a lot.

private:
value_type *wrap(value_type *ptr)
{
 assert(ptr < buffer.get() + m_capacity*2);
 if (ptr >= buffer.get()+m_capacity)
      return ptr-m_capacity;
 else
      return ptr;
}

Now let's check that it all works correctly:

int main()
{
circular_buffer<int> cb(5);

assert(cb.push_back(1));
assert(cb.size() == 1);
assert(cb.capacity() == 5);
assert(!cb.empty());

assert(cb.push_back(2));
assert(cb.size() == 2);
assert(cb.capacity() == 5);
assert(!cb.empty());

assert(cb.push_back(3));
assert(cb.push_back(4));
assert(cb.push_back(5));
assert(cb.size() == 5);
assert(cb.capacity() == 5);
assert(!cb.empty());

assert(!cb.push_back(6));
assert(cb.size() == 5);
assert(cb.capacity() == 5);
assert(!cb.empty());
}

Getting data out

We got it in there, now we need a way to get it out again. To read the contents we implement front(), which returns the item at the head of the buffer. We need two overloads, a const and non-const version:

// In declaration
reference       front();
const_reference front() const;

We can return a reference (or const_reference) to the data inside m_buffer to avoid unnecessary data copying.

What should the behaviour be when the circular_buffer is empty? Following the model set by existing STL containers, the result is undefined. The user Should Not do this, and if you do the class might just explode in a shower of bright purple sparks.

Of course, we'll be a bit more polite than that.

template <typename T>
typename circular_buffer<T>::reference circular_buffer<T>::front()
{
 assert(m_front);
 return *m_front;
}

template <typename T>
typename circular_buffer<T>::const_reference circular_buffer<T>::front() const
{
 assert(m_front);
 return *m_front;
}

Once we've read the item at the front, we need to remove it so we can get at the next item. The candidate for that is called called pop_front. Again, the user should not call pop_front if there is no data in the circular_buffer so we are quite at liberty to produce exciting purple sparks, or boring assertion failures.

template <typename T>
void circular_buffer<T>::pop_front()
{
 assert(m_front);

 value_type *const next = wrap(m_front+1);
 if (next == m_back)
     m_front = 0;
 else
     m_front = next;
}

If you're paying attention, you should by now be feeling very uncomfortable. There's an elephant lurking in the corner of this room. Clue: it's related to object lifetimes. We'll address this in the next installment.

Until then, we need to compose some reasonable tests for front() and pop_front(). To do this, I'll provide the entire code so far so you can see how it looks.

#include <boost/scoped_array.hpp>
#include <algorithm>

template <typename T>
class circular_buffer
{
public:
  typedef T                 value_type;
  typedef size_t            size_type;
  typedef value_type       &reference;
  typedef const value_type &const_reference;

  circular_buffer(size_t capacity);

  size_type    size()     const;
  size_type    max_size() const;
  bool empty() const;

  size_type capacity() const;

  reference       front();
  const_reference front() const;

  bool push_back(const value_type &);
  void pop_front();

private:
  const size_type                 m_capacity;
  boost::scoped_array<value_type> m_buffer;
  value_type                     *m_front;
  value_type                     *m_back; // points to next unused item

  typedef circular_buffer<T> class_type;
  circular_buffer(const class_type &);
  class_type &operator=(const class_type &);

  value_type *wrap(value_type *ptr)
  {
  assert(ptr < m_buffer.get() + m_capacity*2);
  if (ptr >= m_buffer.get()+m_capacity)
        return ptr-m_capacity;
  else
        return ptr;
  }
};

template <typename T>
circular_buffer<T>::circular_buffer(size_t capacity)
: m_capacity(capacity),
m_buffer(new value_type[capacity]),
m_front(0),
m_back(m_buffer.get())
{
}

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::capacity() const
{
  return m_capacity;
}

template <typename T>
bool circular_buffer<T>::empty() const
{
  return !m_front;
}

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::size() const
{
  return !m_front ? 0
      : (m_back > m_front ? m_back : m_back+m_capacity) - m_front;
}

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::max_size() const
{
  const size_type count = size_type(-1) / sizeof(value_type);
  return std::max(count, size_type(1));
}

template <typename T>
bool circular_buffer<T>::push_back(const value_type &value)
{
  *m_back = value;

  value_type *const next = wrap(m_back+1);
  if (!m_front)
  {
      // first entry in the buffer
      m_front = m_back;
      m_back = next;
      return true;
  }
  else if (m_front == m_back)
  {
      // buffer is full already, throw something away
      m_front = m_back = next;
      return false;
  }
  else
  {
      m_back = next;
      return true;
  }
}

template <typename T>
typename circular_buffer<T>::reference circular_buffer<T>::front()
{
  assert(m_front);
  return *m_front;
}

template <typename T>
typename circular_buffer<T>::const_reference circular_buffer<T>::front() const
{
  assert(m_front);
  return *m_front;
}

template <typename T>
void circular_buffer<T>::pop_front()
{
  assert(m_front);

  value_type *const next = wrap(m_front+1);
  if (next == m_back)
      m_front = 0;
  else
      m_front = next;
}

int main()
{
  circular_buffer<int> cb(5);

  assert(cb.size() == 0);
  assert(cb.capacity() == 5);
  assert(cb.empty());
  assert(cb.max_size() > 0);

  assert(cb.push_back(1));
  assert(cb.size() == 1);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 1);

  assert(cb.push_back(2));
  assert(cb.size() == 2);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 1);

  assert(cb.push_back(3));
  assert(cb.push_back(4));
  assert(cb.push_back(5));
  assert(cb.size() == 5);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 1);

  assert(!cb.push_back(6));
  assert(cb.size() == 5);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 2);

  cb.pop_front();
  assert(cb.size() == 4);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 3);

  cb.pop_front();
  assert(cb.size() == 3);
  assert(cb.front() == 4);

  cb.pop_front();
  assert(cb.size() == 2);
  assert(cb.front() == 5);

  cb.pop_front();
  assert(cb.size() == 1);
  assert(cb.front() == 6);

  cb.pop_front();
  assert(cb.size() == 0);
  assert(cb.capacity() == 5);
  assert(cb.empty());

  // empty again

  assert(cb.push_back(7));
  assert(cb.size() == 1);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 7);

  assert(cb.push_back(8));
  assert(cb.push_back(9));
  assert(cb.size() == 3);
  assert(!cb.empty());
  assert(cb.front() == 7);

  return 0;
}

C++: An STL-like circular buffer (Part 4)

Now it's time to think about the gory internal details of our circular_buffer.

Obviously, we need a data store for the buffer. A good old-fashioned array will do nicely, thank you. We'll need to remember the capacity of the array so we don't overrun it. And we must maintain a record of the front and the back of the data stored in the array. We could store these as indexes into the array, or as a pointer to the data. Let's go with the latter. There will be no need to separately store the number of items held in the buffer as it can be derived easily from the front/back pointers.

We want to play the C++ game nicely and make sure that we never leak resources, so we'll store the buffer in a boost::scoped_array (see here). So, here's a first stab at the data members for our class:

private:
const size_type                 m_capacity;
boost::scoped_array<value_type> m_buffer;
value_type                     *m_front;
value_type                     *m_back; // points to next unused item

Stylistic note #1: I really don't usually like m_ prefixes for member variables. However, since we will shortly need to create a public method called capacity(), we can't use that as a variable name. I don't want to instead use a bizarre variable name for "capacity", so I'll adopt this naming scheme.

Here's the plan:

• We insert new data at m_back.
• We read data from m_front.
  
• When m_front == m_back (as it will after construction), the buffer is empty.
• If the item after m_front is m_back, then the buffer is full.
  

Having established this, we can get on with some serious implementation:

The constructor

The constructor sets everything up as you'd expect. Note that we make it explicit so you can't write the nonsensical line: circular_buffer cb = 20;

// In declaration
explicit circular_buffer(size_t capacity);


template <typename T>
circular_buffer<T>::circular_buffer(size_t capacity)
: m_capacity(capacity),
m_buffer(new value_type[capacity]),
m_front(buffer.get()),
m_back(buffer.get())
{
}

Stylistic note #2: I'm writing the definitions of all methods out-of-line underneath the class declaration. This makes the class declaration far easier to read, at the expense of more typing are the definition.

If you're paying attention then you'll already realise that there may be some problems with this design. We'll get to this in Part 6.

Some easy questions

Now we can implement some of the simpler methods required by section 23.1 of the C++ standard. size() returns the number of items held in the buffer. empty() tells you if the container is empty (rather than emptying all the items out of it, which is a common newbie misunderstanding!) capacity() tells you how many items the container can hold. max_size() returns the size() of the largest possible container.

// In declaration
size_type size()     const;
size_type max_size() const;
bool      empty()    const;
size_type capacity() const;

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::capacity() const
{
  return m_capacity;
}

template <typename T>
bool circular_buffer<T>::empty() const
{
  return m_front == m_back;
}

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::size() const
{
  return (m_back > m_front ? m_back : m_back+m_capacity) - m_front;
}

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::max_size() const
{
  // Yes, this is a rather nasty trick. We could pull the maximum value for
  // size_type from std::numeric_limits instead of using -1.
  // But we'll do something even nicer shortly.
  const size_type count = size_type(-1) / sizeof(value_type);
  return std::max(count, size_type(1));
}

The only reasonably complex function is size() and it's clear what's going on in there, isn't it?

Note the use of typename in the function implementations above. That is required to help the compiler deduce that circular_buffer<T>::size_type is the name of a type; the poor thing can't work this out for itself.

Notable by their absense

The circular_buffer is notionally a sequence container (as defined by section 23.1.1 of the standard), by its very nature it does not support insertion or removal of items in the middle of the sequence. So we will not provide a version of insert() or erase(). We'll also chose not to support reserve(); unlike a growing container (e.g. std::vector), the circular buffer size must be supplied on construction. There is little point in providing an interface to change this capacity. (If you want to do this, I will leave it as an exercise for the reader).

Prohibit the prohibitable

Our choice of data storage means that it is not safe to copy or assign to a circular_buffer. Until we deign to fix this, we'll make sure that a user of the code can't shoot themselves in the foot:

// In declaration
private: // Not to be implemented
   typedef circular_buffer class_type;
   circular_buffer(const class_type &);
   class_type &operator=(const class_type &);

This is a standard c++ technique: we declare the copy constructor and assignment operator in the private section and don't implement them.

Testing

Before we bring part 4 to rest, we'd best check that those methods work. I usually use Aeryn, a great unit test framework for C++. But rather than indoctrinate you into the cult Aeryn right now, we'll write some simple tests using nothing more that the standard C assert macro.

int main()
{
  circular_buffer<int> cb(5);

  assert(cb.size() == 0);
  assert(cb.capacity() == 5);
  assert(cb.empty());
  assert(cb.max_size() > 0);
}

Right now, there's not much more we can do to the buffer. But that's all set to change...

C++: An STL-like circular buffer (Part 3)

Now it's time flesh out the class, and consider the interface we'd like to give it.

First, STL containers have a number of requirements, laid down in the C++ standard in section 23.1. This includes definitions for these nested type definitions:

• value_type - type of the items help in the container
  
• reference - type of a reference to an item in the container
  
• const_reference - type of a reference to a constant item in the container
  
• iterator - type of container iterator
  
• const_iterator - type of container const interator
  
• difference_type - type expressing the distance between two iterators (or const_iterators)
  
• size_type - type that represents any non-negative value of difference_type

As a first step, we'll add to our class the following typedefs, remembering that T is the template parameter name for the container item type:

  typedef T                 value_type;
  typedef size_t            size_type;
  typedef int               difference_type;
  typedef value_type       &reference;
  typedef const value_type &const_reference;

This is a starting point. We'll define the iterator types later, and some of these definitions can be made a little more elegant, too.

Next time: we'll decide the mechanics of the class and how to manage resources.