Navigation



10.4 — 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 it’s 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 class. 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 instead because of the additional benefits it provides. Unlike built-in arrays, array container classes generally provide dynamically resizing (when elements are added or removed) 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 delete functions because they are slow and the class designer does not want to encourage their use.

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 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, C++ generally does not allow you to mix types inside a container. If you want one container class that holds integers and another that holds doubles, you will 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 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 its organizing.

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

#ifndef INTARRAY_H
#define INTARRAY_H

class IntArray
{
};

#endif

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.

#ifndef INTARRAY_H
#define INTARRAY_H

class IntArray
{
private:
    int m_nLength;
    int *m_pnData;
};

#endif

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.

#ifndef INTARRAY_H
#define INTARRAY_H

class IntArray
{
private:
    int m_nLength;
    int *m_pnData;

public:
    IntArray()
    {
        m_nLength = 0;
        m_pnData = 0;
    }

    IntArray(int nLength)
    {
        m_pnData = new int[nLength];
        m_nLength = nLength;
    }
};

#endif

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.

    ~IntArray()
    {
        delete[] m_pnData;
    }

    void Erase()
    {
        delete[] m_pnData;
        // We need to make sure we set m_pnData to 0 here, otherwise it will
        // be left pointing at deallocated memory!
        m_pnData = 0;
        m_nLength = 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.

#ifndef INTARRAY_H
#define INTARRAY_H

#include <assert.h> // for assert()

class IntArray
{
private:
    int m_nLength;
    int *m_pnData;

public:
    IntArray()
    {
        m_nLength = 0;
        m_pnData = 0;
    }

    IntArray(int nLength)
    {
        m_pnData = new int[nLength];
        m_nLength = nLength;
    }

    ~IntArray()
    {
        delete[] m_pnData;
    }

    void Erase()
    {
        delete[] m_pnData;
        // We need to make sure we set m_pnData to 0 here, otherwise it will
        // be left pointing at deallocated memory!
        m_pnData = 0;
        m_nLength = 0;
    }

    int& operator[](int nIndex)
    {
        assert(nIndex >= 0 && nIndex < m_nLength);
        return m_pnData[nIndex];
    }

    int GetLength() { return m_nLength; }
};

#endif

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 it’s 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.

    // Reallocate resizes the array.  Any existing elements will be destroyed.
    // This function operates quickly.
    void Reallocate(int nNewLength)
    {
        // First we delete any existing elements
        Erase();

        // If our array is going to be empty now, return here
        if (nNewLength<= 0)
            return;

        // Then we have to allocate new elements
        m_pnData = new int[nNewLength];
        m_nLength = nNewLength;
    }

    // Resize resizes the array.  Any existing elements will be kept.
    // This function operates slowly.
    void Resize(int nNewLength)
    {
        // If we are resizing to an empty array, do that and return
        if (nNewLength <= 0)
        {
            Erase();
            return;
        }

        // Now we can assume nNewLength is at least 1 element.  This algorithm
        // works as follows: First we are going to allocate a new array.  Then we
        // are going to copy elements from the existing array to the new array.
        // Once that is done, we can destroy the old array, and make m_pnData
        // point to the new array.

        // First we have to allocate a new array
        int *pnData = new int[nNewLength];

        // Then we have to figure out how many elements to copy from the existing
        // array to the new array.  We want to copy as many elements as there are
        // in the smaller of the two arrays.
        if (m_nLength > 0)
        {
            int nElementsToCopy = (nNewLength > m_nLength) ? m_nLength : nNewLength;

            // Now copy the elements one by one
            for (int nIndex=0; nIndex < nElementsToCopy; nIndex++)
                pnData[nIndex] = m_pnData[nIndex];
        }

        // Now we can delete the old array because we don't need it any more
        delete[] m_pnData;

        // And use the new array instead!  Note that this simply makes m_pnData point
        // to the same address as the new array we dynamically allocated.  Because
        // pnData was dynamically allocated, it won't be destroyed when it goes out of scope.
        m_pnData = pnData;
        m_nLength = nNewLength;
    }

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

    void InsertBefore(int nValue, int nIndex)
    {
        // Sanity check our nIndex value
        assert(nIndex >= 0 && nIndex <= m_nLength);

        // First create a new array one element larger than the old array
        int *pnData = new int[m_nLength+1];

        // Copy all of the elements up to the index
        for (int nBefore=0; nBefore < nIndex; nBefore++)
            pnData[nBefore] = m_pnData[nBefore];

        // Insert our new element into the new array
        pnData[nIndex] = nValue;

        // Copy all of the values after the inserted element
        for (int nAfter=nIndex; nAfter < m_nLength; nAfter++)
            pnData[nAfter+1] = m_pnData[nAfter];

        // Finally, delete the old array, and use the new array instead
        delete[] m_pnData;
        m_pnData = pnData;
        m_nLength += 1;
    }

    void Remove(int nIndex)
    {
        // Sanity check our nIndex value
        assert(nIndex >= 0 && nIndex < m_nLength);

        // First create a new array one element smaller than the old array
        int *pnData = new int[m_nLength-1];

        // Copy all of the elements up to the index
        for (int nBefore=0; nBefore < nIndex; nBefore++)
            pnData[nBefore] = m_pnData[nBefore];

        // Copy all of the values after the inserted element
        for (int nAfter=nIndex+1; nAfter < m_nLength; nAfter++)
            pnData[nAfter-1] = m_pnData[nAfter];

        // Finally, delete the old array, and use the new array instead
        delete[] m_pnData;
        m_pnData = pnData;
        m_nLength -= 1;
    }

    // A couple of additional functions just for convenience
    void InsertAtBeginning(int nValue) { InsertBefore(nValue, 0); }
    void InsertAtEnd(int nValue) { InsertBefore(nValue, m_nLength); }

Here is our IntArray container class in it’s entirety:

#ifndef INTARRAY_H
#define INTARRAY_H

#include <assert.h> // for assert()

class IntArray
{
private:
    int m_nLength;
    int *m_pnData;

public:
    IntArray()
    {
        m_nLength = 0;
        m_pnData = 0;
    }

    IntArray(int nLength)
    {
        m_pnData = new int[nLength];
        m_nLength = nLength;
    }

    ~IntArray()
    {
        delete[] m_pnData;
    }

    void Erase()
    {
        delete[] m_pnData;
        // We need to make sure we set m_pnData to 0 here, otherwise it will
        // be left pointing at deallocated memory!
        m_pnData = 0;
        m_nLength = 0;
    }

    int& operator[](int nIndex)
    {
        assert(nIndex >= 0 && nIndex < m_nLength);
        return m_pnData[nIndex];
    }

    // Reallocate resizes the array.  Any existing elements will be destroyed.
    // This function operates quickly.
    void Reallocate(int nNewLength)
    {
        // First we delete any existing elements
        Erase();

        // If our array is going to be empty now, return here
        if (nNewLength<= 0)
            return;

        // Then we have to allocate new elements
        m_pnData = new int[nNewLength];
        m_nLength = nNewLength;
    }

    // Resize resizes the array.  Any existing elements will be kept.
    // This function operates slowly.
    void Resize(int nNewLength)
    {
        // If we are resizing to an empty array, do that and return
        if (nNewLength <= 0)
        {
            Erase();
            return;
        }

        // Now we can assume nNewLength is at least 1 element.  This algorithm
        // works as follows: First we are going to allocate a new array.  Then we
        // are going to copy elements from the existing array to the new array.
        // Once that is done, we can destroy the old array, and make m_pnData
        // point to the new array.

        // First we have to allocate a new array
        int *pnData = new int[nNewLength];

        // Then we have to figure out how many elements to copy from the existing
        // array to the new array.  We want to copy as many elements as there are
        // in the smaller of the two arrays.
        if (m_nLength > 0)
        {
            int nElementsToCopy = (nNewLength > m_nLength) ? m_nLength : nNewLength;

            // Now copy the elements one by one
            for (int nIndex=0; nIndex < nElementsToCopy; nIndex++)
                pnData[nIndex] = m_pnData[nIndex];
        }

        // Now we can delete the old array because we don't need it any more
        delete[] m_pnData;

        // And use the new array instead!  Note that this simply makes m_pnData point
        // to the same address as the new array we dynamically allocated.  Because
        // pnData was dynamically allocated, it won't be destroyed when it goes out of scope.
        m_pnData = pnData;
        m_nLength = nNewLength;
    }

	    void InsertBefore(int nValue, int nIndex)
    {
        // Sanity check our nIndex value
        assert(nIndex >= 0 && nIndex <= m_nLength);

        // First create a new array one element larger than the old array
        int *pnData = new int[m_nLength+1];

        // Copy all of the elements up to the index
        for (int nBefore=0; nBefore < nIndex; nBefore++)
            pnData[nBefore] = m_pnData[nBefore];

        // insert our new element into the new array
        pnData[nIndex] = nValue;

        // Copy all of the values after the inserted element
        for (int nAfter=nIndex; nAfter < m_nLength; nAfter++)
            pnData[nAfter+1] = m_pnData[nAfter];

        // Finally, delete the old array, and use the new array instead
        delete[] m_pnData;
        m_pnData = pnData;
        m_nLength += 1;
    }

    void Remove(int nIndex)
    {
        // Sanity check our nIndex value
        assert(nIndex >= 0 && nIndex < m_nLength);

        // First create a new array one element smaller than the old array
        int *pnData = new int[m_nLength-1];

        // Copy all of the elements up to the index
        for (int nBefore=0; nBefore < nIndex; nBefore++)
            pnData[nBefore] = m_pnData[nBefore];

        // Copy all of the values after the inserted element
        for (int nAfter=nIndex+1; nAfter < m_nLength; nAfter++)
            pnData[nAfter-1] = m_pnData[nAfter];

        // Finally, delete the old array, and use the new array instead
        delete[] m_pnData;
        m_pnData = pnData;
        m_nLength -= 1;
    }

    // A couple of additional functions just for convenience
    void InsertAtBeginning(int nValue) { InsertBefore(nValue, 0); }
    void InsertAtEnd(int nValue) { InsertBefore(nValue, m_nLength); }

    int GetLength() { return m_nLength; }
};

#endif

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

#include <iostream>
#include "IntArray.h"

using namespace std;

int main()
{
    // Declare an array with 10 elements
    IntArray cArray(10);

    // Fill the array with numbers 1 through 10
    for (int i=0; i<10; i++)
        cArray[i] = i+1;

    // Resize the array to 8 elements
    cArray.Resize(8);

    // Insert the number 20 before the 5th element
    cArray.InsertBefore(20, 5);

    // Remove the 3rd element
    cArray.Remove(3);

    // Add 30 and 40 to the end and beginning
    cArray.InsertAtEnd(30);
    cArray.InsertAtBeginning(40);

    // Print out all the numbers
    for (int j=0; j<cArray.GetLength(); j++)
        cout << cArray[j] << " ";

    return 0;
}

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 (eg. a point class).

11.1 — Introduction to inheritance
Index
10.3 — Aggregation

28 comments to 10.4 — Container classes

  • Zafer

    Why did we use delete m_pnData instead of delete [] m_pnData?

    • Because I screwed up. :) Forgetting to use delete[] on arrays is a mistake I make all the time. That’s one of the reasons I generally use an Array class to do arrays — because it takes care of the deletes for me.

      In any case, I fixed the example. Thanks for catching this.

      • mahe

        Under code section “IntArray container class in it’s entirety”
        On line 79 new is allocated to pnData but on line 94 we delete[] m_pnData.
        On line 109 new is allocated to pnData but on line 123 we delete[] m_pnData.
        on line 134 new is allocated to pnData but on line 145 we delete[] m_pnData.
        so can we allocated “new” to one variable and “delete” different variable? dosen’t lead to memory leak?

  • [...] the lesson on container classes, you learned how to use aggregation to implement classes that contained multiple instances of other [...]

  • davidv

    In the Resize function, if the new length is bigger than the initial one, we will be left with some empty spots at the end. Is that fine, or should we fill those places by default with, say, zeros?

    • This is a good question with no correct answer.

      I think I’d personally leave those extra elements unallocated. If you’re accessing those values before you set them, you’ve got a logic problem with your code that needs to be fixed anyway. And if you do access them before setting them, you’re more likely to notice when your array value comes out as some strange number (eg. -26432593). Also, filling with 0′s takes extra time that may not be needed if you’re just going to overwrite the values anyway.

      However, I can see cases where it would be useful to default those elements to 0. For example, if I was using the array to hold the counts of different kinds of things, I’d want to start counting from 0. So I think the ideal solution would be to add an an optional boolean parameter on the Resize function that gives the user the choice to fill extra elements with 0 or not. That way, the user can decide on a case-by-case basis whether or not they want/need to do that. I’d also add that optional boolean parameter to the constructors so you could allocate an array filled with 0 in the first place if you wanted.

  • Eugene Wee

    Have you considered teaching about std::vector and the other standard containers? For example, std::vector is far more efficient than your naive dynamic array example, but it is not suitable for a beginners’ tutorial to cover the sophistication that makes such efficiency possible, so it is best for beginners to at least get to know what should be used before trying to reinvent the wheel.

  • Jacob Bundgaard

    Just a little tip.
    The InsertAtEnd function.
    I hope you can figure it out from this:

    assert(nIndex >= 0 && nIndex < = m_nLength);
    void InsertAtEnd(int nValue) { InsertBefore(nValue, m_nLength); }

    • MarkG

      Jacob,

      I’m just a beginner at c++ going through these examples, but I think what Alex has written is correct. As there are (n+1) ways to insert an object “next to” (n) objects, it makes sense to call the InsertBefore function with the m_nLength parameter, even though the value you’re inserting before doesn’t exist in the array. It worked well enough in the example of this code which I wrote and compiled.

      Did I interpret your post correctly? Maybe next time you could be a bit less cryptic :)

      Mark

  • Rob

    As an intermediate programmer using this site brushing up on my C++ I would definitely recommend at least adding a reference to the STL Container classes which would largely omit the need to write your own containers. If I didn’t already know about them, seeing the need to write these myself would make me think twice using C++ for my coding needs.

  • bla

    In the Resize function, why do you put:

     if (m_nLength > 0) 

    and not:

     if (m_nLength != 0) 

    ?
    This would, in my opinion, be more intuitively understandable (if m_nLength is < 0 this shouldn't this cause an error?). Or did I misunderstand something here?

    • D.M. Ryan

      Error trapping, without aborting the function. If by some mistake a negative number is passed, the code will just empty the array. Example: if main() has a way to knock down a size variable nArraySize to -1 when the programmer really meant 0, the function will treat nArraySize as if it were zero.

      if (m_nLength > 0)

      allows the function to adjust for the programmer’s intention with respect to emptying arrays.

      Plus, it’s simpler to put in

      if (m_nLength > 0)

      than it would be to use

      if (m_nLength != 0)

      and a separate error-checking line. Had

      if (m_nLength != 0)

      been used, the function would have to guard against negative values with a line like

      assert(nIndex >= 0);

      Alex’s choice collapses two lines into one, in a way that doesn’t halt the program if a negative number gets passed. Since Resize doesn’t declare an array, assert() isn’t really needed.

  • cooltoad

    Why did we need a Reallocate()? I don’t see it being used anywhere.

  • integral

    In the Resize function, will it be a good idea to end it with the following line:
    delete[] pnData;

    If we dont include the above, could we run into a memory leak problem?

  • [...] 16.2 — STL containers overview By Alex, on September 11th, 2011 By far the most commonly used functionality of the STL library are the STL container classes. If you need a quick refresher on container classes, check out lesson 10.4 — Container Classes. [...]

  • Punit Mishra

    Hey Alex. Thanks for such good article on container classes..One request i have..Can you post some good article on C++ design pattern..That will be really very helpful for us..

  • voodoojah

    Hey Alex. Thanks a lot for your articles! They are really helpful, interesting and precise. I’m so glad to accidentally find this site, surfing the web!
    But it’s double sad that you really wrote something misleading at least once. The function InsertAtEnd() in the IntArray designed in this article causes an assertion. The if statement (nIndex < m_nLength) will always evaluate false when we pass the parameter m_nLength. Perhaps you have missed it in a hurry.

  • Christian

    hey, really enjoying the tutorial, but I was wondering, in “void Resize(int nNewLength)” what ever happens to pnData, it never gets deleted, so does it just remain filling up memory? or would it get deleted at the end of the function?

    • Miguel

      pnData doesn’t get deleted because m_pnData was made to point to that address after deleting the original m_pnData.

      delete[] m_pnData;
      m_pnData = pnData;

  • [...] By far the most commonly used functionality of the STL library are the STL container classes. If you need a quick refresher on container classes, check out lesson 10.4 — Container Classes. [...]

  • tanekim77

    For the excerpt below, why doesn’t ~IntArray() does not include m_pnData = 0; m_nLength = 0; unlike Erase() does?

    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.
    ~IntArray()
    {
    delete[] m_pnData;
    }

    void Erase()
    {
    delete[] m_pnData;
    // We need to make sure we set m_pnData to 0 here, otherwise it will
    // be left pointing at deallocated memory!
    m_pnData = 0;
    m_nLength = 0;
    }

  • vipulcr

    “Here is our IntArray container class in it’s entirety”

    Shouldn’t this be “in its entirety”?

    Curious to know. Reply if possible.

  • momalok

    Hi there Alex.
    Nice lengthy section here! But well worth it.
    Just a couple things that confuse me here:
    1.) Why didnt you use implicit assignment here for the constructors in the above example, as in the previous sections?
    2.)Is there no need to overload the assignment operator here, as you use cArray[i] = i+1; clearly you dont because the program works fine, but im confused as to why that is?
    Any help is appreciated.
    Great tutorial!

You must be logged in to post a comment.