16.6 — Container classes

In real life, we use containers all the time. Your breakfast cereal comes in a box, the pages in your book come inside a cover and binding, and you might store any number of items in containers in your garage. Without containers, it would be extremely inconvenient to work with many of these objects. Imagine trying to read a book that didn’t have any sort of binding, or eat cereal that didn’t come in a box without using a bowl. It would be a mess. The value the container provides is largely in its ability to help organize and store items that are put inside it.

Similarly, a container class is a class designed to hold and organize multiple instances of another type (either another class, or a fundamental type). There are many different kinds of container classes, each of which has various advantages, disadvantages, and restrictions in their use. By far the most commonly used container in programming is the array, which you have already seen many examples of. Although C++ has built-in array functionality, programmers will often use an array container class (std::array or std::vector) instead because of the additional benefits they provide. Unlike built-in arrays, array container classes generally provide dynamic resizing (when elements are added or removed), remember their size when they are passed to functions, and do bounds-checking. This not only makes array container classes more convenient than normal arrays, but safer too.

Container classes typically implement a fairly standardized minimal set of functionality. Most well-defined containers will include functions that:

  • Create an empty container (via a constructor)
  • Insert a new object into the container
  • Remove an object from the container
  • Report the number of objects currently in the container
  • Empty the container of all objects
  • Provide access to the stored objects
  • Sort the elements (optional)

Sometimes certain container classes will omit some of this functionality. For example, arrays container classes often omit the insert and remove functions because they are slow and the class designer does not want to encourage their use.

Container classes implement a member-of relationship. For example, elements of an array are members-of (belong to) the array. Note that we’re using “member-of” in the conventional sense, not the C++ class member sense.

Types of containers

Container classes generally come in two different varieties. Value containers are compositions that store copies of the objects that they are holding (and thus are responsible for creating and destroying those copies). Reference containers are aggregations that store pointers or references to other objects (and thus are not responsible for creation or destruction of those objects).

Unlike in real life, where containers can hold whatever types of objects you put in them, in C++, containers typically only hold one type of data. For example, if you have an array of integers, it will only hold integers. Unlike some other languages, many C++ containers do not allow you to arbitrarily mix types. If you need containers to hold integers and doubles, you will generally have to write two separate containers to do this (or use templates, which is an advanced C++ feature). Despite the restrictions on their use, containers are immensely useful, and they make programming easier, safer, and faster.

An array container class

In this example, we are going to write an integer array class from scratch that implements most of the common functionality that containers should have. This array class is going to be a value container, which will hold copies of the elements it’s organizing. As the name suggests, the container will hold an array of integers, similar to std::vector<int>.

First, let’s create the IntArray.h file:

Our IntArray is going to need to keep track of two values: the data itself, and the size of the array. Because we want our array to be able to change in size, we’ll have to do some dynamic allocation, which means we’ll have to use a pointer to store the data.

Now we need to add some constructors that will allow us to create IntArrays. We are going to add two constructors: one that constructs an empty array, and one that will allow us to construct an array of a predetermined size.

We’ll also need some functions to help us clean up IntArrays. First, we’ll write a destructor, which simply deallocates any dynamically allocated data. Second, we’ll write a function called erase(), which will erase the array and set the length to 0.

Now let’s overload the [] operator so we can access the elements of the array. We should bounds check the index to make sure it’s valid, which is best done using the assert() function. We’ll also add an access function to return the length of the array. Here’s everything so far:

At this point, we already have an IntArray class that we can use. We can allocate IntArrays of a given size, and we can use the [] operator to retrieve or change the value of the elements.

However, there are still a few thing we can’t do with our IntArray. We still can’t change its size, still can’t insert or delete elements, and we still can’t sort it.

First, let’s write some code that will allow us to resize an array. We are going to write two different functions to do this. The first function, Reallocate(), will destroy any existing elements in the array when it is resized, but it will be fast. The second function, Resize(), will keep any existing elements in the array when it is resized, but it will be slow.

Whew! That was a little tricky!

Many array container classes would stop here. However, just in case you want to see how insert and delete functionality would be implemented we’ll go ahead and write those too. Both of these algorithms are very similar to resize().

Here is our IntArray container class in its entirety.


Now, let’s test it just to prove it works:

This produces the result:

40 1 2 3 5 20 6 7 8 30

Although writing container classes can be pretty complex, the good news is that you only have to write them once. Once the container class is working, you can use and reuse it as often as you like without any additional programming effort required.

It is also worth explicitly mentioning that even though our sample IntArray container class holds a built-in data type (int), we could have just as easily used a user-defined type (e.g. a Point class).

One more thing: If a class in the standard library meets your needs, use that instead of creating your own. For example, instead of using IntArray, you’re better off using std::vector<int>. It’s battle tested, efficient, and plays nicely with the other classes in the standard library. But sometimes you need a specialized container class that doesn’t exist in the standard library, so it’s good to know how to create your own when you need to. We’ll talk more about containers in the standard library once we’ve covered a few more fundamental topics.

16.7 -- std::initializer_list
16.5 -- Dependencies

193 comments to 16.6 — Container classes

  • shapecoder

    Wait. What happens when the container is empty? m_length will be 0, so this assert will accept 0 as a valid index, but there will be no data at m_data[0]...

    The other asserts are written like this:

    That makes sense. If m_length == 0, 0 will not be a valid index...

    Do I get a bonus point now?

    • nascardriver

      Assume index=0

      Replacing the index variable, we're left with

  • HangUp

    hello, I am a little bit confused about the definition of a container class can it only be an array like the one shown in this lessons or can it be a simple data struct like this:

    • nascardriver

      I'm not aware of a official definition. To my knowledge, a container is a type that can store any number of elements. The internal structure does not matter, it can be a contiguous array, a list, a map, whatever you like.

      All types in the standard libraries container library ( ) can store any number of elements.
      `std::tuple` (and `std::pair`) (A type where each element has to be specified separately) is located in the utility library, rather than the containers library.

  • kio

    This is gold!, thanks Aleks and Driver :)

  • michael oska


    in the Resize() function why we didn t delete the data array after? delete[] data;

  • yeokaiwei

    On Microsoft Visual Studio 2019, you will get a C6386 warning for 2 lines of code.

    Warning    C6386    Buffer overrun while writing to 'data':  the writable size is '(m_length+1)*4' bytes, but 'index' bytes might be written.    

    "data[index] = value;"

    "for (int before{ 0 }; before < index; ++before)
           data[before] = m_data[before];"

  • Robert Lennie

    Even simpler...

  • Aryan Parekh

    when we overload the [] operator , why can't we do int operator[] rather than reference It with int& operator[]?

  • Michael Wycombe

    What exactly does this statement do?
        IntArray() = default;

    I can't find where default it defined..


  • Tim

    When I ran your code, I got the warnings below on lines 117 and 146:

    Severity    Code    Description    Project    File    Line    Suppression State
    Warning    C6386    Buffer overrun while writing to 'data':  the writable size is '(m_length-1)*4' bytes, but '8' bytes might be written.    ConsoleApplication1    F:\Fall2020\ConsoleApplication1\ConsoleApplication1\IntArray.h    101

  • SaMIRa

    This is my 'remove' function , it works fine I guess:

Leave a Comment

Put all code inside code tags: [code]your code here[/code]