Lesson 16-C++ Standard Template Library STL

STL is part of C++ and includes a series of reusable components, such as containers, algorithms, iterators, etc. These components are designed following the principles of generic programming, making them widely applicable to different types of data.

Containers

Sequential Containers

  • vector: Dynamic array, supports random access.
  • deque: Double-ended queue, supports fast insertion and deletion at both ends.
  • list: Doubly linked list, supports fast insertion and deletion at any position.

Using vector

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Add elements
    numbers.push_back(6);
    numbers.insert(numbers.begin(), 0);

    // Remove elements
    numbers.pop_back();
    numbers.erase(numbers.begin());

    // Access elements
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Advanced usage of std::vector

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};

    // Use reserve to pre-allocate memory
    v.reserve(10);

    // Use emplace_back to construct elements directly in the container
    v.emplace_back(6);

    // Use at to access elements
    std::cout << "Element at index 3: " << v.at(3) << std::endl;

    // Traverse using begin and end
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::deque

  • Double-ended queue: Efficient insertion and deletion at both ends.
  • Member functions: push_front, pop_front, push_back, pop_back.

Example code: Using std::deque

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d = {1, 2, 3, 4, 5};

    // Add element at the front
    d.push_front(0);

    // Add element at the back
    d.push_back(6);

    // Traverse using begin and end
    for (auto it = d.begin(); it != d.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::list

  • Doubly linked list: Suitable for frequent insertions and deletions.
  • Member functions: push_front, pop_front, push_back, pop_back, splice.

Example code: Using std::list

#include <iostream>
#include <list>

int main() {
    std::list<int> l = {1, 2, 3, 4, 5};

    // Add element at the front
    l.push_front(0);

    // Add element at the back
    l.push_back(6);

    // Use splice to move elements
    auto it = l.begin();
    std::advance(it, 2);  // Move to the third element
    std::list<int>::iterator pos = l.begin();
    l.splice(pos, l, it);

    // Traverse using begin and end
    for (auto it = l.begin(); it != l.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Associative Containers

  • set: Sorted collection, no duplicate elements allowed.
  • map: Sorted key-value mapping, keys cannot be duplicated.
  • multiset: Sorted collection, duplicate elements allowed.
  • multimap: Sorted key-value mapping, keys can be duplicated.

Example code: Using map

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> scores = {
        {"Alice", 100},
        {"Bob", 90},
        {"Charlie", 80}
    };

    // Insert element
    scores["David"] = 95;

    // Update element
    scores["Alice"] = 105;

    // Access elements
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << std::endl;
    }

    return 0;
}

std::set

  • Ordered collection: Implemented using a red-black tree.
  • Member functions: insert, erase, find, count.

Example code: Using std::set

#include <iostream>
#include <set>

int main() {
    std::set<int> s = {1, 2, 3, 4, 5};

    // Insert new element
    s.insert(6);

    // Find element
    auto it = s.find(4);
    if (it != s.end()) {
        std::cout << "Found element: " << *it << std::endl;
    }

    // Traverse using begin and end
    for (const auto& elem : s) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Container Adapters

  • stack: Stack, last in, first out.
  • queue: Queue, first in, first out.
  • priority_queue: Priority queue, sorted by priority.

Example code: Using priority_queue

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    // Add elements
    pq.push(10);
    pq.push(5);
    pq.push(20);

    // Access elements
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

Iterators

Iterators are objects in STL used to traverse container elements. They support different operations such as moving, comparing, and dereferencing.

Example code: Using iterators to traverse vector

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Traverse container
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Algorithms

Algorithms are functions in STL used to process container elements. They can be used for sorting, searching, transforming, etc.

Non-modifying Sequence Operations

  • for_each: Applies a function to each element in the sequence.
  • copy: Copies a sequence.

Example code: Using for_each

#include <iostream>
#include <vector>
#include <algorithm>

void print(int x) {
    std::cout << x << " ";
}

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Traverse container
    std::for_each(numbers.begin(), numbers.end(), print);
    std::cout << std::endl;

    return 0;
}

Modifying Sequence Operations

  • sort: Sorts.
  • reverse: Reverses the sequence.
  • fill: Fills the sequence.

Example code: Using sort

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 3, 1, 4, 2};

    // Sort container
    std::sort(numbers.begin(), numbers.end());

    // Output sorted result
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Replacement Operations

  • replace: Replaces elements.

Example code: Using replace

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {1, 2, 3, 2, 4, 2};

    // Replace elements
    std::replace(numbers.begin(), numbers.end(), 2, 10);

    // Output replaced result
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Removal Operations

  • remove: Removes elements.
  • unique: Removes duplicate elements.

Example code: Using remove

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {1, 2, 3, 2, 4, 2};

    // Remove elements
    numbers.erase(std::remove(numbers.begin(), numbers.end(), 2), numbers.end());

    // Output removed result
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Search Operations

  • find: Finds an element.
  • find_if: Finds an element using a predicate.

Example code: Using find_if

#include <iostream>
#include <vector>
#include <algorithm>

bool is_even(int x) {
    return x % 2 == 0;
}

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Find element
    auto it = std::find_if(numbers.begin(), numbers.end(), is_even);

    if (it != numbers.end()) {
        std::cout << "Found even number: " << *it << std::endl;
    } else {
        std::cout << "No even number found." << std::endl;
    }

    return 0;
}

Partition Operations

  • partition: Partitions the sequence.

Example code: Using partition

#include <iostream>
#include <vector>
#include <algorithm>

bool is_odd(int x) {
    return x % 2 != 0;
}

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Partition sequence
    auto it = std::partition(numbers.begin(), numbers.end(), is_odd);

    // Output partitioned result
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Sorting Operations

  • stable_sort: Stable sort.
  • partial_sort: Partial sort.

Example code: Using stable_sort

#include <iostream>
#include <vector>
#include <algorithm>

struct Person {
    std::string name;
    int age;

    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 25},
        {"David", 35}
    };

    // Stable sort
    std::stable_sort(people.begin(), people.end());

    // Output sorted result
    for (const auto& person : people) {
        std::cout << person.name << ": " << person.age << std::endl;
    }

    return 0;
}

Example code: Using partial_sort

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 3, 1, 4, 2};

    // Partially sort the first three elements
    std::partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end());

    // Output partially sorted result
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Merge Operations

  • merge: Merges two sorted sequences.

Example code: Using merge

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec1 = {1, 3, 5};
    std::vector<int> vec2 = {2, 4, 6};
    std::vector<int> result(vec1.size() + vec2.size());

    // Merge two sorted sequences
    std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

    // Output merged result
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Transform Operations

  • transform: Transforms a sequence.

Example code: Using transform

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    std::vector<int> vec1 = {1, 2, 3};
    std::vector<int> vec2 = {4, 5, 6};
    std::vector<int> result(vec1.size());

    // Transform two sequences using addition
    std::transform(vec1.begin(), vec1.end(), vec2.begin(), result.begin(), std::plus<int>());

    // Output transformed result
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Function Objects

A function object is an object that can be called like a function. STL provides various predefined function objects, such as plus, minus, etc.

Example code: Using plus

#include <iostream>
#include <functional>

int main() {
    std::plus<int> adder;

    int a = 5;
    int b = 3;
    int sum = adder(a, b);

    std::cout << "Sum: " << sum << std::endl;

    return 0;
}

Advanced Topics

Generic Programming

  • Template metaprogramming
  • SFINAE (Substitution Failure Is Not An Error)

Example code: Using template metaprogramming

#include <iostream>
#include <type_traits>

template<typename T>
struct IsInteger {
    static constexpr bool value = std::is_integral<T>::value;
};

template<typename T>
void printType() {
    if (IsInteger<T>::value) {
        std::cout << "Type is an integer." << std::endl;
    } else {
        std::cout << "Type is not an integer." << std::endl;
    }
}

int main() {
    printType<int>();  // Output "Type is an integer."
    printType<double>();  // Output "Type is not an integer."

    return 0;
}

Adapters

  • Container adapters
  • Iterator adapters

Example code: Using iterator adapter

#include <iostream>
#include <vector>
#include <iterator>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Use reverse iterator adapter
    for (auto rit = numbers.rbegin(); rit != numbers.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    return 0;
}

Allocators

  • allocator: Default allocator
  • Custom allocators

Example code: Using allocator

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers(10);  // Create vector using default allocator

    // Get allocator
    std::allocator<int> alloc = numbers.get_allocator();

    // Allocate memory using allocator
    int* data = alloc.allocate(5);

    // Initialize data
    for (int i = 0; i < 5; ++i) {
        alloc.construct(&data[i], i);
    }

    // Output data
    for (int i = 0; i < 5; ++i) {
        std::cout << data[i] << " ";
    }
    std::cout << std::endl;

    // Destroy data
    for (int i = 0; i < 5; ++i) {
        alloc.destroy(&data[i]);
    }

    // Deallocate memory
    alloc.deallocate(data, 5);

    return 0;
}

Practical Applications

Efficient Algorithm Design

  • Algorithm complexity analysis
  • Algorithm optimization techniques

Example code: Using binary search

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 7;

    // Use binary search
    auto it = std::lower_bound(numbers.begin(), numbers.end(), target);

    if (it != numbers.end() && *it == target) {
        std::cout << "Found at index: " << std::distance(numbers.begin(), it) << std::endl;
    } else {
        std::cout << "Not found." << std::endl;
    }

    return 0;
}

Container Selection and Usage

  • Performance comparison
  • Choosing the right data structure

Example code: Comparing performance of vector and list

#include <iostream>
#include <vector>
#include <list>
#include <chrono>

int main() {
    const int N = 1000000;

    // Test vector
    {
        std::vector<int> vec;
        auto start = std::chrono::high_resolution_clock::now();

        for (int i = 0; i < N; ++i) {
            vec.push_back(i);
        }

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
        std::cout << "Vector time: " << duration << " ms" << std::endl;
    }

    // Test list
    {
        std::list<int> lst;
        auto start = std::chrono::high_resolution_clock::now();

        for (int i = 0; i < N; ++i) {
            lst.push_back(i);
        }

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
        std::cout << "List time: " << duration << " ms" << std::endl;
    }

    return 0;
}

Comprehensive Exercises

Writing Your Own Container

Design and implement a simple container

Example code: Implementing a simple stack

#include <iostream>
#include <vector>

template<typename T>
class SimpleStack {
public:
    void push(const T& item) {
        data.push_back(item);
    }

    T pop() {
        if (empty()) {
            throw std::runtime_error("Stack is empty.");
        }
        T topItem = data.back();
        data.pop_back();
        return topItem;
    }

    bool empty() const {
        return data.empty();
    }

private:
    std::vector<T> data;
};

int main() {
    SimpleStack<int> stack;

    stack.push(1);
    stack.push(2);
    stack.push(3);

    while (!stack.empty()) {
        std::cout << stack.pop() << " ";
    }
    std::cout << std::endl;

    return 0;
}

Best Practices

Code Style and Naming Conventions

  • Use clear and meaningful variable names
  • Avoid using single letters as variable names unless they have clear meaning

Example code: Following coding standards

#include <iostream>
#include <vector>

// Use clear naming
void print_vector(const std::vector<int>& numbers) {
    for (int number : numbers) {
        std::cout << number << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> sample_numbers = {1, 2, 3, 4, 5};
    print_vector(sample_numbers);

    return 0;
}

Code Refactoring

  • Regularly refactor code to improve readability and maintainability
  • Avoid duplicate code

Example code: Refactoring duplicate code

#include <iostream>
#include <vector>

void process_numbers(const std::vector<int>& numbers, int threshold) {
    for (int number : numbers) {
        if (number > threshold) {
            std::cout << "Number " << number << " is greater than " << threshold << std::endl;
        }
    }
}

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    int threshold = 3;

    process_numbers(numbers, threshold);

    return 0;
}

Performance Optimization

Memory Management

  • Reduce unnecessary memory allocation and deallocation
  • Use caching mechanisms

Example code: Reducing memory allocation

#include <iostream>
#include <vector>

void process_data(const std::vector<int>& data) {
    // Process data...
}

int main() {
    std::vector<int> data;
    data.reserve(10000);  // Pre-allocate memory

    for (int i = 0; i < 10000; ++i) {
        data.push_back(i);
    }

    process_data(data);

    return 0;
}

Parallel Processing

  • Use multithreading or parallel libraries for parallel processing
  • Consider using OpenMP or the <thread> library in C++11 standard

Example code: Using C++11 <thread> for parallel processing

#include <iostream>
#include <vector>
#include <thread>

void process_chunk(const std::vector<int>& chunk) {
    for (int i : chunk) {
        // Process data...
    }
}

int main() {
    std::vector<int> data(1000000);
    for (size_t i = 0; i < data.size(); ++i) {
        data[i] = i;
    }

    const size_t chunk_size = 10000;
    const size_t num_threads = 10;

    std::vector<std::thread> threads;
    for (size_t i = 0; i < num_threads; ++i) {
        size_t start = i * chunk_size;
        size_t end = (i + 1) * chunk_size;
        threads.emplace_back(process_chunk, std::vector<int>(data.begin() + start, data.begin() + end));
    }

    for (auto& t : threads) {
        t.join();
    }

    return 0;
}
Share your love