Search

10.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 provides. 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, C++ generally does not allow you to mix types inside a container. 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 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. 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.

IntArray.h:

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 this won’t always be possible, 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.

10.x -- Chapter 10 comprehensive quiz
Index
10.5 -- Dependencies

67 comments to 10.6 — Container classes

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

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

    • Darren

      Showing how to write these container classes may give you insight into how to write your own classes that may or may not be containers. But, yes, you should definitely have a good reason as to why you are writing your own container class and not using those provided in the STL.

      • Alex

        Yup, I’ve already added introduction lessons about std::array and std::vector, which you should have encountered if you’ve been reading sequentially.

        I intend to cover the standard library containers in more depth in a future chapter, but there are other topics that we need to talk about first to maximize our value (things like iterators and big-o notation).

        Even though you should use standard containers instead of writing your own, going through the logic of how these things are built gives you insight into how they work and what their limitations are.

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

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

      • Alex

        Yup, the memory allocated to data was assigned to m_data, so that memory can be used by the other class functions. It will eventually get deleted by the constructor (or another function that reallocates the memory).

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

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

      • Alex

        Exactly this.

        After calling Erase(), the object will still be in a valid state, so we need to make sure all member variables have expected, valid values.
        After the destructor is called, the object will be destroyed, so there’s no need to zero out values or set pointers to null, since all those values will be destroyed anyway.

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

    • Alex

      No, it’s not valid. We need to special case the situation where we’re removing the last element. I’ve updated the example to handle this.

      This is a good reminder as to why dealing with your own memory management should be avoided if possible -- it’s really easy to miss edge cases!

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

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

    • Alex

      m_data and m_length are part-of IntArray, and don’t have any value/meaning outside the IntArray. IntArray manages both of them entirely, including initializing and destroying them. The fact that m_data is a pointer instead of a normal value is irrelevant.

      That’s pretty much the definition of a composition.

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

        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.
          Thanks…

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

  • which websites do all of you recommend me to learn for computer graphics and openGL? Thank you very much.

  • Baubas

    Why do we need Reallocate() if we don’t use this function anywhere else?

    • Alex

      When building classes, it’s often good to consider what tools you might want to have handy at a later date, and add them while you’ve got a good understanding of the code. Coming back later and trying to add a new function will generally be more difficult.

  • gl4d14t0r

    Quick question. Why is the prefix of the member variables in classes started off with an ‘m_’? I have seen other C++ programmers do this too.

  • Ola Sh

    Hi Alex,

    It seems there’s an error in one of your sentences:(paragraph 2, line 5) …array container classes generally provide "dynamically resizing" (when elements are added or removed) and do bounds-checking. I think it should be …provide dynamic resizing". I really like your tutorials. It’s been helpful. Thanks.

  • Lance

    In the test section you are putting 20 before the sixth element and removing the fourth element. I think the comments are incorrect; unless we refer to a zeroth element

  • Hannah

    Hi,

    in Reallocate(), why do we need to delete[] m_pnData before we set it to pnData?

    • Alex

      Consider what would happen if m_pnData was already pointing to allocated memory. If we then overwrote m_pnData with pnData, then we’d lose our only pointer to that allocated memory, which means we’d have a memory leak.

      Deleting m_pnData ensures that any previously allocated data is properly cleaned up before we point m_pnData at something else.

      • Hannah

        So we wouldn’t have to do it if m_pnData was an array (or anything except for a pointer)?

        Thank you, Alex!

        • Alex

          Yeah, if m_pnData was an array, a vector, or some other type of class, the overloaded operator= would handle the memory allocation for you, so you’d only need to do an assignment. This is part of the reason why std::array, std::vector, and other classes are so great. Less code, less chances of mistakes, less things to worry about.

  • Hannah

    Now all is clear. Thanks Alex!

  • Abdul sami

    dear Alex . how can we return m_pnData .which is a pointer,how it works ,please explain ,thanks

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

  • Connor

    Hello Alex, I have 2 questions:

    1. In the void Resize() member function:

    However, in Lesson 6.9 you gave an example:

      Because pointers follow all of the same rules as normal variables, when the function ends, ptr will go out of scope. I’m confused why m_pnData doesn’t become a dangling pointer? Why don’t I get a compiler error that

    is already defined if it never went out of scope? Should we make it static?

    2. Also in the void Resize() member function,

    When this function is called a consecutive time, shouldn’t the pnData now point to a newly allocated handful of memory, without releasing the previous allocated memory, whereby leading to memory leak as the memory reserved for the previous pnData is now inaccessible?

    Thanks again for helping me struggle through this.

    • Alex

      1) When pointers go out of scope, they are destroyed. However, the contents that they point to are not (they are not implicitly deleted). So when pnData goes out of scope, pnData gets destroyed, but the memory allocated is still there. Normally this would result in a dangling pointer, except that we’ve already set m_pnData to point to that same value, so we still have a way to access it.

      2) You removed the line that prevents memory leaks! That’s what this line is for:

      In English:
      1) Allocate some memory and assign it to a temporary pointer
      2) Delete any old memory we’re holding onto
      3) Make our class point at the new memory we just allocated

      We can do those above 3 steps as many times as we want and each time we’ll swap newly allocated memory in and delete the old memory.

      Make sense?

      • Connor

        I think so. So it isn’t a pointer, pointing to a pointer, pointing to allocated memory.

        but rather re-initializing the address held by m_pnData.

        I was under the impression that m_pnData would be pointing to nothing (link lost between it and allocated memory) when pnData went out of scope.

  • cham

    hi alex how to make a class container ???

  • Matt

    What is the difference between including <assert.h> or <cassert>?

    • Alex

      In the general case, best practice in C++ is to include <cXXX> rather than <XXX.h>, as the <cXXX> headers tend to put less in the global namespace (they make better use of namespace std).

      In the specific case of cassert vs assert.h, since macros are namespace agnostic, there’s no difference.

      Nevertheless, I’ve updated the lesson to use cassert, since that better follows the best practice.

  • Matt

    In your "remove()" function, you wrote a comment after the assert statement:
    "// If this is the last element in the erase, set the array to empty and bail out".

    I think "erase" is a mistake.

  • Srinivasan RB

    Hi Alex,
    In resize methods we can add a conditional check to see if newSize is same as m_length and can return without erasing and creating array again.

    resize() {
            if (newLength == m_length)
                return;

            // If we are resizing to an empty array, do that and return
            if (newLength <= 0)
            {
                erase();
                return;
            }

    }

Leave a Comment

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