Now imagine the amount of boilerplate and manual memory management you have to do in order to resize a simple array to store an arbitrary number of items:
#include <iostream>
void add_element(int*& arr, int& size, int new_value) {
// Allocate a new, larger array
int* temp = new int[size + 1];
// Copy the old elements to the new array
for (int i = 0; i < size; ++i) {
temp[i] = arr[i];
}
// Add the new element
temp[size] = new_value;
// Free the old array memory
delete[] arr;
// Point to the new array and update size
arr = temp;
++size;
}
int main() {
int size = 3;
int* scores = new int[size]{ 90, 85, 95 };
add_element(scores, size, 100);
for (int i = 0; i < size; ++i) {
std::cout << scores[i] << " ";
}
std::cout << "\n";
delete[] scores;
return 0;
}As you can see, this code works, but it poses a very important question: why do I need to write so many lines of code just to add a single integer to a collection? I had to allocate new heap memory, to copy the current content, to add new item, to deallocate old memory and to update my variables. Failure to deallocate array will lead to memory leak. One wrong offset while copying data will cause me to overwrite some data. C-style arrays and dynamic allocation is just too low-level tool to work with everyday collections.
How Standard Library Containers behaves
A container keeps a collection of elements and allows operations to store, find and remove them. Standard Library doesn't offer you a universal best container, since they vary in terms of element layout and access patterns. A vector stores elements consecutively, a linked list stores separate nodes and an associative container keeps elements sorted by keys.
In order to remove all this manual burden, C++ provides a set of template classes called containers, part of Standard Template Library. A container is an object which keeps a collection of other objects. It uses the concept of Resource Acquisition Is Initialization to encapsulate the logic of memory management.
Standard Library containers are classified according to how they store elements in memory and how it affects their performance for particular operations: As you can see, selecting the appropriate container will allow you to optimize the speed of your insertions, lookups or accessing sequentially without reinventing the wheel.
- Sequence Containers: Store elements in a strictly linear order. Access elements by their indexes. Examples: a dynamically resized array, a doubly-linked list, double-ended queue.
- Associative Containers: Automatically keep elements sorted by keys to allow quick lookups. Examples: a collection of sorted unique values, collection of sorted key-value pairs.
- Unordered Associative Containers: Use hash tables to organize elements and perform lookups with average constant time. Examples: unordered collection of unique values, unordered key-value collection.
- Container Adaptors: Wrap another sequence container to use particular behavior such as Last-In, First-Out or First-In, First-Out. Examples: stack and queue.
Select the operations that your program performs most frequently, rather than a container name that looks familiar to you. Random access, insertion point, ordering, duplicate keys, stability of references and memory overhead will help to narrow the choice down. Also, container member types let you refer to exactly the selected types in generic code.
Memory Ownership and Object Lifetimes in Containers
One of the major features of Standard Library containers is that they own their elements. When you insert an object into a container, it allocates its memory and copy/move the object to this memory. When container itself is destroyed, its destructor runs and destroys all elements and frees allocated memory.
This example shows how a container manages lifetime of objects it keeps, using a dynamic array container as an example:
#include <iostream>
#include <vector>
class Widget {
private:
int m_id;
public:
Widget(int id) : m_id{ id } {
std::cout << "Widget " << m_id << " created\n";
}
~Widget() {
std::cout << "Widget " << m_id << " destroyed\n";
}
};
int main() {
std::cout << "Entering block\n";
{
// Declare a vector that holds Widget objects
std::vector<Widget> widget_list;
// Add elements to the vector
widget_list.push_back(Widget(1));
widget_list.push_back(Widget(2));
std::cout << "Leaving block\n";
} // widget_list goes out of scope here, destroying its elements
std::cout << "Exited block\n";
return 0;
}As you may notice, Standard Library containers only manage memory of elements they directly own. If you put raw pointers into a container, it will deallocate only memory of pointers, not objects pointed by them, when it is destroyed, leaving objects orphaned on the heap. In order to avoid memory leaks, you should either store objects directly in the container or use smart pointers which will deallocate their resources when they are destroyed.
Exercise: Introduction to STL ContainersStarter code, hints and solutionOpenClose
Practice: Introduction to STL Containers
Work through the mission, reveal hints only when needed, and compare your result with the model solution.
Your challenge
Push one more Widget with id 3 and print the vector size. Explain why temporary and reallocation destructor messages must not be counted as stored elements.
Mission checklist
- Run the starter as a baseline, then predict the change requested in Your challenge.
- Make that change in your editor; use the lesson-specific hints if you need help.
- Compile and run your answer, then compare with the worked solution and explain the result.
Starter program
This is the working baseline, not the completed answer. Compile as C++20, then make the change described above.
#include <iostream>
#include <vector>
class Widget {
private:
int m_id;
public:
Widget(int id) : m_id{ id } {
std::cout << "Widget " << m_id << " created\n";
}
~Widget() {
std::cout << "Widget " << m_id << " destroyed\n";
}
};
int main() {
std::cout << "Entering block\n";
{
// Declare a vector that holds Widget objects
std::vector<Widget> widget_list;
// Add elements to the vector
widget_list.push_back(Widget(1));
widget_list.push_back(Widget(2));
std::cout << "Leaving block\n";
} // widget_list goes out of scope here, destroying its elements
std::cout << "Exited block\n";
return 0;
}Hints
widget_list owns its contained Widget values and destroys them when the vector leaves the inner block. The Widget(1) and Widget(2) arguments also create temporary objects.
Do not count every destructor message as the final destruction of a vector element: temporaries and reallocation can add messages. Track the vector's size separately from those lifetime events.
Worked solution
A third Widget is inserted with the vector's normal push_back operation. The added size output is 3. Constructor/destructor logging can also include temporaries and reallocation, so do not equate its message count with the number of elements; the shown trace is one implementation's run.
#include <iostream>
#include <vector>
class Widget {
private:
int m_id;
public:
Widget(int id) : m_id{ id } {
std::cout << "Widget " << m_id << " created\n";
}
~Widget() {
std::cout << "Widget " << m_id << " destroyed\n";
}
};
int main() {
std::cout << "Entering block\n";
{
// Declare a vector that holds Widget objects
std::vector<Widget> widget_list;
// Add elements to the vector
widget_list.push_back(Widget(1));
widget_list.push_back(Widget(2));
widget_list.push_back(Widget(3));
std::cout << "Stored widgets: " << widget_list.size() << '\n';
std::cout << "Leaving block\n";
} // widget_list goes out of scope here, destroying its elements
std::cout << "Exited block\n";
return 0;
}
Example output
This is one tested C++20 run. Sizes, capacity, formatting, floating-point details, or extra container lifetime messages may differ by implementation; use the explanation to identify the guaranteed result.
Entering block
Widget 1 created
Widget 1 destroyed
Widget 2 created
Widget 1 destroyed
Widget 2 destroyed
Widget 3 created
Widget 1 destroyed
Widget 2 destroyed
Widget 3 destroyed
Stored widgets: 3
Leaving block
Widget 1 destroyed
Widget 2 destroyed
Widget 3 destroyed
Exited block
0 comments
No comments yet. Be the first.