Language Selector

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:

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.

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.

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

11.1 -- Introduction to inheritance
10.3 -- Aggregation

43 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?

  • 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


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


  • 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:

    and not:

    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.

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

      Plus, it’s simpler to put in

      than it would be to use

      and a separate error-checking line. Had

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

      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?

  • 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;

  • 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.
    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;

    • Michael Bresette

      The destructor function is only called whenever a variable of that type is destroyed. So, if you set m_pnData = 0; m_nLength = 0; they wouldn’t actually do anything because those variables are a piece of the class we’re destroying. It would be the equivalent to setting a functions local variables to 0 at the end of it, they’re going to be destroyed when they go out of scope so there is really no point.

  • 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!

    • momalok

      Also, i noticed that you didnt cover sorting here, unless i missed something. Was that intentional?

    • niravkarani

      To understand why cArray[i] = i+1; works, refer to section 9.8 - overloading the subscript operator. In particular, have a look at the sub-section ‘Why operator[] returns a reference’.

  • Janez

    Is this a valid expression: int *pnData = new int[0]? If it is, what is the point of all special cases (when m_nLength equals to 0)? If it isn’t there is a bug in the Remove function.

  • Enrique

    Thank you very much for the detailed explanation, BUT what I see is that this is an array of INTEGERS  and not a container CLASS. You can make an example where you work with classes. Thank you very much.

  • Peter

    I think it is before the 6th and remove the 4th

  • Sheik

    Got the logic of container how it works.. Its more about that how we implementing the algorithm.

    People commenting here are more discussing about how the containers got implemented but i just want to know how this Integer container related to composition.
    As far as my understanding,
    1. here we don’t have any sub-classes (any way this is simple IntArray that’s why we dont have separate sub-class)
    2. we are using pointers to hold data (any way allocating when main class created and deallocating when main class destroyed)

    Please correct me if my understanding is wrong.

  • Migal

    Hi, thank you for this fantastic tutorial.

    In main() if I call cArray.Resize with a value greater than the previous array
    ( ex.

    i got the un-set elements of the array set to zero.

    i.e : 40 1 2 3 5 20 6 7 8 9 10 0 0 0 0 0 0 0 0 30

    I expected to have garbage instead of that zero.
    Are they set to zero when I dinamically make a new array or is just garbage?

  • Mostafa

    Thanks A lot sir.
    I hope for you the best.
    Thanks again for your Good Website.

  • Alex, please correct me if I am wrong:
    In the integer array class:
    1. All the parameters could be marked as consts.
    2. If I do this: IntArray my_array; with no parameters (or, IntArray my_array (0);), the constructor sets m_pnData and m_nLength to 0. Now if I wish to use reallocator (Reallocate ()) , what would happen? The first line In Reallocate () calls Erase() that deallocates the memory allocated in m_pnData. Deallocating a null pointer, does that make sense? We can put a condition in function Error (), that makes Error () deallocate memory In m_pnData only if it was previously allocated. Same problem with function Resize ().
    3. I failed to understand why you put this check inside Resize ():

    4. Shouldn’t the destructor set m_pnData to null? Isn’t it necessary?

    • Alex

      1) It wouldn’t hurt to make the parameters const, if for no other reason than to prevent the function from accidentally changing the value of a parameter.
      2) Deleting a null pointer doesn’t do anything -- it’s a no-op. There’s no need to explicitly guard against it. It’s only dereferencing a null pointer that causes problems.
      3) It’s technically not needed, but it makes the logic of the function easier to follow. With it, you know that the following block only executes if the current array has elements. Otherwise, you have to see that nElementsToCopy gets set to 0 and the for loop executes 0 times. That’s not immediately obvious. I’ll favor understandability over efficiency in most cases, and this one of them.
      4) No, it isn’t necessary. m_pnData will go out of scope at the end of the destructor, so setting it to null beforehand isn’t needed. Doing so will make your code slower for no real benefit.

  • JaSoN

    Hi Alex, I’m a big fan of you! What a great tutorial
    + Why do you have to create a constructor constructing an empty array because I delete it but the code still can run ?
    + What do you mean when you say Reallocate operates quickly and Resize operates slowly?
    + I failed to understand your idea about the beginning snippet of Reallocate and Resize: Why we have to erase, whats wrong with the if condition and what is the exactly "thing" we return ?
    + I need a refresh on this: int nElementsToCopy = (nNewLength > m_nLength) ? m_nLength : nNewLength; but I couldn’t remember which lesson, can you help me?
    + One silly question: Do you have a plan to write all of this or you just sit down and the code continuously appear in your head?
    The other parts of the lesson are perfect!
    Thank you so much for your time Alex!

    • Alex

      > + Why do you have to create a constructor constructing an empty array because I delete it but the code still can run ?

      When creating classes, it’s always good to consider how they _could_ be used, not just how you want to use them right now.

      We create a default constructor so that if we wanted to do something like this:

      array would have it’s member variables initialized correctly.

      > + What do you mean when you say Reallocate operates quickly and Resize operates slowly?

      I mean Reallocate() executes quickly and Resize() executes slowly (because it has to copy over elements from the old array to the new array, which takes time).

      > + I failed to understand your idea about the beginning snippet of Reallocate and Resize: Why we have to erase, whats wrong with the if condition and what is the exactly “thing” we return ?

      Erase() deallocates the currently allocated array (if it has been allocated), so we can either allocate a new array, or leave array unallocated (if nNewLength is 0). The if condition checks if we’re requesting an array of length 0, because in that case, we don’t need to allocate a new array. Nothing is returned, these functions return void. They simply modify the values of the classes member variables.

      > I need a refresh on this: int nElementsToCopy = (nNewLength > m_nLength) ? m_nLength : nNewLength; but I couldn’t remember which lesson, can you help me?

      Lesson 3.4 -- Sizeof, comma, and conditional operators.

      Basically, this sets nElementsToCopy to the smaller of nNewLength and m_nLength.

      > One silly question: Do you have a plan to write all of this or you just sit down and the code continuously appear in your head?

      I usually have a plan. How much of a plan depends on how complicated what I am doing is. If it’s something simple, then I just write it. For something of some complexity (such as this IntArray container class), I usually put more thought into it first. First I make sure I know what I want (in this case, a class to manage an array of integers). Then I decide what members I need (an int pointer and a length). Then I work on the primary functions (constructor, destructor, access functions). And finally, supporting functions (such as Resize() and Reallocate()) and operators.

      It’s sometimes useful to use comments to indicate what the function needs to do (handle zero case, allocate the new array, copy the elements, deallocate the old array) before writing the code to do it. I also often discover new useful functions as I go (for example, Erase()). Then I test the code, and usually find things that are broken, or cases that I missed. That requires modifications to the code to address.

      • JaSoN

        if (nNewLength<= 0)

        Are we talking about the same return ? PLease tell me if I’m wrong

        • Devashish

          Hello Jason, Reallocate() is written to “Reset” our array. Suppose we have an IntArray named myarray that has 10 elements in it. If we do this: myarray.Reallocate(5), all 10 elements are destroyed and new size for our myarray is set to 5.

          Now lets talk about this line, inside Reallocate

          Say, we have accidently passed -2 as argument for nNewLength. Now take a look at rest of the code inside Reallocate…

          Now m_pnData points to an array of size -2. Does that makes sense??? The condition ensures that Reallocation will only take place if valid array size is passed in as parameter, otherwise Reallocate exits and control returns to the caller.

          If we pass in the value of 0 (or any number less than 0), that means we now want our array to be empty.

          Reallocate calls Erase() in its first statement, so if there is an invalid value (or 0) passed in, our array will be destroyed (elements would be deleted), m_pnData set to null, and array’s new size will be 0. Let me know if it’s still not clear to you.

      • Quang

        Hi Alex, I thought : int nElementsToCopy = (nNewLength > m_nLength) ? m_nLength : nNewLength; sets nElementsToCopy to the BIGGER of nNewLength and m_nLength ? By the way you made copy - typo in void Remove() : inserted -> removed
        Great tutorial!!

        • Alex

          Is the same as:

          If we’re making the array larger, we only need to copy however many elements were in the older (smaller) array. If we’re making the array smaller, we only need to copy how many elements are in the new (smaller) array.

  • Mr D

    God, after reading through this lesson i feel like such a dimwit. I don’t understand it at all! :(

    I don’t understand: what is IntArray? Is it an Array?
    You said: "Our IntArray is going to need to keep track of two values: the data itself, and the size of the array."
    But an array has more then two values, right? It has as many values as the size of the array (plus the size).

    You said: "Now we need to add some constructors that will allow us to create IntArrays."
    I also don’t understand this! If I want to create an IntArray, i just code:

    Then i have an InArray, right?

    So as you can see, i really don’t understand what this IntArray class is and what it’s doing!
    Any chance you could just try one more time to explain it in simple terms?

    • Alex

      IntArray is just a custom-defined class.

      In the lesson on dynamically allocated arrays, we learned that we can have a pointer to an array and use it to access all the elements in the array, right?

      So our IntArray class contains a member variable (m_pnData) that holds this pointer to the array. We can use it to access all of the elements of the array. It also has another member variable (m_nLength) that stores the array length (since the array pointer doesn’t know how big the array is).

      If we had no constructors, we could create arrays as you suggest (IntArray MyArray), but what values would m_pnData or m_nLength be set to? They would be garbage. We use the constructors to ensure they get initialized with meaningful values, as well as allowing us to create an IntArray with a preset length, like this:

      Really, all we’ve done here is put a dynamic array inside a class.

      Does that help? How can I clarify for you further?

  • Mr D

    Thanks, i get it now! (i was thinking it was more complicated then it actually is!)

Leave a Comment




5 − 4 =

Put C++ code inside [code][/code] tags to use the syntax highlighter