SECRET OF CSS

Standard Template Library (STL) in C++ — An Introduction to Containers | by Joseph Robinson, Ph.D. | Jul, 2022


Modern-day Effective C++

STL Like a Pro— introduce, understand, choose, use, and visualize containers!

Featured image for STL containers.
· Overview
Why use STL?
· STL Containers
Container types
Containers Visualized
Why use STL Containers?
· Container Specifications
· Sequential Containers
· Choosing the right container
· Conclusion
· References
· Supplemental Material
Vectors
Deques
Stacks
Lists and forward lists
Demo Code
· Additional Resources: Dig Deeper
· Contact

As part of our exploration of the Standard Template Library (STL) of C++, we next embark on a critical aspect of the library, STL Containers.

By the end of this tutorial, you will understand the following.

  • How to choose the correct container and the importance of doing so.
  • The types of containers offered by STL, along with their benefits and drawbacks.
  • The best data structure (i.e., container) choice for a given algorithm.

First, we introduce Containers and their importance in delivering Effective C++ [1].

For readers unfamiliar with STL, or those looking for the complete story, referring back to Part 1 is strongly suggested.

As in Part 1, STL comprises modules depicted as follows:

STL components.
Figure Source: https://www.mygreatlearning.com/blog/standard-template-library-in-c/

Where each child is a subject to its blog. Hence, STL, as a whole, will span multiple parts.

Why use STL?

STL provides the bells and whistles for fundamental algorithms and data structures, benefiting the user.

  1. It is well tested and optimized.
  2. There is no need to reinvent the wheel.
  3. It leads to shorter, more compact source code.

Note: (2) assumes the motivation is practical or solves a problem in research or industry. When learning the ins and outs of data structures (e.g., a Stack), a helpful exercise might involve the class implementation without STL; however, I believe there are more effective ways of learning these concepts while also learning the readily available STL. For example, as part of an introduction to C++ course or self-teaching, re-implementing the <string> header is also in the core C++ (see Part 1). Perhaps a subject for the future 🙂

Furthermore, STL, as a whole, is extendable and efficient in relating algorithms and data structures (see Part 1).

Provided M containers and N algorithms, there would typically be NxM processes when running combinations exhaustively. However, the iterators are at the STL philosophy’s core and structure, reducing the number of operations to N + M. Visually, we can depict this as follows.

1*bmULmJWym
Processing N algorithms and M containers typically would cost NxM operations (left); STL iterators allow the number of processes to be reduced drastically (i.e., N + M, right). Illustration created by the author (Part 1).

Include the header of the container, algorithm, iterator, or functors, with the latter three subjects to a future blog.

Include these headers to use STL.
As a part of standard C++, include headers to use STL. Created by the author.

By the end of the series, all components, and their connections, shown in the figure (right), will be well understood. So let us now dig deeper into STL containers.

STL Containers are common data structures with respective functionality. Why not implement our own — well, the motivation listed in 1–3 in the prior section summarizes the reason quite concisely. Let us refer to the words of an expert and leader in the technicalities of effective C++.

They’re simply better than their competition, regardless of whether that competition comes from containers in other libraries or is a container type you’d write yourself. STL containers aren’t just good. They’re really good. — Scott Meyers

Container types

Before listing the specific data structures provided as part of the STL API, let us look at its contents from a higher level.

Different container types.
Sequential and associative container types. Associative contains ordered and unordered. The author created visualization.

Although we will focus on containers that are sequence-based data structures, let us revisit the prior figure with examples of each type.

Example uses of different container types.
Example of each container type provided by STL. For each sample use-cases (top of the lists), for which the respective container type could be the basis, specific containers, as named conventionally and in the STL API, are listed as bullets (bottom).

Here is a glance at container types, along with a brief description. This table, and then some, will be clear by the end of this read.

STL container names, types (i.e., sequential, associative, or adaptor), and brief descriptions.

Containers Visualized

Visual of STL data structures.
STL containers per type, depicting the structures of each. Image by the author.

Why use STL Containers?

In his Modern-Day Effective STL [1], Steve Meyer chose the following item to start his renowned book.

ℹ️  Choose your containers with care.

As we will see, different containers are best for specific scenarios. And although the STL interface is clean and consistent enough to easily substitute one type for another (i.e., as demonstrated in the sample code below), a container choice can significantly affect the source code’s speed and clarity. Plus, algorithms are not agnostic to the option in the container. (i.e., to be covered when we reach below.

Before adopting a means to choose the best container, let us first look at a set of sequence containers.

Let us first read the Type column listed following table (refer back to the Description column later on in this blog, or scan over for now).

STL container types, description, and source (i.e., constructor signature). The top table lists the sequence-based containers, while the bottom table is the associative containers.

In summary, for the sequence-based containers:

  • array is static in size, while all others are dynamic.
  • array and an array sequences comprise vector and deque, respectively; list and forward_list use double and single linked lists.
  • Only list and forward_list do not support random access but forward/backward and forward, respectively.
  • Only list and forward_list always release memory;vector and deque have methods shrink_to_fit()With the latter sometimes releasing memory on its own.
  • Finally, vector and list have memory reservation, while deque and forward_list do not.
ℹ️  Beware the illusion of container-independent code.

Let us summarize a Situation and the corresponding container best to Pick.

RA represents random access (i.e., look-ups).

Now let us use the characteristics of the different types of containers to use logic in the following flowchart to choose the best container.

A flowchart that leads to leafs representing container types.
A flowchart that leads to leafs representing container types. Notice the legend groups containers by the different categories listed above. View the original chart created by the author on LucidChart.

However, such logic is not always provided in a problem. For the sake of generalizability, let us break down the big-O complexities of the different types in the following table.

Containers: operation complexity.
Containers: operation complexity. If blank, the respective operation (i.e., method) is not included as part of that container’s interface. It was created by the author using Canva.

Mai Pham summarizes Big-O complexities in the following blog post.

💡 Vector, list, and deque offer the programmer different complexity trade-offs and should be used accordingly; the vector is the type of sequence that should be used by default, and a list should be used when there are frequent insertions and deletions from the middle of the sequence, the deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence.

STL Containers are the best way to store data in C++. They provide many benefits over other methods, such as arrays. We have looked at several different types of containers and their uses. The best container for a given algorithm can be determined by understanding the trade-offs between the various options. STL provides an easy-to-use interface that makes it the best choice for most applications. We now know that STL containers offer a wide variety of options for data structures, all with different benefits and drawbacks. The best container depends on the specific algorithm and the target data. In general, STL containers are the best option for algorithms because they are efficient and versatile.

In conclusion, STL containers are the best tool for the job. They provide a wide range of options for choosing the perfect container for your data structure and algorithm. Additionally, STL is well-tested and reliable, so you can be confident that your code will work as expected.

[1] http://www.uml.org.cn/c%2B%2B/pdf/EffectiveSTL.pdf

[2] https://www.abebooks.com/Effective-STL-Specific-Ways-Improve-Use/22536211326/bd

[3]

Vectors

We have yet to discuss implementation (i.e., how to use containers) — this was intentional; the proceedings blogs in the series will teach us just that! But, first, we had to understand containers and the options we have when faced with implementation details.

As mentioned, different STL containers provide consistency in the interface, though. Furthermore, as should already be straightforward and will continue to grow more apparent, there are unique characteristics of each for the differences in the underlying structure: a topic we will revisit in-depth in an upcoming blog.

Let us exemplify with std::vector, which is similar to the other containers.

The std::vectortemplate provides dynamically-sized, heap-based arrays without the need for explicit memory management.

std::vector v; 
v.push_back(1);
v.push_back(2);
v.push_back(3);
std::cout << v[0] <<‘, ‘<< v[1] <<‘, ‘<< v[2] << std::endl;
// 1, 2, 3

STL offers a variety of constructors. For std::vector are the following:

  • Default constructor: creates an empty vector.
  • Copy constructor: creates a copy of an existing vector.
  • vector v(N, V): creates a vector with N elements set with values of K.
  • vector v(N): creates a vector with N elements (values of zero)

If you have a vector of items vBut need to pass it on a function call void f(int *a) (i.e., accepts a pointer to an array of items *a) how do you think we can do this?

Solution:

void f(int *a); 
vector v;
f(&v[0]);

Explanation:

Take advantage of vectors being arrays, and pass a pointer to the beginning of the underlying array to the function:

Deques

The std::deque templates a double-ended queue with a similar interface to vectors but efficiently inserts and deletes at the front and back of the data structure. The push_back() and pop_back(), along with most other std::vector operations are also available for deques; also, std::deque offer push_front() and pop_front().

💡  Deques are not guaranteed to be implemented internally as contiguous arrays.

Stacks

The std::stack template is not a separate data structure. It is an adapter template— a specialized interface to an existing template.

By default, std::stack is implemented with std::deque, but one can specify to use a std::vectoror std::list.

💡  The pop method does not return the item that was popped. If you want this item, use the top method before the pop method.

Stacks provide the bare-bone stack operations:

stack s; if (!s.empty()) { 
// Test if empty
std::cout << s.size() << std::endl; // Size of the stack
}
s.push(4); // “push” operation
std::cout << s.top() << std::endl; // top of stack
s.pop(); // “pop” operation

Lists and forward lists

The linked-list-based containers, std::forward_list and std::list differ in a few critical ways. First, the formers hold only a link to the next element, while the latter has two connections to relate to the previous component. Two links iterate the list efficiently in either direction, which comes with additional memory costs and a slight overhead in time when inserting and removing elements. forward_list objects are thus more efficient than list objects, although they only iterate forward.

Compared to other base standard sequence containers (array, vector, and deque), forward_list triumphs in inserting, extracting, and moving elements to arbitrary positions in the container. As we will cover in the next part of this series, algorithms often use these advantages (e.g., sorting algorithms).

Demo Code

Let us use different sequential containers to store the values of the rolling die. We will then view the memory address of all values to analyze the times and tendencies of different containers in memory allocation.

Notice that vectors are quickest when memory is already allocated, but slowest when a new allocation needs to be done due to running out of space (i.e., see the summary at the end of the video).

1*9 bB46c5W5 Im6RIrZ Rvg
Vectors. Note the memory remains contiguous, for all elements move when additional space is needed. Watch the original video here.
1*Z03aX3jN2MKmcdvTjUYbgQ
Deque. Watch the original video here.
1*jJ9I 5KZIDdwdpRs5fQ6fA
Forward_list. Watch the original video here.
List. Watch the original video here.

STL containers have an optional argument (i.e., Allocator()) which allows for the control of memory (i.e., management). Debby Nirwan does an excellent job covering this topic.

Abhishek Rathore blogs a practical guide spanning all components of STL.

Priyansh Khodiyar takes a practical view of data structures and algorithms from a general perspective (i.e., not STL-specific).

TK_ provides a visual guide in vector containers. (Note to TK_, and unsure if intentional, lol, but, without the _, your tag is processed as a TK_Note lol).

Mike McMillan does a deep dive into STL vector.

Along with map and multimap.

Aditya Jain demonstrates the usage of STL containers to implement tree and graph structures.

Scott Meyer’s Effective STL highly inspired this blog. Vanand Gasparyan reviews the book quite nicely.



News Credit

%d bloggers like this: