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 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, 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 it’s 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.7 -- std::initializer_list
Index
10.5 -- Dependencies

112 comments to 10.6 — Container classes

  • Nur

    Hello Alex,
    I have a question. In 8.9 — Class code and header files’s topic you quoted " we can put function declarations inside header files in order to use those functions in multiple files or even multiple projects. Classes are no different. Class definitions can be put in header files in order to facilitate reuse in multiple files or multiple projects".

    My question: Is this what you quoted above related to IntArray class.
    I mean, did you the create header file for IntArray class to use by other files or by other projects as well? i.e. Not only one file or project can be used container IntArray class and others as well, So the purpose of putting IntArray class in header file helps to reuse by other file or projects.Am I right?
    If i am not right here- could you explain? what is the purpose of putting the IntArray class in header file and main() for .cpp file separately?

    Thanks in advance!

  • KnowMore

    Alex? You haven’t deleted data pointer anywhere in the INT ARRAY class, so won’t there be memory leaks !?
    Shouldn’t You Do :-

    Instead of what you have done.. !?
    This also prevents memory leaks !
    Thanks For The Great Tutorials Anyway !
    Reply Plz

    • KnowMore

      Sorry, I realized that the above segment won’t work.
      Let me come directly to my question,
      1) Why didn’t you delete data pointer, Not deleting it wouldn’t cause memory leaks?
      And My Second Question,
      What’s the difference b/w :- ?

      and,

      I know that in the 1st case, they both would have same memory addresses and in the 2nd case, they would have diff. memory addresses.
      But still, the segment I asked you to replace doesn’t work ! Help Plz !
      Thanks in Advance 🙂

      • KnowMore

        Oh God ! Why am I so confused?
        Sorry Alex !
        The segment that I asked you to replace actually worked perfectly !
        So, Now My Only Question is,
        You haven’t deleted data pointer anywhere in the INT ARRAY class, so won’t there be memory leaks !?
        Thanks 😉

        • Help

          He made a function called erase() that delete the data if needed and if the object dies he delete it with destructor.

          • KnowMore

            I am talking about data pointer not m_data pointer.
            Look Again 🙂

            • Help

              Sorry, my bad! But isn’t m_data pointing at data ( m_data = data;) so they are both connected. Well im learning so im not the right person to give answer but what i understand is that m_data is later on assigned to point at same. so deleting m_data is same as delete data? so if we do several remove they keep stacking with point to point or maybe im just wrong but i think you got a point
              Well its better to wait for Alex answer 🙂

              • KnowMore

                You are actually right ! Don’t Worry ! Thanks for Helping ! I’m also Learning !
                But, The thing is that I’m deep copying not shallow copying in this :-

                In this, even if i Delete data it doesnt affect m_data….

        • Alex

          No. We’re doing 4 things in this code:
          * Dynamically allocating a new array (held by pointer data)
          * Copying the old array into the new array
          * Deleting the old array (held by m_data)
          * Setting m_data to point to the new array (m_data = data)

          We don’t have a memory leak here because of this line:

          This sets m_data to point at the new array we created. If we deleted data, then m_data would be a dangling pointer, and our class would have unexpected behavior the next time we dereferenced m_data.

          • KnowMore

            Ah Yes ! I mis-understood it earlier !
            Is it that as we are deleting m_data, dynamically allocated contents of data pointer also get deleted !?
            Can’t we do Deep-Copying Here Btw :-

            Thanks In Advance ! 🙂

            • Alex

              If we delete m_data, the contents of data also get deleted if and only if they are both pointing to the same thing.

              In your snippet of code, what does data represent?

              • KnowMore

                Exactly What I thought !
                data pointer is the extra ptr we created….
                I am deleting it explicitly (even though there is no need to), I just meant to ask That we can perform deep copying too there ! 🙂
                Thanks For The Help !!

  • Help

    Hi!
    When i run the code i get error do uk why? i copy paste the code and it gives me Assertion failed! index >= 0 && index < m_length.
    I copy pasted the code and it doesnt work

    By the way i have so much problem understanding when it comes to std::vector and std::vector when u use pointer to object in vector i get confused, any advice what knowledge i am missing? why use pointer to object and not just object?
    Thanks in advice:)

    • Help

      it supposed to say std::vector<object> and std::vector<*object>

      pointed object to vector and object to vector what is purpose for doing with point

    • Help

      I think i found the error! in ur insertBefore(int value, int index) when it calls insertAtEnd then u send insertBefore(int value, m_length) which will trigger the assert! so u need to have <= to be able to use the insertAtEnd to use that function!

      assert(index >= 0 && index <= m_length);

      • Alex

        Exactly right. I’d removed the equals sign in the index <= m_length check, but an index of m_length is actually valid here. I've updated the code to add it back in.

    • Alex

      Oops, my bad. I accidentally changed an assert I shouldn’t have in response to a previous comment. It should be fixed now.

      You should use a pointer to an object when your objects aren’t owned by the array/vector, or when your objects can’t be created with a default constructor.

      • Help

        Thanks for the respond! About that pointer to object there is something i am missing cause it doesnt ring a bell for me, and it always makes me unsure. Do u got any advice where i should go back and read cause it feels like something i am missing. like the 10.4 why pointer to patient and doctor in std::vector everything else i understand just something i always struggle with

        Thanks in advice and thanks for the great guide its helps a lot 🙂

        • Alex

          Hmmm, I don’t know if I’ve covered this topic anywhere explicitly. I updated lesson 10.4 to note that aggregations are normally implemented using pointers. In the doctor/patient example, we use Doctor and Patient pointers so that each can reference the other without implying ownership. If we tried to use normal members, it wouldn’t work for many reasons. First, a Doctor doesn’t have a Patient, so semantically the model is wrong. Second, if a Doctor included a Patient member and a Patient included a Doctor member, you’d get a circular reference that wouldn’t compile. Third, a normal member confers ownership -- if a Doctor had a Patient member, when the Doctor was destroyed, the Patient would be too.

          So, generally speaking, with arrays/vectors, you use normal members when you’re modelling compositions, and pointers when you’re modeling aggregations or associations.

  • Omri

    " // If this is the last element in the erase, set the array to empty and bail out
            if (m_length == 1)
            {
                erase();
                return;
            } "
    I think this should be:
    //If there is a single element in the array and erase() will render it empty do the following:

  • Omri

    In:
    "void insertBefore(int value, int index)
        {
            // Sanity check our index value
            assert(index >= 0 && index <= m_length);
            …"
    a. We require a valid index relating to the existing array.
        Why then allow index==m_length in index<=m_length?
    b. Sanity check… do you mean: relevance check?

    • Alex

      a) index >= m_length should be index > m_length. I’ve fixed that. Thanks for noticing the error.
      b) Same thing. It’s a colloquialism for ensuring what we’re doing makes sense.

  • Omri

    Regarding:
    "We need to make sure we set m_data to 0 here, otherwise it will be left pointing at deallocated memory!"
    Should this not be:
    "We need to set m_data to *nullptr* here, otherwise it will be left pointing at deallocated memory!"

    And further on:
            m_data = nullptr; //instead of 0
            m_length = 0;

  • C++ Learner

    why delete[] m_data is written also inside erase function if it is already written inside destructor?

    • Alex

      So the user has a way to manually erase the data and reset the class back to a null state if they want to do that without destructing the object.

      • C++ Learner

        thanks 🙂 can you say when destructor gets called in that code?
        The constructor is called when the object is created and destructor is called when object is destroyed, but what is the code that says the object is destroyed?

        • Alex

          It depends. Objects can get destroyed in a few ways:
          * If they have automatic duration (e.g. non-static local variables), at the end of the block they were declared in
          * If they have static duration, at the end of the program.
          * If they are allocated dynamically, whenever the user manually destroys them using the delete keyword.

  • Yifang Tan

    Hi Alex:
    I am trying to separate your example IntArray.h to header and body according to section 8.9, but always got error.
    Could it be possible for you, or anybody else, to correct my code?
    Thanks a lot!
    Yifang

    The header:

    And this is the body part:

    • Alex

      It looks like your functions in the header already have bodies:

      So the compiler is complaining that you’re trying to redefine them in the code file.

      Update the functions in the header to not supply definitions:

      • Yifang Tan

        Thanks a lot!
        There are always too many options for any subject, which is the complexity of C++, so that similar but more concise tutorial is needed for beginners.
        Very good tutorials and thank you again!

  • The blinking amber light could mean a dead …..omg i would forget the nae#hm8230;.t&e part that you plug in the power cord! a major problem for the dell opiplex 745 atleast!

  • john

    Just two minor corrections:
    "This array class is going to be a value container, which will hold copies of the elements its organizing." - typo, its -> it’s or it is.

    "And use the new array instead!  Note that this simply makes m_pnData point" - there is no m_pnData, var name is m_data.

Leave a Comment

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