Unit-7_PC++ standard library containers.

Unit-7_PC++

1. UNIT-7 STANDARD LIBRARY CONTAINERS AND ITERATORS Prepared By: Dr. Aayushi Chaudhari, CE, CSPIT Prof. Nishat Shaikh, IT, CSPIT

2. Contents Introduction to Big O Introduction to Hash Tables Introduction to Containers Working with Iterators Sequence Container (vector, list, deque , Associative) Container Adaptors Lambda Expression

3. Introduction to Big O Big O notation is a mathematical representation used to describe the time complexity and space complexity of an Program. It helps in evaluating an Program's efficiency by expressing how its performance scales as the input size grows . Time Complexity: How the time required to run an Program increases with input size . Space Complexity: How the memory usage of an Program grows with input size . Big O notation provides an upper bound on the growth rate, focusing on the worst-case scenario. It ignores constants and lower-order terms, emphasizing the dominant factor that affects scalability.

4. Purpose of Big O Notation Efficiency Analysis : Helps compare Programs and determine which one is faster or uses less memory for large inputs . Predict Performance : Gives an idea of how an Program will perform as input sizes increase. Optimization : Helps identify bottlenecks and improve code by choosing better Programs .

5. Common Big O Complexity Classes O(1): Constant time – performance does not depend on input size. O(log n): Logarithmic time – grows slowly as input size increases. O(n): Linear time – grows directly proportional to input size. O(n log n): Log-linear time – common in efficient sorting Programs . O(n²): Quadratic time – performance degrades significantly with larger inputs .

6. Example O(1 ) - Constant Time #include < iostream > int main() { int arr [] = {1, 2, 3, 4, 5}; std :: cout << "First element: " << arr [0] << std :: endl ; // O(1) return 0; } Explanation : Accessing an array element by index is a constant-time operation, regardless of the array's size.

7. O(n) - Linear Time #include < iostream > #include <vector> int main() { std ::vector< int > vec = {1, 2, 3, 4, 5}; int sum = 0; for ( int num : vec ) { // O(n) sum += num ; } std :: cout << "Sum: " << sum << std :: endl ; return 0; } Explanation: The loop runs once for each element in the vector. If there are n elements, the loop runs n times.

8. O(log n) - Logarithmic Time #include < iostream > #include <vector > int binarySearch ( const std ::vector< int >& vec , int target) { int left = 0, right = vec.size () - 1; while (left <= right) { // The search space is halved in each step int mid = left + (right - left) / 2; if ( vec [mid] == target) { return mid; // Target found } else if ( vec [mid] < target) { left = mid + 1; // Search in the right half } else { right = mid - 1; // Search in the left half } } return -1; // Target not found } It works by repeatedly halving the search space until the target is found.

9. O(n log n) Merge Sort is a divide-and-conquer algorithm that splits the input into smaller parts, sorts them, and then merges the sorted parts back together. Its time complexity is O(n log n) due to the following: Divide : The array is recursively divided into two halves until each subarray contains a single element. This division step takes log n time, as the array is halved at each level . Merge : The subarrays are merged back together in sorted order. Each merge operation processes all elements in the array, taking O(n) time at each level . Combine : The merging is repeated across all levels of recursion, resulting in n log n time complexity . {0, 1, 2, 3, 7, 8, 10} O(n log n) Log-linear time Divide Original : {8, 3, 1, 7, 0, 10, 2} Split 1: {8, 3, 1} and {7, 0, 10, 2} Split 2: {8} {3, 1} and {7, 0} {10, 2} Split 3: {8} {3} {1} and {7} {0} {10} {2} Merge Merge 1: {3} and {1} → {1, 3} {7} and {0} → {0, 7} {10} and {2} → {2, 10} Merge 2: {8} and {1, 3} → {1, 3, 8} {0, 7} and {2, 10} → {0, 2, 7, 10} Merge 3: {1, 3, 8} and {0, 2, 7, 10} → {0, 1, 2, 3, 7, 8, 10}

10. O(n²) - Quadratic Time #include < iostream > #include <vector> int main() { std ::vector< int > vec = {1, 2, 3, 4, 5}; for ( size_t i = 0; i < vec.size (); ++ i ) { // Outer loop O(n) for ( size_t j = 0; j < vec.size (); ++j) { // Inner loop O(n) std :: cout << vec [ i ] << ", " << vec [j] << std :: endl ; } } return 0; } For each element in the outer loop, the inner loop iterates through the entire vector, resulting in n × n = n² iterations.

11. Introduction to Hash Tables A hash table is a data structure that provides an efficient way to store and retrieve data using key-value pairs. The core idea of a hash table is to use a hash function to compute an index into an array of buckets, where the desired value can be found . In C++, hash tables are implemented using the std :: unordered_map container from the < unordered_map > header . Key-Value Storage: Stores data as key-value pairs . Hash Function: Computes an index for each key to quickly locate its value . Non-Sequential Order: Keys are not stored in any specific order .

12. Key Methods Method Description insert({key, value}) Inserts a key-value pair into the hash table. erase(key) Removes the key-value pair by key. find(key) Returns an iterator to the key-value pair if found; otherwise, returns end(). operator[] Accesses or modifies the value associated with a key. size() Returns the number of elements in the hash table. empty() Checks if the hash table is empty.

13. Example of hash table Hash Function: Converting the Key to a Hash Code ASCII of String Key ("apple "): "a" = 97," p" = 112," p" = 112," l" = 108," e" = 101 Summing these ASCII values: 97 + 112 + 112 + 108 + 101 = 530 apply a modulo operation with the table size ( eg . 10) 530 % 10 = Thus, the hash function maps the key "apple" to the hash code 530, which corresponds to index 0 in the hash table. So , the key-value pair ("apple", 5) is stored at index 0 in the hash table. Key Hash Code Calculation Index (Bucket) Action apple ASCII sum = 530, 530 % 10 = 0 Insert ("apple", 5) banana ASCII sum = 530, 530 % 10 = 0 Insert ("banana", 2) cherry ASCII sum = 606, 606 % 10 = 6 6 Insert ("cherry", 8)

14. Introduction to containers Containers in C++ are fundamental components of the Standard Template Library (STL) that store and manage collections of data in a structured way. They provide a variety of functionalities for handling data efficiently, such as insertion, deletion, access, and traversal . Common Operations in Containers Insertion : Add elements using methods like push_back , insert, or emplace . Deletion : Remove elements using methods like pop_back , erase, or clear . Traversal : Use iterators (e.g., begin() and end()) or range-based loops to traverse the elements.

15. Ways to choose the Right Container Use vector for dynamic arrays with random access . Use list for frequent insertions and deletions in the middle . Use deque for insertions and deletions from both ends. Use map for key-value pairs with sorted keys . Use unordered_map for fast key-value lookups with no order requirement . Use stack or queue for LIFO or FIFO data processing .

16. Examples of Sequence containers

17. Vector

18. Example of List (Insertion and deletion in middle of the list) advance(it, n): Moves the iterator it forward by n positions . insert(it , value): Inserts the value before the position pointed to by it . erase(it ): Deletes the element at the position pointed to by it and returns an iterator to the next element.

19. Example of list (Insertion, deletion at the front and end) push_back : Adds an element to the end of the list . push_front : Adds an element to the front of the list . pop_back : Removes the last element of the list . pop_front : Removes the first element of the list . Range-based for loop: Traverses and prints the elements of the list.

20. Deque push_back : Adds an element to the back of the deque . push_front : Adds an element to the front of the deque . pop_front : Removes the front element . pop_back : Removes the back element . front and back: Access the first and last elements . Range-based for loop: Traverses and prints all elements.

21. Examples of Associative container

22. Set example Set is used to store unique elements in sorted order . It cannot accept duplicate values.

23. Multiset example A multiset allows duplicate elements and stores them in sorted order.

24. Map A map stores key-value pairs with unique keys, sorted by the keys.

25. Multimap A multimap stores key-value pairs where duplicate keys are allowed.

26. Container Adapter

27. What are Container adapters?? Container adapters in C++ are a specialized form of containers in the Standard Template Library (STL ). They are built on top of existing sequence containers (like vector, deque , or list) to provide restricted interfaces and tailored functionalities . There are three main container adapters : stack (LIFO - Last In First Out ) queue (FIFO - First In First Out ) priority_queue (Elements ordered by priority)

28. stack A stack operates on the LIFO (Last In First Out) principle. Elements are added and removed from the top of the stack .

29. queue A queue operates on the FIFO (First In First Out) principle. Elements are added at the back and removed from the front.

30. priority queue A priority queue orders elements by priority. By default, it uses a max-heap (largest element at the top), but can be configured to use a min-heap .

31. Lambda Expressions Lambda expressions, are a convenient way to define anonymous (unnamed) functions . They are particularly useful for short operations that are passed as arguments to algorithms or used for event handling . Syntax of Lambda Expressions: [ capture_clause ] ( parameters ) -> return_type { function_body } [ ] (empty): No variables are captured . [=]: Captures all variables by value . [&]: Captures all variables by reference . [ a, &b]: Captures a by value and b by reference . Parameters : The input arguments to the lambda . Return Type : (Optional) Specifies the return type. Usually inferred automatically . Function Body : The code to execute.

32. Example of simple lambda

33. Example of lambda with parameters

34. Example with Capture Clause

35. Example with Capture clause (Correct) Note : Adding mutable allows modifying copies of captured values.

36. Thank You.