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
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 composition that store copies of the objects that they are holding (and thus are responsible for creating and destroying those copies), for example std::string. Reference containers or views are aggregations that store pointers or references to other objects (and thus are not responsible for creation or destruction of those objects), for example std::string_view.
Unlike in real life, where containers can hold whatever types of objects you put in them, in C++, containers typically only hold one type of data. For example, if you have an array of integers, it will only hold integers. Unlike some other languages, many C++ containers do not allow you to arbitrarily mix types. If you need containers to hold integers and doubles, you will generally have to write two separate containers to do this. 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 own the elements it’s organizing. As the name suggests, the container will hold an array of integers, similar to std::vector<int>.
First, let’s create the IntArray.h file:
|
1 2 3 4 5 6 7 8 |
#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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#ifndef INTARRAY_H #define INTARRAY_H #include <cstddef> // std::size_t #include <memory> class IntArray { public: // Use an alias for the type of index variables in case // we ever want to change it. using size_type = std::size_t; // The same goes for the element type. using value_type = int; private: size_type m_length{}; std::unique_ptr<value_type[]> m_data{}; }; #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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#ifndef INTARRAY_H #define INTARRAY_H #include <cstddef> #include <memory> class IntArray { public: using size_type = std::size_t; using value_type = int; private: size_type m_length{}; std::unique_ptr<value_type[]> m_data{}; public: // Constructs an empty array IntArray() = default; // Constructs an array of the given length IntArray(size_type length) : m_length{ length }, m_data{ std::make_unique<value_type[]>(length) } // Note: Dynamically allocating arrays of size 0 is allowed { } }; #endif |
We’ll also need some functionality to help us clean up IntArrays. We’ll write a function called erase(), which will erase the array and set the length to 0.
|
1 2 3 4 5 |
void erase() { m_data.reset(); m_length = 0; } |
Now let’s overload the [] operator so we can access the elements of the array. We perform bounds checking on the index to make sure it’s valid, which we do using the assert() function. By convention, element access operators don’t perform bounds checking, but at() functions do. We add an assert() anyway, because it only runs in debug mode, so it has no impact when we compile the program in release mode. We’ll also add an access function to return the length of the array. Here’s everything so far:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#ifndef INTARRAY_H #define INTARRAY_H #include <cassert> #include <cstddef> #include <memory> class IntArray { public: using size_type = std::size_t; using value_type = int; private: size_type m_length{}; std::unique_ptr<value_type[]> m_data{}; public: void erase() { m_data.reset(); m_length = 0; } size_type size() const { return m_length; } value_type& operator[](size_type index) { assert(index < m_length); return m_data[index]; } IntArray() = default; IntArray(size_type length) : m_length{ length }, m_data{ std::make_unique<value_type[]>(length) } { } }; #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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include "IntArray.h" #include <iostream> int main() { // Use direct initialization for types that might have a list-constructor. // IntArray doesn't have a list-constructor yet, but we'll add one in the // next lesson. IntArray array(5); array[2] = 123; for (IntArray::size_type i{ 0 }; i < array.size(); ++i) { std::cout << array[i] << ' '; } std::cout << '\n'; return 0; } |
Output
0 0 123 0 0
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 begin() and end() member functions. These will allow us to use IntArray with many of the standard functions as well as range-based for-loops. begin() and end() are straightforward, because we can use the begin and end of the array the IntArray storing internally.
|
1 2 3 4 5 6 7 8 9 |
value_type* begin() { return m_data.get(); } value_type* end() { return (m_data.get() + m_length); } |
Second, let’s write some code that will allow us to resize an array. We are going to write a resize() function, that will keep any existing elements in the array when its size increases and add new elements with value 0. If the array shrinks, all elements that are past the new end of the array are discarded.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <algorithm> // std::ranges::copy_n or std::copy #include <utility> // std::move // ... // resize resizes the array. Any existing elements will be kept, unless they don't fit into the new array. void resize(size_type newLength) { // If the array doesn't change size, we're done if (newLength == m_length) { return; } // 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_data // point to the new array. // First we have to allocate a new array auto data{ std::make_unique<value_type[]>(newLength) }; // 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. // copy_n copies the given number of elements from begin() to data. std::copy_n(begin(), std::min(m_length, newLength), data.get()); // Now we can override the old data pointer with the new array! // std::unique_ptr takes care of deallocating the old array for us. m_data = std::move(data); // Explanation below m_length = newLength; } |
std::move() is a sneak peak at move semantics, which we mentioned when introducing std::unique_ptr. It transfers ownership of the new array from data to m_data. By using std::move(), data is reset to a nullptr and won’t try to destroy the resource when it dies.
Whew! That was a little tricky! But it was worth it, we can now use range-based for-loops and standard algorithms
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include "IntArray.h" #include <algorithm> #include <iostream> int main() { IntArray array(5); array[2] = 123; for (auto i : array) { std::cout << i << ' '; } std::cout << '\n'; array.resize(3); array[0] = 312; std::ranges::sort(array); // Before C++20 // std::sort(array.begin(), array.end()); for (auto i : array) { std::cout << i << ' '; } std::cout << '\n'; return 0; } |
Output
0 0 123 0 0 0 123 312
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().
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
void insertBefore(value_type value, size_type index) { // Sanity check our index value assert(index <= m_length); // First create a new array one element larger than the old array auto data{ std::make_unique<value_type[]>(m_length + 1) }; // Copy all of the elements up to the index std::copy_n(begin(), index, data.get()); // Insert our new element into the new array data[index] = value; // Copy all of the values after the inserted element. // IntArray is storing the elements consecutively, so we can use // pointer arithmetic on its iterators. // Note: This is std::copy, not std::copy_n. All arguments are iterators. std::copy(begin() + index, end(), data.get() + index + 1); // Finally, replace the old array with the new array m_data = std::move(data); ++m_length; } void remove(size_type index) { // Sanity check our index value assert(index < m_length); // First create a new array one element smaller than the old array auto data{ std::make_unique<value_type[]>(m_length - 1) }; // Copy all of the elements up to the index std::copy_n(begin(), index, data.get()); // Copy all of the values after the removed element std::copy(begin() + index + 1, end(), data.get() + index); // Finally, use the new array m_data = std::move(data); --m_length; } // Additional functions just for convenience void pushFront(value_type value) { insertBefore(value, 0); } void pushBack(value_type value) { insertBefore(value, m_length); } |
Here is our IntArray container class in its entirety.
IntArray.h:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#ifndef INTARRAY_H #define INTARRAY_H #include <cassert> #include <cstddef> #include <memory> #include <algorithm> class IntArray { public: using size_type = std::size_t; using value_type = int; private: size_type m_length{}; std::unique_ptr<value_type[]> m_data{}; public: void erase() { m_data.reset(); m_length = 0; } size_type size() const { return m_length; } value_type& operator[](size_type index) { assert(index < m_length); return m_data[index]; } value_type* begin() { return m_data.get(); } value_type* end() { return (m_data.get() + m_length); } void resize(size_type newLength) { if (newLength == m_length) { return; } auto data{ std::make_unique<value_type[]>(newLength) }; std::copy_n(begin(), std::min(m_length, newLength), data.get()); m_data = std::move(data); m_length = newLength; } void insertBefore(value_type value, size_type index) { assert(index <= m_length); auto data{ std::make_unique<value_type[]>(m_length + 1) }; std::copy_n(begin(), index, data.get()); data[index] = value; std::copy(begin() + index, end(), data.get() + index + 1); m_data = std::move(data); ++m_length; } void pushFront(value_type value) { insertBefore(value, 0); } void pushBack(value_type value) { insertBefore(value, m_length); } void remove(size_type index) { assert(index < m_length); auto data{ std::make_unique<value_type[]>(m_length - 1) }; std::copy_n(begin(), index, data.get()); std::copy(begin() + index + 1, end(), data.get() + index); m_data = std::move(data); --m_length; } IntArray() = default; IntArray(size_type length) : m_length{ length }, m_data{ std::make_unique<value_type[]>(length) } { } }; #endif |
Now, let’s test it just to prove it works:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include "IntArray.h" #include <iostream> #include <numeric> // std::iota int main() { // Declare an array with 10 elements IntArray array(10); // Fill the array with numbers starting at 1 and counting up. // ie. numbers from 1 to 10 std::iota(array.begin(), array.end(), 1); // Resize the array to 8 elements array.resize(8); // Insert the number 20 before element with index 5 array.insertBefore(20, 5); // Remove the element with index 3 array.remove(3); // Add 30 and 40 to the end and beginning array.pushBack(30); array.pushFront(40); // Print out all the numbers for (auto i : array) { std::cout << i << ' '; } std::cout << '\n'; 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 most of the time you can use standard containers instead, and if you do need to write custom containers, you only have to write them once. Once the container class is working, you can use and reuse it as often as you like without any additional programming effort required.
It is also worth explicitly mentioning that even though our sample IntArray container class holds a built-in data type (int), we could have just as easily used a user-defined type (e.g. a Point class).
One more thing: If a class in the standard library meets your needs, use that instead of creating your own. For example, instead of using IntArray, you’re better off using std::vector<int>. It’s battle tested, efficient, and plays nicely with the other classes in the standard library. But sometimes you need a specialized container class that doesn’t exist in the standard library, so it’s good to know how to create your own when you need to. We’ll talk more about containers in the standard library once we’ve covered a few more fundamental topics.
%Missing lookup for lesson id 4839%
Leave a Reply