Introduction to Standard Template Library (STL)

The Standard Template Library (STL) is a powerful set of C++ template classes to provide general-purpose classes and functions with templates that implement many popular and commonly used algorithms and data structures like vectors, lists, queues, and stacks.

What is STL?

The Standard Template Library (STL) is a software library for the C++ programming language that provides four components:

1. Containers: Objects that store data
2. Algorithms: Methods for processing data
3. Iterators: Objects that behave like pointers to connect algorithms with containers
4. Function Objects (Functors): Objects that act like functions

The STL was designed to be efficient, reusable, and extensible. It allows you to focus on your application logic instead of reinventing common data structures and algorithms.

Why Use STL?

There are several advantages to using the STL:

1. Reusability: The STL provides implementations of common data structures and algorithms, so you don’t have to write them yourself.
2. Efficiency: STL implementations are optimized for performance.
3. Type Safety: STL is implemented using templates, ensuring type safety at compile time.
4. Standardization: The STL is part of the C++ standard library, so it’s available on all platforms that support C++.
5. Less Code: Using the STL can significantly reduce the amount of code you need to write and maintain.

Components of STL

1. Containers

Containers are objects that store data of specified types. They are implemented as class templates, which allows a great flexibility in the types supported as elements.

The STL includes the following containers:

Sequence Containers:

• Vector: Dynamic array that can resize itself automatically
• List: Doubly-linked list
• Deque: Double-ended queue
• Forward List (since C++11): Singly-linked list
• Array (since C++11): Static array with fixed size

Associative Containers:

• Set: Collection of unique keys, sorted by keys
• Map: Collection of key-value pairs, sorted by keys
• Multiset: Collection of keys, sorted by keys (allows duplicates)
• Multimap: Collection of key-value pairs, sorted by keys (allows duplicates)

Unordered Associative Containers (since C++11):

• Unordered Set: Collection of unique keys, hashed by keys
• Unordered Map: Collection of key-value pairs, hashed by keys
• Unordered Multiset: Collection of keys, hashed by keys (allows duplicates)
• Unordered Multimap: Collection of key-value pairs, hashed by keys (allows duplicates)

Container Adapters:

• Stack: LIFO (Last-In-First-Out) data structure
• Queue: FIFO (First-In-First-Out) data structure
• Priority Queue: Queue that maintains elements in a specific order

2. Algorithms

Algorithms are functions that operate on ranges of elements. They are implemented as function templates and can work with different types of containers.

The STL includes algorithms for:

• Searching (e.g., find, binary_search)
• Sorting (e.g., sort, merge, partial_sort)
• Modifying sequences (e.g., copy, move, transform)
• Numeric operations (e.g., accumulate, inner_product)

3. Iterators

Iterators are objects that behave like pointers. They are used to traverse the elements of a container. Iterators provide a common interface for algorithms to work with different containers.

The STL defines five categories of iterators:

• Input Iterator: Can read forward (e.g., istream_iterator)
• Output Iterator: Can write forward (e.g., ostream_iterator)
• Forward Iterator: Can read and write forward
• Bidirectional Iterator: Can read and write forward and backward (e.g., list iterators)
• Random Access Iterator: Can read and write with random access (e.g., vector iterators)

4. Function Objects (Functors)

Function objects, also known as functors, are objects that can be called as if they were functions. They are implemented as classes with an operator() method.

The STL includes predefined functors for:

• Arithmetic operations (e.g., plus, minus, multiplies)
• Comparison operations (e.g., equal_to, less, greater)
• Logical operations (e.g., logical_and, logical_or, logical_not)

Basic Example of STL Usage

Here’s a simple example that demonstrates the use of STL containers, iterators, and algorithms:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // Create a vector container
    vector<int> numbers = {5, 2, 9, 1, 7, 3};
    
    // Sort the vector using an STL algorithm
    sort(numbers.begin(), numbers.end());
    
    // Print the sorted vector using iterators
    cout << "Sorted numbers: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // Find a number using an STL algorithm
    auto it = find(numbers.begin(), numbers.end(), 7);
    if (it != numbers.end()) {
        cout << "Found 7 at position: " << (it - numbers.begin()) << endl;
    } else {
        cout << "7 not found" << endl;
    }
    
    return 0;
}

Output:

Sorted numbers: 1 2 3 5 7 9
Found 7 at position: 4

Overview of STL Containers

Vector

Vectors are sequence containers representing arrays that can change in size. They provide random access to elements, dynamic size, and efficient insertion at the end.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // Create a vector
    vector<int> vec;
    
    // Add elements
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    
    // Access elements
    cout << "vec[1] = " << vec[1] << endl;
    
    // Iterate through the vector
    cout << "Vector elements: ";
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;
    
    // Vector size
    cout << "Size: " << vec.size() << endl;
    
    return 0;
}

Output:

vec[1] = 20
Vector elements: 10 20 30
Size: 3

List

Lists are sequence containers that allow constant time insertion and removal of elements from anywhere in the container. They are implemented as doubly-linked lists.

#include <iostream>
#include <list>
using namespace std;

int main() {
    // Create a list
    list<int> myList;
    
    // Add elements
    myList.push_back(10);   // Add to the end
    myList.push_front(5);   // Add to the beginning
    myList.push_back(15);
    
    // Iterate through the list
    cout << "List elements: ";
    for (int num : myList) {
        cout << num << " ";
    }
    cout << endl;
    
    // Insert an element in the middle
    auto it = myList.begin();
    advance(it, 1);  // Move to the second element
    myList.insert(it, 7);
    
    cout << "After insertion: ";
    for (int num : myList) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

Output:

List elements: 5 10 15
After insertion: 5 7 10 15

Map

Maps are associative containers that store elements formed by a combination of a key and a mapped value. They are implemented as balanced binary search trees.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    // Create a map (string -> int)
    map<string, int> ages;
    
    // Insert elements
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;
    
    // Access elements
    cout << "Bob's age: " << ages["Bob"] << endl;
    
    // Check if a key exists
    if (ages.find("David") == ages.end()) {
        cout << "David not found" << endl;
    }
    
    // Iterate through the map
    cout << "All ages:" << endl;
    for (const auto& pair : ages) {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    return 0;
}

Output:

Bob's age: 25
David not found
All ages:
Alice: 30
Bob: 25
Charlie: 35

Set

Sets are associative containers that store unique elements in a specific order. They are implemented as balanced binary search trees.

#include <iostream>
#include <set>
using namespace std;

int main() {
    // Create a set
    set<int> numbers;
    
    // Insert elements
    numbers.insert(5);
    numbers.insert(3);
    numbers.insert(8);
    numbers.insert(3);  // Duplicate, will be ignored
    
    // Check size
    cout << "Set size: " << numbers.size() << endl;
    
    // Check if an element exists
    if (numbers.find(5) != numbers.end()) {
        cout << "5 is in the set" << endl;
    }
    
    // Iterate through the set
    cout << "Set elements: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

Output:

Set size: 3
5 is in the set
Set elements: 3 5 8

Overview of STL Algorithms

STL provides a rich set of algorithms that can be used with containers through iterators. Here are some common algorithms:

Sorting and Searching

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec = {5, 2, 8, 1, 9, 3};
    
    // Sort
    sort(vec.begin(), vec.end());
    
    cout << "Sorted vector: ";
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;
    
    // Binary search (works on sorted containers)
    bool found = binary_search(vec.begin(), vec.end(), 8);
    cout << "8 is " << (found ? "found" : "not found") << endl;
    
    // Find
    auto it = find(vec.begin(), vec.end(), 9);
    if (it != vec.end()) {
        cout << "Found 9 at position: " << (it - vec.begin()) << endl;
    }
    
    return 0;
}

Output:

Sorted vector: 1 2 3 5 8 9
8 is found
Found 9 at position: 5

Modifying Sequences

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec1 = {1, 2, 3, 4, 5};
    vector<int> vec2(5);  // Create with 5 elements
    
    // Copy
    copy(vec1.begin(), vec1.end(), vec2.begin());
    
    // Transform (multiply each element by 2)
    transform(vec2.begin(), vec2.end(), vec2.begin(), 
              [](int x) { return x * 2; });
    
    cout << "Transformed vector: ";
    for (int num : vec2) {
        cout << num << " ";
    }
    cout << endl;
    
    // Replace
    replace(vec1.begin(), vec1.end(), 3, 30);
    
    cout << "After replace: ";
    for (int num : vec1) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

Output:

Transformed vector: 2 4 6 8 10
After replace: 1 2 30 4 5

Numeric Operations

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5};
    
    // Sum
    int sum = accumulate(vec.begin(), vec.end(), 0);
    cout << "Sum: " << sum << endl;
    
    // Product
    int product = accumulate(vec.begin(), vec.end(), 1, 
                             multiplies<int>());
    cout << "Product: " << product << endl;
    
    // Running total
    vector<int> runningTotal(5);
    partial_sum(vec.begin(), vec.end(), runningTotal.begin());
    
    cout << "Running total: ";
    for (int num : runningTotal) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

Output:

Sum: 15
Product: 120
Running total: 1 3 6 10 15

Benefits of Learning STL

1. Productivity: STL allows you to write less code while accomplishing more.
2. Readability: STL code is often more concise and easier to understand.
3. Reliability: STL components are well-tested and reliable.
4. Performance: STL implementations are optimized for efficiency.
5. Industry Standard: STL is widely used in industry, making it an essential skill.

Best Practices for Using STL

1. Use STL algorithms instead of hand-written loops when possible.
2. Choose the right container for your specific needs:
   • Use vector for most sequences that require random access.
   • Use list when you need frequent insertions/deletions in the middle.
   • Use map or unordered_map for key-value pairs.
   • Use set or unordered_set for unique collections of items.
3. Use range-based for loops for cleaner iteration.
4. Be aware of the complexity of different operations on different containers.
5. Use STL iterators with algorithms for maximum flexibility.

Summary

The Standard Template Library (STL) is a powerful part of the C++ standard library that provides generic containers, algorithms, iterators, and function objects. It enables you to write more efficient, reusable, and maintainable code by leveraging well-tested implementations of common data structures and algorithms.

Understanding the STL is essential for any C++ programmer, as it helps you solve common programming problems quickly and efficiently without having to reinvent the wheel.