Introduction to STL & Containers

The Standard Template Library (STL) is a powerful component of the C++ Standard Library that provides a collection of generic classes and functions. It simplifies programming by offering reusable components, which can be used to implement common data structures and algorithms efficiently. Understanding STL is crucial for any serious C++ programmer as it can significantly reduce development time and improve code quality.

In this tutorial, we will explore the core components of STL, particularly focusing on containers. We'll discuss different types of containers, their characteristics, and when to use each one. By the end of this tutorial, you should have a solid understanding of how to leverage STL containers in your C++ programs.

Core Content

What is STL?

The Standard Template Library (STL) is a set of templates classes and functions that implement common data structures and algorithms. It provides a high-level abstraction for programming, allowing developers to write more generic and reusable code.

Components Overview

STL is divided into three main components:

1. Containers: These are objects that store data. They provide a way to manage collections of elements.
2. Algorithms: These are functions that operate on containers. They perform operations like sorting, searching, and transforming data.
3. Iterators: These are objects that allow traversal through the elements in containers.

Container Categories

STL provides several types of containers, each suited for different use cases:

1. Sequence Containers:

   • std::vector: Dynamic array that can grow or shrink in size.
   • std::list: Doubly linked list that allows fast insertion and deletion at any position.
   • std::deque: Double-ended queue that allows fast insertion and deletion from both ends.

2. Associative Containers:

   • std::set: Sorted set of unique elements.
   • std::map: Sorted key-value pairs where keys are unique.
   • std::multiset: Sorted set of non-unique elements.
   • std::multimap: Sorted key-value pairs where keys can be non-unique.

3. Unordered Associative Containers:

   • std::unordered_set: Unsorted set of unique elements with fast average-time complexity for insertions and lookups.
   • std::unordered_map: Unsorted key-value pairs where keys are unique, with fast average-time complexity.
   • std::unordered_multiset: Unsorted set of non-unique elements.
   • std::unordered_multimap: Unsorted key-value pairs where keys can be non-unique.

When to Use Which Container

Choosing the right container is crucial for optimizing your program. Here are some guidelines:

• Use std::vector when you need a dynamic array with fast random access and moderate insertion/deletion at the end.
• Use std::list when frequent insertions and deletions are required, especially at positions other than the end.
• Use std::deque when you need efficient insertion and deletion from both ends.
• Use std::set or std::map when you need a collection of unique elements that are automatically sorted.
• Use std::unordered_set or std::unordered_map when you need fast average-time complexity for insertions and lookups, with no guarantee of order.

Practical Example

Let's create a simple program that demonstrates the use of different containers. This program will store a list of integers in each container type and print them out.

1#include <iostream>
2#include <vector>
3#include <list>
4#include <deque>
5#include <set>
6#include <map>
7#include <unordered_set>
8#include <unordered_map>
9 
10int main() {
11  // Vector example
12  std::vector<int> vec = {1, 2, 3, 4, 5};
13  std::cout << "Vector: ";
14  for (const auto& elem : vec) {
15      std::cout << elem << " ";
16  }
17  std::cout << std::endl;
18 
19  // List example
20  std::list<int> lst = {1, 2, 3, 4, 5};
21  std::cout << "List: ";
22  for (const auto& elem : lst) {
23      std::cout << elem << " ";
24  }
25  std::cout << std::endl;
26 
27  // Deque example
28  std::deque<int> deq = {1, 2, 3, 4, 5};
29  std::cout << "Deque: ";
30  for (const auto& elem : deq) {
31      std::cout << elem << " ";
32  }
33  std::cout << std::endl;
34 
35  // Set example
36  std::set<int> st = {1, 2, 3, 4, 5};
37  std::cout << "Set: ";
38  for (const auto& elem : st) {
39      std::cout << elem << " ";
40  }
41  std::cout << std::endl;
42 
43  // Map example
44  std::map<int, std::string> mp;
45  mp[1] = "One";
46  mp[2] = "Two";
47  mp[3] = "Three";
48  mp[4] = "Four";
49  mp[5] = "Five";
50  std::cout << "Map: ";
51  for (const auto& elem : mp) {
52      std::cout << elem.first << ":" << elem.second << " ";
53  }
54  std::cout << std::endl;
55 
56  // Unordered Set example
57  std::unordered_set<int> ust = {1, 2, 3, 4, 5};
58  std::cout << "Unordered Set: ";
59  for (const auto& elem : ust) {
60      std::cout << elem << " ";
61  }
62  std::cout << std::endl;
63 
64  // Unordered Map example
65  std::unordered_map<int, std::string> ump;
66  ump[1] = "One";
67  ump[2] = "Two";
68  ump[3] = "Three";
69  ump[4] = "Four";
70  ump[5] = "Five";
71  std::cout << "Unordered Map: ";
72  for (const auto& elem : ump) {
73      std::cout << elem.first << ":" << elem.second << " ";
74  }
75  std::cout << std::endl;
76 
77  return 0;
78}

Output

Vector: 1 2 3 4 5 
List: 1 2 3 4 5 
Deque: 1 2 3 4 5 
Set: 1 2 3 4 5 
Map: 1:One 2:Two 3:Three 4:Four 5:Five 
Unordered Set: 5 4 3 2 1 
Unordered Map: 5:Five 4:Four 3:Three 2:Two 1:One

Explanation

• Vector: The elements are stored in a contiguous block of memory, allowing for fast random access.
• List: The elements are stored in nodes connected by pointers, allowing for efficient insertion and deletion at any position.
• Deque: The elements are stored in multiple blocks of memory, allowing for fast insertion and deletion from both ends.
• Set: The elements are stored in a balanced tree structure (usually a red-black tree), ensuring that the elements are always sorted.
• Map: Similar to std::set, but each element is a key-value pair. The keys are unique and sorted.
• Unordered Set: The elements are stored in hash buckets, allowing for fast average-time complexity for insertions and lookups.
• Unordered Map: Similar to std::unordered_set, but each element is a key-value pair. The keys are unique.

Summary

What's Next?

In the next tutorial, we will delve deeper into one of the sequence containers: std::array. We'll explore its features, use cases, and how it compares to other containers. Stay tuned!