Module 6 Templates and the Standard Template Library (STL)

—

by

admin
in

Function Templates (STL)

Module Overview:

In this module, we will explore Function Templates, a key feature in C++ that allows the creation of generic functions. Templates enable writing functions that work with any data type, improving code reusability and flexibility. We will also see how STL (Standard Template Library) takes advantage of function templates to provide a collection of powerful, reusable algorithms and data structures.

1. Introduction to Function Templates

  • Definition: A function template allows you to write a function that can operate on any data type. The function is defined with a generic type, and when the function is called, the compiler generates the code for the specific data type you pass as arguments.

Syntax: Function templates are defined using the template keyword followed by one or more type parameters in angle brackets. For example:

cpp
CopyEdit
template <typename T>

T add(T a, T b) {

return a + b;

}

  • In this example, T is a placeholder for a data type, and the function add can work with any data type that supports the +
  • Why Use Function Templates?
    • Code Reusability: You can write a function that can work with any data type, eliminating the need to write multiple overloaded functions for each type.
    • Type Safety: The compiler ensures that the correct data types are used with function templates, providing compile-time type checking.
    • Generic Programming: Function templates are a fundamental aspect of generic programming, where algorithms and data structures are written without being tied to specific types.

2. Function Template Example

Basic Example: Let’s define a simple function template that adds two values:

cpp
CopyEdit
#include <iostream>

using namespace std;

 

// Function template to add two values

template <typename T>

T add(T a, T b) {

return a + b;

}

 

int main() {

cout << “Sum of 3 and 4 (int): ” << add(3, 4) << endl;

cout << “Sum of 3.5 and 4.5 (double): ” << add(3.5, 4.5) << endl;

cout << “Sum of ‘a’ and ‘b’ (char): ” << add(‘a’, ‘b’) << endl;

return 0;

}

Output:
arduino
CopyEdit
Sum of 3 and 4 (int): 7

Sum of 3.5 and 4.5 (double): 8

Sum of ‘a’ and ‘b’ (char): 195

  • Explanation:
    • In the above example, the function add is defined as a template that can add two values of any type. When the function is called with integers, doubles, or characters, the appropriate version of the function is instantiated by the compiler. This demonstrates the flexibility of function templates.

3. Template Specialization

  • Definition: Template specialization allows you to define a specific version of a template function for a particular data type. This is useful when the generic version of the function does not work as expected for a certain data type, or you need to implement a specialized behavior.

Syntax: Specialization is done by providing a function definition for a specific type:

cpp
CopyEdit
template <typename T>

T multiply(T a, T b) {

return a * b;

}

 

// Template specialization for char type

template <>

char multiply(char a, char b) {

return a; // Special behavior for char type

}

Example of Specialization:

cpp
CopyEdit
#include <iostream>

using namespace std;

 

// Generic template for multiply

template <typename T>

T multiply(T a, T b) {

return a * b;

}

 

// Specialization for char type

template <>

char multiply(char a, char b) {

return a; // Special behavior for char type

}

 

int main() {

cout << “Multiply 3 and 4 (int): ” << multiply(3, 4) << endl;

cout << “Multiply 3.5 and 4.5 (double): ” << multiply(3.5, 4.5) << endl;

cout << “Multiply ‘a’ and ‘b’ (char): ” << multiply(‘a’, ‘b’) << endl;

return 0;

}

Output:
arduino
CopyEdit
Multiply 3 and 4 (int): 12

Multiply 3.5 and 4.5 (double): 15.75

Multiply ‘a’ and ‘b’ (char): a

  • Explanation:
    • In this case, the template function multiply is specialized for the char type to return only the first character instead of performing multiplication. This allows for custom behavior when the type is char, while still using the generic template for other types.

4. Template Functions with Multiple Parameters

Function Templates with Multiple Types: Function templates can also be written to accept multiple type parameters. Here’s an example of a template function that takes two parameters of different types:

cpp
CopyEdit
template <typename T, typename U>

auto add(T a, U b) -> decltype(a + b) {

return a + b;

}

 

int main() {

cout << “Sum of 3 and 4.5 (int + double): ” << add(3, 4.5) << endl;

cout << “Sum of ‘a’ and 5 (char + int): ” << add(‘a’, 5) << endl;

return 0;

}

Output:

arduino
CopyEdit
Sum of 3 and 4.5 (int + double): 7.5

Sum of ‘a’ and 5 (char + int): 102

  • Explanation:
    • In this example, the add function template takes two parameters of different types (T and U). The return type is deduced using the decltype keyword, which automatically determines the resulting type of the operation a + b.

5. Function Template and STL (Standard Template Library)

  • STL and Function Templates: The Standard Template Library (STL) in C++ is a powerful collection of generic classes and functions. It heavily relies on function templates to create reusable and efficient algorithms and data structures, such as vector, list, map, and algorithms like sort and find.

Example: Using std::sort (Function Template from STL):

cpp
CopyEdit
#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int main() {

vector<int> nums = {5, 1, 4, 3, 2};

sort(nums.begin(), nums.end());  // sort is a function template

 

for (int num : nums) {

cout << num << ” “;

}

return 0;

}

Output:
CopyEdit
1 2 3 4 5

  • Explanation:
    • The sort function is a template function in the STL that sorts a range of elements, here a vector of integers. Since it is a template, it works for any container type (e.g., vector<int>, vector<double>, etc.), making it highly reusable.

6. Best Practices for Function Templates

  • Use const where applicable: Always use const for function arguments that shouldn’t be modified to avoid unexpected side effects.
  • Avoid unnecessary template specialization: Use template specialization only when you need to implement custom behavior for specific types.
  • Keep template functions simple and efficient: Since templates generate code at compile-time, make sure your function templates are simple and do not lead to unnecessary code bloat.

7. Exercises and Hands-On Practice

  • Exercise 1: Implement a function template findMax that returns the largest of two numbers. Test it with different types (int, float, double).
  • Exercise 2: Write a function template that swaps two values of any data type.
  • Exercise 3: Create a template function to find the average of an array of elements.
  • Exercise 4: Use std::find to search for an element in a container and print the result.

8. Conclusion and Summary

  • Function templates provide a powerful way to write reusable, type-independent functions in C++. They allow for generic programming and help reduce code duplication.
  • The Standard Template Library (STL) leverages function templates to offer a rich set of algorithms and data structures that can be used with different types.
  • Mastering function templates and understanding their usage in the STL will significantly improve the efficiency and maintainability of your code.

Assessment and Quizzes

  • Quiz 1: Multiple-choice questions to test the understanding of function templates.
  • Quiz 2: Practical exercises where students write function templates and apply them to real-world problems.

 

 

Class Templates (STL)

Module Overview:

In this module, we will explore Class Templates in C++. Class templates allow us to define classes that work with any data type, enabling the creation of generic, reusable, and flexible classes. We’ll also see how STL (Standard Template Library) leverages class templates to provide powerful, generic data structures, such as vectors, lists, and maps. By mastering class templates, you can write highly reusable code and design your own data structures and algorithms that can work with any data type.

1. Introduction to Class Templates

  • Definition: A class template is a blueprint for creating classes that can handle any data type. Just like function templates, class templates allow you to write a single class definition that works with any data type. When you create an instance of a class template, the compiler generates the code for that specific data type.

Syntax: The syntax for defining a class template is similar to function templates but with the class keyword:

cpp
CopyEdit
template <typename T>

class Box {

private:

T value;

public:

void setValue(T v) { value = v; }

T getValue() { return value; }

};

  • Why Use Class Templates?
    • Code Reusability: One class template can be used for different data types, eliminating the need to write separate classes for each type.
    • Type Safety: The compiler ensures that only the appropriate data types are used, providing type checking at compile time.
    • Generic Programming: Class templates are the foundation for generic programming, where algorithms and data structures are designed to work with any type.

2. Class Template Example

Basic Example: Let’s define a simple class template for a Box that stores a value of any type:

cpp
CopyEdit
#include <iostream>

using namespace std;

 

// Class template for Box

template <typename T>

class Box {

private:

T value;

public:

void setValue(T v) { value = v; }

T getValue() { return value; }

};

 

int main() {

// Create a Box for an int

Box<int> intBox;

intBox.setValue(10);

cout << “Box value (int): ” << intBox.getValue() << endl;

 

// Create a Box for a double

Box<double> doubleBox;

doubleBox.setValue(10.5);

cout << “Box value (double): ” << doubleBox.getValue() << endl;

 

// Create a Box for a string

Box<string> stringBox;

stringBox.setValue(“Hello, World!”);

cout << “Box value (string): ” << stringBox.getValue() << endl;

 

return 0;

}

Output:

java
CopyEdit
Box value (int): 10

Box value (double): 10.5

Box value (string): Hello, World!

  • Explanation:
    • In the above example, the class template Box is defined with a template parameter T. The setValue function stores a value of type T in the value member variable, and getValue retrieves it.
    • The class Box is instantiated with different data types (int, double, string) to show that a single class template can handle multiple types.

3. Template Specialization for Classes

  • Definition: Template specialization for classes allows you to provide a specific implementation of a class template for a particular type. This is useful when the general template does not work as expected or you need a custom implementation for a specific type.

Syntax: You can specialize a class template for a specific type by using the following syntax:

cpp
CopyEdit
template <typename T>

class Box {

T value;

public:

void setValue(T v) { value = v; }

T getValue() { return value; }

};

 

// Specialization for type ‘char’

template <>

class Box<char> {

char value;

public:

void setValue(char v) { value = v; }

char getValue() { return value; }

};

Example of Class Template Specialization:

cpp
CopyEdit
#include <iostream>

using namespace std;

 

// Generic template

template <typename T>

class Box {

private:

T value;

public:

void setValue(T v) { value = v; }

T getValue() { return value; }

};

 

// Specialization for char type

template <>

class Box<char> {

private:

char value;

public:

void setValue(char v) { value = v; }

char getValue() { return value; }

};

 

int main() {

// Box for int

Box<int> intBox;

intBox.setValue(10);

cout << “Box value (int): ” << intBox.getValue() << endl;

 

// Box for char (specialized)

Box<char> charBox;

charBox.setValue(‘A’);

cout << “Box value (char): ” << charBox.getValue() << endl;

 

return 0;

}

Output:

java
CopyEdit
Box value (int): 10

Box value (char): A

  • Explanation:
    • The class template Box is specialized for the char type, providing a custom implementation for storing and retrieving char

4. Class Templates with Multiple Parameters

  • Class Templates with Multiple Type Parameters: Class templates can take multiple type parameters, allowing you to define classes that can work with combinations of data types.

Syntax:

cpp
CopyEdit
template <typename T, typename U>

class Pair {

private:

T first;

U second;

public:

Pair(T f, U s) : first(f), second(s) {}

T getFirst() { return first; }

U getSecond() { return second; }

};

Example:

cpp
CopyEdit
#include <iostream>

using namespace std;

 

template <typename T, typename U>

class Pair {

private:

T first;

U second;

public:

Pair(T f, U s) : first(f), second(s) {}

T getFirst() { return first; }

U getSecond() { return second; }

};

 

int main() {

Pair<int, double> p1(10, 20.5);

cout << “First: ” << p1.getFirst() << “, Second: ” << p1.getSecond() << endl;

 

Pair<string, char> p2(“Hello”, ‘A’);

cout << “First: ” << p2.getFirst() << “, Second: ” << p2.getSecond() << endl;

 

return 0;

}

Output:

sql
CopyEdit
First: 10, Second: 20.5

First: Hello, Second: A

  • Explanation:
    • In this example, the Pair class template takes two type parameters, T and U. The class can be used to store two different data types, and the appropriate types are specified when the class is instantiated.

5. STL Containers and Class Templates

  • STL and Class Templates: The Standard Template Library (STL) in C++ is built on the concept of class templates. STL provides a collection of generic data structures and algorithms, such as vector, list, map, set, and many others, that use class templates to allow storage of different data types.

Example: Using std::vector (Class Template from STL):

cpp
CopyEdit
#include <iostream>

#include <vector>

using namespace std;

 

int main() {

vector<int> vec; // vector is a class template

vec.push_back(10);

vec.push_back(20);

vec.push_back(30);

 

for (int num : vec) {

cout << num << ” “;

}

return 0;

}

Output:CopyEdit
10 20 30

  • Explanation:
    • The std::vector is a class template from STL that can store elements of any type. In this example, we create a vector of integers, add elements to it, and iterate over the vector to display its contents.

6. Best Practices for Class Templates

  • Use meaningful names for template parameters: Choose meaningful names for template parameters (e.g., T for type, KeyType, ValueType for map-like containers).
  • Avoid specialization unless necessary: Use specialization only when you need to implement custom behavior for specific types.
  • Leverage STL: The STL provides highly optimized class templates (e.g., vector, map, set), so prefer to use STL containers when possible instead of implementing your own.

7. Exercises and Hands-On Practice

  • Exercise 1: Implement a class template Stack that simulates a stack data structure with push, pop, and top
  • Exercise 2: Write a class template Array that stores a fixed-size array of elements and provides methods to get and set values.
  • Exercise 3: Create a class template Queue that implements a queue data structure with enqueue, dequeue, and peek

8. Conclusion and Summary

  • Class templates are an essential feature in C++ that allows you to define generic classes for working with any data type. They help create flexible, reusable code.
  • The Standard Template Library (STL) is built on class templates and provides a rich set of pre-built, highly efficient data structures and algorithms that can be applied to any data type.
  • By mastering class templates and understanding their usage in STL, you can build efficient, reusable, and type-safe code for a variety of applications.

Assessment and Quizzes

  • Quiz 1: Multiple-choice questions to test the understanding of class templates.
  • Quiz 2: Practical exercises where students write class templates and apply them to real-world problems.

STL Containers in C++

Module Overview:

The Standard Template Library (STL) in C++ provides a collection of data structures and algorithms. These data structures, called containers, are implemented as class templates and are designed to store and manage collections of data. In this module, you will learn about the different types of containers provided by the STL, how to use them, and when to choose the appropriate container for a given task.

1. Introduction to STL Containers

  • What are STL Containers? STL containers are a set of template classes that allow you to store and manipulate data. They are highly efficient and versatile, allowing you to work with various data types and structures in a generic way.
  • Categories of STL Containers: STL containers can be broadly divided into four categories:
    1. Sequence Containers: Store elements in a linear order. Examples: vector, list, deque.
    2. Associative Containers: Store key-value pairs and allow fast lookups based on keys. Examples: set, map, multiset, multimap.
    3. Unordered Associative Containers: Like associative containers but use hash tables for faster lookups. Examples: unordered_set, unordered_map, unordered_multiset, unordered_multimap.
    4. Container Adapters: Provide a different interface for underlying containers. Examples: stack, queue, priority_queue.

2. Sequence Containers

Sequence containers store elements in a linear order. The main sequence containers in STL are:

2.1. vector

  • Definition: A vector is a dynamic array that can grow in size as elements are added. It allows random access to elements and is highly efficient for operations at the end of the container.
  • Common Operations:
    • push_back(): Adds an element to the end of the vector.
    • pop_back(): Removes the last element.
    • size(): Returns the number of elements in the vector.
    • []: Access elements via index.

Example:

cpp
CopyEdit
#include <iostream>

#include <vector>

using namespace std;

 

int main() {

vector<int> vec;

vec.push_back(10);

vec.push_back(20);

vec.push_back(30);

 

for (int i : vec) {

cout << i << ” “;

}

return 0;

}

Output:
CopyEdit
10 20 30

2.2. list

  • Definition: A list is a doubly-linked list, which allows efficient insertion and removal of elements from both ends. However, it does not allow direct access to elements by index.
  • Common Operations:
    • push_back(), push_front(): Adds an element to the end or front.
    • pop_back(), pop_front(): Removes an element from the end or front.
    • size(): Returns the number of elements in the list.

Example:

cpp
CopyEdit
#include <iostream>

#include <list>

using namespace std;

 

int main() {

list<int> lst;

lst.push_back(10);

lst.push_back(20);

lst.push_back(30);

 

for (int i : lst) {

cout << i << ” “;

}

return 0;

}

Output:
CopyEdit
10 20 30

2.3. deque

  • Definition: A deque (double-ended queue) is similar to a vector but allows efficient insertion and removal of elements from both ends. It is a hybrid between a list and a vector.
  • Common Operations:
    • push_back(), push_front(): Adds an element to the end or front.
    • pop_back(), pop_front(): Removes an element from the end or front.
    • size(): Returns the number of elements in the deque.

Example:

cpp
CopyEdit
#include <iostream>

#include <deque>

using namespace std;

 

int main() {

deque<int> dq;

dq.push_back(10);

dq.push_front(20);

dq.push_back(30);

 

for (int i : dq) {

cout << i << ” “;

}

return 0;

}

Output:
CopyEdit
20 10 30

3. Associative Containers

Associative containers are used to store key-value pairs and provide fast lookups based on the key. These containers automatically sort their elements according to the key.

3.1. set

  • Definition: A set is an associative container that stores unique elements in a sorted order. It automatically sorts its elements according to the key.
  • Common Operations:
    • insert(): Adds an element to the set.
    • find(): Finds an element in the set.
    • size(): Returns the number of elements in the set.

Example:

cpp
CopyEdit
#include <iostream>

#include <set>

using namespace std;

 

int main() {

set<int> s;

s.insert(10);

s.insert(20);

s.insert(30);

 

for (int i : s) {

cout << i << ” “;

}

return 0;

}

Output:
CopyEdit
10 20 30

3.2. map

  • Definition: A map is an associative container that stores key-value pairs in sorted order based on the key. It ensures that each key is unique.
  • Common Operations:
    • insert(): Adds a key-value pair to the map.
    • find(): Finds a key in the map.
    • size(): Returns the number of elements in the map.

Example:

cpp
CopyEdit
#include <iostream>

#include <map>

using namespace std;

 

int main() {

map<int, string> m;

m[1] = “Apple”;

m[2] = “Banana”;

m[3] = “Cherry”;

 

for (auto& p : m) {

cout << p.first << “: ” << p.second << endl;

}

return 0;

}

Output:
makefile
CopyEdit
1: Apple

2: Banana

3: Cherry

3.3. multiset and multimap

  • Definition:
    • multiset: Similar to a set, but allows duplicate elements.
    • multimap: Similar to a map, but allows duplicate keys.

Example:

cpp
CopyEdit
#include <iostream>

#include <set>

using namespace std;

 

int main() {

multiset<int> ms;

ms.insert(10);

ms.insert(20);

ms.insert(10);

 

for (int i : ms) {

cout << i << ” “;

}

return 0;

}

Output:
CopyEdit
10 10 20

4. Unordered Associative Containers

Unordered associative containers store key-value pairs and provide fast lookups using hash tables. They do not maintain any specific order.

4.1. unordered_set

  • Definition: A unordered_set is an associative container that stores unique elements, but unlike set, it does not maintain any specific order.

Example:

cpp
CopyEdit
#include <iostream>

#include <unordered_set>

using namespace std;

 

int main() {

unordered_set<int> us;

us.insert(10);

us.insert(20);

us.insert(30);

 

for (int i : us) {

cout << i << ” “;

}

return 0;

}

Output:
css
CopyEdit
30 10 20 (Order may vary)

4.2. unordered_map

  • Definition: An unordered_map stores key-value pairs and allows fast lookups based on the key, using hash tables. The key-value pairs are not stored in any particular order.

Example:

cpp
CopyEdit
#include <iostream>

#include <unordered_map>

using namespace std;

 

int main() {

unordered_map<int, string> um;

um[1] = “Apple”;

um[2] = “Banana”;

um[3] = “Cherry”;

 

for (auto& p : um) {

cout << p.first << “: ” << p.second << endl;

}

return 0;

}

Output:
makefile
CopyEdit
1: Apple

2: Banana

3: Cherry

(Order may vary)

5. Container Adapters

Container adapters provide a different interface for existing containers.

5.1. stack

  • Definition: A stack is a container adapter that provides a LIFO (Last In, First Out) structure, allowing elements to be added and removed from the top.
  • Common Operations:
    • push(): Adds an element to the top.
    • pop(): Removes the top element.
    • top(): Returns the top element.

Example:

cpp
CopyEdit
#include <iostream>

#include <stack>

using namespace std;

 

int main() {

stack<int> st;

st.push(10);

st.push(20);

st.push(30);

 

cout << “Top element: ” << st.top() << endl;

st.pop();

cout << “Top element after pop: ” << st.top() << endl;

 

return 0;

}

Output:
mathematica
CopyEdit
Top element: 30

Top element after pop: 20

5.2. queue

  • Definition: A queue is a container adapter that provides a FIFO (First In, First Out) structure. It allows elements to be added at the back and removed from the front.

Example:

cpp
CopyEdit
#include <iostream>

#include <queue>

using namespace std;

 

int main() {

queue<int> q;

q.push(10);

q.push(20);

q.push(30);

 

cout << “Front element: ” << q.front() << endl;

q.pop();

cout << “Front element after pop: ” << q.front() << endl;

 

return 0;

}

Output:
mathematica
CopyEdit
Front element: 10

Front element after pop: 20

5.3. priority_queue

  • Definition: A priority_queue is a container adapter that stores elements in a way such that the largest element is always at the top, supporting efficient retrieval of the maximum element.

Example:

cpp
CopyEdit
#include <iostream>

#include <queue>

using namespace std;

 

int main() {

priority_queue<int> pq;

pq.push(10);

pq.push(30);

pq.push(20);

 

cout << “Top element: ” << pq.top() << endl;

pq.pop();

cout << “Top element after pop: ” << pq.top() << endl;

 

return 0;

}

Output:
mathematica
CopyEdit
Top element: 30

Top element after pop: 20

6. Conclusion

STL containers in C++ offer a powerful way to store, manage, and manipulate data efficiently. By selecting the appropriate container based on the needs of your application, you can optimize your code’s performance and ensure scalability. This module covered the different categories of containers and provided hands-on examples for you to get familiar with their usage.

  • Choose vector for fast random access.
  • Choose list for efficient insertions and deletions at both ends.
  • Choose set or map for automatically sorted key-value pairs.
  • Choose unordered_map or unordered_set for fast lookups with no order guarantees.

Iterators in C++

1. Introduction to Iterators

Iterators in C++ are objects that point to elements within a container, such as an array, vector, or list. They provide a way to traverse through the elements of a container in a sequential manner without exposing the underlying structure of the container. Iterators are an essential part of the C++ Standard Template Library (STL) and provide a generic way to access and manipulate elements in a container.

1.1. Why Use Iterators?

  • Abstraction: Iterators abstract the process of traversing elements, making code more readable and maintainable.
  • Uniformity: They provide a consistent interface to traverse different types of containers.
  • Flexibility: Iterators allow for operations such as reading, writing, and manipulating elements during traversal.

2. Types of Iterators

C++ provides several types of iterators, each serving different purposes:

2.1. Input Iterators

Input iterators are used to read elements from a container in a single-pass, forward-only manner. They allow you to iterate through a container and read its elements.

2.2. Output Iterators

Output iterators are used to write elements to a container in a single-pass, forward-only manner. They allow you to iterate through a container and modify its elements.

2.3. Forward Iterators

Forward iterators support reading and writing of elements and can move forward through a container. They can traverse a container multiple times.

2.4. Bidirectional Iterators

Bidirectional iterators extend forward iterators by allowing movement both forward and backward through a container.

2.5. Random Access Iterators

Random access iterators provide the most functionality. They allow movement to any element in constant time, making them suitable for containers like vector and deque.

3. Iterator Operations

Iterators support various operations, depending on their type. Here are some common operations:

3.1. Dereferencing

Dereferencing an iterator gives access to the element it points to.

cpp
#include <iostream>

#include <vector>

 

int main() {

std::vector<int> vec = {10, 20, 30};

std::vector<int>::iterator it = vec.begin();

std::cout << *it << std::endl;  // Output: 10

return 0;

}

3.2. Incrementing and Decrementing

  • Incrementing (++it): Moves the iterator to the next element.
  • Decrementing (–it): Moves the iterator to the previous element (only for bidirectional iterators).

3.3. Comparison

Iterators can be compared using relational operators such as == and != to check equality or inequality.

3.4. Arithmetic Operations

Random access iterators support arithmetic operations like addition and subtraction.

cpp
#include <iostream>

#include <vector>

 

int main() {

std::vector<int> vec = {10, 20, 30, 40};

std::vector<int>::iterator it = vec.begin();

it += 2;

std::cout << *it << std::endl;  // Output: 30

return 0;

}

4. Using Iterators with Different Containers

4.1. Vector

cpp
#include <iostream>

#include <vector>

 

int main() {

std::vector<int> vec = {1, 2, 3, 4, 5};

for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {

std::cout << *it << ” “;

}

return 0;

}

4.2. List

cpp
#include <iostream>

#include <list>

 

int main() {

std::list<int> lst = {10, 20, 30};

for (std::list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {

std::cout << *it << ” “;

}

return 0;

}

4.3. Map

cpp
#include <iostream>

#include <map>

 

int main() {

std::map<int, std::string> mp = {{1, “one”}, {2, “two”}, {3, “three”}};

for (std::map<int, std::string>::iterator it = mp.begin(); it != mp.end(); ++it) {

std::cout << it->first << “: ” << it->second << std::endl;

}

return 0;

}

5. Reverse Iterators

Reverse iterators traverse a container from the end to the beginning. They can be created using the rbegin() and rend() functions.

cpp
#include <iostream>

#include <vector>

 

int main() {

std::vector<int> vec = {1, 2, 3, 4, 5};

for (std::vector<int>::reverse_iterator rit = vec.rbegin(); rit != vec.rend(); ++rit) {

std::cout << *rit << ” “;

}

return 0;

}

6. Iterator Adapters

6.1. std::back_inserter

The std::back_inserter creates an iterator that inserts new elements at the end of the container.

cpp
#include <iostream>

#include <vector>

#include <algorithm>

 

int main() {

std::vector<int> vec;

std::back_inserter(vec) = 10;

std::back_inserter(vec) = 20;

for (int x : vec) {

std::cout << x << ” “;

}

return 0;

}

6.2. std::front_inserter

The std::front_inserter creates an iterator that inserts new elements at the beginning of the container.

6.3. std::inserter

The std::inserter inserts elements at a specified position in the container.

7. Conclusion

Iterators are a powerful tool in C++ that provide a unified way to traverse and manipulate elements in various containers. Understanding and mastering iterators is essential for efficient and effective C++ programming, especially when working with the STL.

Algorithms in STL C++

1. Introduction to STL Algorithms

The Standard Template Library (STL) in C++ offers a rich collection of algorithms that operate on various containers like arrays, vectors, lists, and more. These algorithms are generic, flexible, and can be used for searching, sorting, manipulating, and performing other operations on data. The use of STL algorithms reduces the need to write common algorithms from scratch and helps in writing efficient and concise code.

1.1. Benefits of Using STL Algorithms

  • Efficiency: STL algorithms are highly optimized and efficient.
  • Reusability: They promote code reuse by providing common algorithms.
  • Simplicity: They simplify complex operations with straightforward function calls.

2. Commonly Used STL Algorithms

2.1. Searching Algorithms

2.1.1. std::find

std::find searches for an element in a range and returns an iterator to the first occurrence of the element.

cpp
#include <iostream>

#include <vector>

#include <algorithm>

 

int main() {

std::vector<int> vec = {10, 20, 30, 40, 50};

auto it = std::find(vec.begin(), vec.end(), 30);

if (it != vec.end()) {

std::cout << “Element found at position: ” << std::distance(vec.begin(), it) << std::endl;

} else {

std::cout << “Element not found.” << std::endl;

}

return 0;

}

2.1.2. std::binary_search

cpp
std::binary_search checks if an element exists in a sorted range.

#include <iostream>

#include <vector>

#include <algorithm>

 

int main() {

std::vector<int> vec = {10, 20, 30, 40, 50};

bool found = std::binary_search(vec.begin(), vec.end(), 30);

std::cout << (found ? “Element found.” : “Element not found.”) << std::endl;

return 0;

}

2.2. Sorting Algorithms

2.2.1. std::sort

cpp
std::sort sorts elements in a range in ascending order by default.

#include <iostream>

#include <vector>

#include <algorithm>

 

int main() {

std::vector<int> vec = {40, 10, 50, 30, 20};

std::sort(vec.begin(), vec.end());

for (int x : vec) {

std::cout << x << ” “;

}

return 0;

}

2.2.2. std::stable_sort

std::stable_sort maintains the relative order of equal elements while sorting.

2.3. Modifying Algorithms

2.3.1. std::reverse

cpp
std::reverse reverses the order of elements in a range.

#include <iostream>

#include <vector>

#include <algorithm>

 

int main() {

std::vector<int> vec = {10, 20, 30, 40, 50};

std::reverse(vec.begin(), vec.end());

for (int x : vec) {

std::cout << x << ” “;

}

return 0;

}

2.3.2. std::rotate

std::rotate rotates the elements in a range such that a specified element becomes the first element.

2.4. Removing Algorithms

2.4.1. std::remove

cpp
std::remove removes all occurrences of a specified value and shifts the remaining elements.

#include <iostream>

#include <vector>

#include <algorithm>

 

int main() {

std::vector<int> vec = {10, 20, 30, 20, 40, 50};

vec.erase(std::remove(vec.begin(), vec.end(), 20), vec.end());

for (int x : vec) {

std::cout << x << ” “;

}

return 0;

}

2.5. Transforming Algorithms

2.5.1. std::transform

cpp
std::transform applies a function to a range and stores the result in another range.

#include <iostream>

#include <vector>

#include <algorithm>

 

int main() {

std::vector<int> vec = {1, 2, 3, 4, 5};

std::vector<int> result(vec.size());

std::transform(vec.begin(), vec.end(), result.begin(), [](int x) { return x * 2; });

for (int x : result) {

std::cout << x << ” “;

}

return 0;

}

3. Numeric Algorithms

3.1. std::accumulate

cpp
std::accumulate calculates the sum of a range of elements.

#include <iostream>

#include <vector>

#include <numeric>

 

int main() {

std::vector<int> vec = {1, 2, 3, 4, 5};

int sum = std::accumulate(vec.begin(), vec.end(), 0);

std::cout << “Sum: ” << sum << std::endl;

return 0;

}

3.2. std::inner_product

std::inner_product computes the inner product of two ranges.

4. Conclusion

STL algorithms provide a powerful set of tools for working with data in C++. By using these algorithms, developers can write more efficient and concise code, reduce errors, and focus on the logic of their applications. Mastering these algorithms is crucial for effective C++ programming, especially when dealing with complex data structures and operations.

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *