C++ course
Multithreading and STL(Standard Template Library)
Vishnu Joshi
joshivis@[Link]
Oregon State University
Multithreading
Multithreading
Threads
Multithreading
Threads
Threads
Mutex and smart
lock
Standard
Template Library
What are threads?
4/15
Multithreading
Threads
Threads
Mutex and smart
lock
Standard
Template Library
What are threads?
They are unit of execution in a process
4/15
Multithreading
Threads
Threads
Mutex and smart
lock
Standard
Template Library
What are threads?
They are unit of execution in a process
Why do we need threads?
4/15
Multithreading
Threads
Threads
Mutex and smart
lock
Standard
Template Library
What are threads?
They are unit of execution in a process
Why do we need threads?
⋄ To concurrently execute the program for time efficiency
4/15
Multithreading
Threads
Threads
Mutex and smart
lock
Standard
Template Library
What are threads?
They are unit of execution in a process
Why do we need threads?
⋄ To concurrently execute the program for time efficiency
⋄ In real world nothing works linearly
4/15
Multithreading
Threads
Threads
Mutex and smart
lock
Standard
Template Library
What are threads?
They are unit of execution in a process
Why do we need threads?
⋄ To concurrently execute the program for time efficiency
⋄ In real world nothing works linearly
⋄ Most simple module in a complex system usually has multiple things
running at the same time
4/15
Multithreading
Mutex and smart lock
Multithreading
Mutex and smart lock
Threads
Mutex and smart
lock
Standard
Template Library
Issues with multithreading
⋄ Deadlock
6/15
Multithreading
Mutex and smart lock
Threads
Mutex and smart
lock
Standard
Template Library
Issues with multithreading
⋄ Deadlock - Can be solved with intelligent algorithm design
6/15
Multithreading
Mutex and smart lock
Threads
Mutex and smart
lock
Standard
Template Library
Issues with multithreading
⋄ Deadlock - Can be solved with intelligent algorithm design
⋄ Race condition
6/15
Multithreading
Mutex and smart lock
Threads
Mutex and smart
lock
Standard
Template Library
Issues with multithreading
⋄ Deadlock - Can be solved with intelligent algorithm design
⋄ Race condition - Use of locks, priorities etc
6/15
Multithreading
Mutex and smart lock
Threads
Mutex and smart
lock
Standard
Template Library
Issues with multithreading
⋄ Deadlock - Can be solved with intelligent algorithm design
⋄ Race condition - Use of locks, priorities etc
⋄ Starvation
6/15
Multithreading
Mutex and smart lock
Threads
Mutex and smart
lock
Standard
Template Library
Issues with multithreading
⋄ Deadlock - Can be solved with intelligent algorithm design
⋄ Race condition - Use of locks, priorities etc
⋄ Starvation - Usually caused by forgotten unlocks
6/15
Standard Template Library
Standard Template Library
What are STLs?
Multithreading
STL
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
⋄ STL is predefined classes and functions that implements Data
Unordered
containers
Structures
9/15
Multithreading
STL
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
⋄ STL is predefined classes and functions that implements Data
Unordered
containers
Structures
⋄ They are well tested
9/15
Multithreading
STL
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
⋄ STL is predefined classes and functions that implements Data
Unordered
containers
Structures
⋄ They are well tested
There are 4 kinds,
9/15
Multithreading
STL
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
⋄ STL is predefined classes and functions that implements Data
Unordered
containers
Structures
⋄ They are well tested
There are 4 kinds,
⋄ Containers -
9/15
Multithreading
STL
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
⋄ STL is predefined classes and functions that implements Data
Unordered
containers
Structures
⋄ They are well tested
There are 4 kinds,
⋄ Containers - They store and manage data
9/15
Multithreading
STL
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
⋄ STL is predefined classes and functions that implements Data
Unordered
containers
Structures
⋄ They are well tested
There are 4 kinds,
⋄ Containers - They store and manage data
⋄ Algorithm -
9/15
Multithreading
STL
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
⋄ STL is predefined classes and functions that implements Data
Unordered
containers
Structures
⋄ They are well tested
There are 4 kinds,
⋄ Containers - They store and manage data
⋄ Algorithm - They operate on container data
9/15
Multithreading
STL
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
⋄ STL is predefined classes and functions that implements Data
Unordered
containers
Structures
⋄ They are well tested
There are 4 kinds,
⋄ Containers - They store and manage data
⋄ Algorithm - They operate on container data
⋄ Iterators -
9/15
Multithreading
STL
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
⋄ STL is predefined classes and functions that implements Data
Unordered
containers
Structures
⋄ They are well tested
There are 4 kinds,
⋄ Containers - They store and manage data
⋄ Algorithm - They operate on container data
⋄ Iterators - They help in traversing the containers
9/15
Multithreading
STL
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
⋄ STL is predefined classes and functions that implements Data
Unordered
containers
Structures
⋄ They are well tested
There are 4 kinds,
⋄ Containers - They store and manage data
⋄ Algorithm - They operate on container data
⋄ Iterators - They help in traversing the containers
⋄ Functors (Function objects) -
9/15
Multithreading
STL
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
⋄ STL is predefined classes and functions that implements Data
Unordered
containers
Structures
⋄ They are well tested
There are 4 kinds,
⋄ Containers - They store and manage data
⋄ Algorithm - They operate on container data
⋄ Iterators - They help in traversing the containers
⋄ Functors (Function objects) - They modify the algorithms
9/15
Standard Template Library
Types of containers
Types of containers
Multithreading
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ Sequence containers -
11/15
Types of containers
Multithreading
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ Sequence containers - vector, list, deque, array, forward_list
11/15
Types of containers
Multithreading
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ Sequence containers - vector, list, deque, array, forward_list
⋄ Associative containers -
11/15
Types of containers
Multithreading
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ Sequence containers - vector, list, deque, array, forward_list
⋄ Associative containers - set, map, multiset, multimap
11/15
Types of containers
Multithreading
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ Sequence containers - vector, list, deque, array, forward_list
⋄ Associative containers - set, map, multiset, multimap
⋄ Unordered containers -
11/15
Types of containers
Multithreading
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ Sequence containers - vector, list, deque, array, forward_list
⋄ Associative containers - set, map, multiset, multimap
⋄ Unordered containers - unordered_set, unordered_map,
unordered_multiset, unordered_multimap
11/15
Types of containers
Multithreading
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ Sequence containers - vector, list, deque, array, forward_list
⋄ Associative containers - set, map, multiset, multimap
⋄ Unordered containers - unordered_set, unordered_map,
unordered_multiset, unordered_multimap
⋄ Container adapter -
11/15
Types of containers
Multithreading
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ Sequence containers - vector, list, deque, array, forward_list
⋄ Associative containers - set, map, multiset, multimap
⋄ Unordered containers - unordered_set, unordered_map,
unordered_multiset, unordered_multimap
⋄ Container adapter - stack, queue and priority queue
11/15
Standard Template Library
Associative containers
Multithreading
Associative containers
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ maps, multimaps, sets, multiset
13/15
Multithreading
Associative containers
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ maps, multimaps, sets, multiset
⋄ they are stored in Red Black Tree a form of BST
13/15
Multithreading
Associative containers
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ maps, multimaps, sets, multiset
⋄ they are stored in Red Black Tree a form of BST
⋄ since they use tree they are always sorted
13/15
Multithreading
Associative containers
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ maps, multimaps, sets, multiset
⋄ they are stored in Red Black Tree a form of BST
⋄ since they use tree they are always sorted
⋄ best used with small data and when ordering is required, access time
is O(log n)
13/15
Standard Template Library
Unordered containers
Multithreading
Unordered containers
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ unordered_maps, unordered_multimaps, unordered_sets,
unordered_multisets
15/15
Multithreading
Unordered containers
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ unordered_maps, unordered_multimaps, unordered_sets,
unordered_multisets
⋄ they are stored in hash table
15/15
Multithreading
Unordered containers
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ unordered_maps, unordered_multimaps, unordered_sets,
unordered_multisets
⋄ they are stored in hash table
⋄ they are not sorted
15/15
Multithreading
Unordered containers
Standard
Template Library
What are STLs?
Types of containers
Associative
containers
Unordered
containers
⋄ unordered_maps, unordered_multimaps, unordered_sets,
unordered_multisets
⋄ they are stored in hash table
⋄ they are not sorted
⋄ best when used with large amount of data and when the access
needs to be O(1)
15/15
Thanks for your attention!