Difference between revisions of "GPU621/Braindead"
m |
(Updated STL section with Container Class Templates) |
||
| Line 4: | Line 4: | ||
== Group Members == | == Group Members == | ||
| + | Joseph Chan | ||
| + | Bowen Chu | ||
| + | Henry Xu | ||
| + | |||
| + | == Background == | ||
| + | C++11 introduces many improvements and modifications, such as the addition of function objects and hash tables. These can be | ||
| + | found within the STL, which stands for Standard Template Library. It consists of commonly used containers, algorithms, | ||
| + | functions and iterator templates. | ||
| + | |||
| + | The C++11 STL has container classes such as a list and deque. However, the methods within these classes do not have built-in | ||
| + | concurrency, despite the STL having thread classes that may be used for parallelization. Intel's oneAPI Threading Building | ||
| + | Blocks (oneTBB) implements similar container classes that, unlike the STL container classes, has built-in concurrency which | ||
| + | allows operations performed with them to be executed in parallel. Thus, oneTBB is one of many tools that can be used for | ||
| + | parallel programming with containers. | ||
| + | |||
| + | == Standard Template Library (STL) == | ||
| + | The STL has many container classes. In this section, only three of the container types will be covered: vector, queue, and | ||
| + | hash table. | ||
| − | + | === Container Class Templates === | |
| + | ==== std::vector ==== | ||
| + | The std::vector template has an underlying data structure of a dynamic array. That is, the std::vector stores elements in a sequence akin to an array, but also has the functionality of resizing to match the capacity to the number of elements in the container. Upon adding or removing elements, the std::vector will resize itself to create or remove space depending on the number of elements that will be added. | ||
| + | |||
| + | Member functions: | ||
| + | * at - accesses the specified element but throws an exception if it is out of bounds | ||
| + | * operator[] - accesses the specified element | ||
| + | * front - accesses the front element | ||
| + | * back - accesses the back element | ||
| + | * empty - checks whether the container is empty | ||
| + | * size - returns the number of elements | ||
| + | * clear - deletes all elements | ||
| + | * insert - inserts elements | ||
| + | * emplace - constructs and inserts an element | ||
| + | * erase - deletes an element | ||
| + | * push_back - adds an element to the end | ||
| − | + | ==== std::queue ==== | |
| + | The std::queue template has the same properties as std::vector in that it is a dynamically resizing array, but implements the First-In First-Out (FIFO) approach. This means that the first element to be added into the std::queue will be the first element to be removed from the queue. It also implies that the last element to be added will be the last element to be removed. | ||
| − | + | Member functions: | |
| + | * front - accesses the first element | ||
| + | * back - accesses the last element | ||
| + | * empty - checks whether the container is empty | ||
| + | * size - returns the number of elements | ||
| + | * push - inserts an element at the front | ||
| + | * emplace - constructs and inserts an element at the front | ||
| + | * push - inserts an element at the front | ||
| + | * pop - removes the first element | ||
| − | == | + | ==== std::unordered_map ==== |
| + | The std::unordered_map template has an underlying data structure of a hash map (or hash table). A hash map is an unsorted table of key-value pairs that have unique keys. In other words, there cannot be two or more pairs in the table that have the same key. In a hash table, the keys of the pairs are hashed by using a hash function. | ||
| − | + | Member functions: | |
| − | + | * at - accesses the specified element but throws an exception if it is out of bounds | |
| + | * operator[] - accesses or inserts a specified element | ||
| + | * find - finds an element with a specific key | ||
| + | * empty - checks whether the container is empty | ||
| + | * size - returns the number of elements | ||
| + | * clear - deletes all elements | ||
| + | * insert - inserts elements | ||
| + | * emplace - constructs and inserts an element | ||
| + | * erase - deletes an element | ||
| − | === | + | === Container Performance === |
| − | + | ==== Vector ==== | |
| + | ==== Queue ==== | ||
| + | ==== HashMap ==== | ||
| − | === | + | == Thread Building Blocks (TBB) == |
| − | + | === Container Class Templates === | |
| + | ==== tbb::concurrent_vector ==== | ||
| + | ==== tbb::concurrent_queue ==== | ||
| + | ==== tbb::concurrent_hash_map ==== | ||
| + | === Container Performance === | ||
| + | ==== Concurrent Vector ==== | ||
| + | ==== Concurrent Queue ==== | ||
| + | ==== Concurrent HashMap ==== | ||
| − | == | + | == STL and TBB Comparison == |
| + | === Advantages and Disadvantages === | ||
Revision as of 23:30, 11 August 2021
GPU621/DPS921 | Participants | Groups and Projects | Resources | Glossary
Contents
C++11 STL Comparison to TBB - Case Studies
Our goal is to compare the STL to the TBB in C++11.
Group Members
Joseph Chan Bowen Chu Henry Xu
Background
C++11 introduces many improvements and modifications, such as the addition of function objects and hash tables. These can be found within the STL, which stands for Standard Template Library. It consists of commonly used containers, algorithms, functions and iterator templates.
The C++11 STL has container classes such as a list and deque. However, the methods within these classes do not have built-in concurrency, despite the STL having thread classes that may be used for parallelization. Intel's oneAPI Threading Building Blocks (oneTBB) implements similar container classes that, unlike the STL container classes, has built-in concurrency which allows operations performed with them to be executed in parallel. Thus, oneTBB is one of many tools that can be used for parallel programming with containers.
Standard Template Library (STL)
The STL has many container classes. In this section, only three of the container types will be covered: vector, queue, and hash table.
Container Class Templates
std::vector
The std::vector template has an underlying data structure of a dynamic array. That is, the std::vector stores elements in a sequence akin to an array, but also has the functionality of resizing to match the capacity to the number of elements in the container. Upon adding or removing elements, the std::vector will resize itself to create or remove space depending on the number of elements that will be added.
Member functions:
- at - accesses the specified element but throws an exception if it is out of bounds
- operator[] - accesses the specified element
- front - accesses the front element
- back - accesses the back element
- empty - checks whether the container is empty
- size - returns the number of elements
- clear - deletes all elements
- insert - inserts elements
- emplace - constructs and inserts an element
- erase - deletes an element
- push_back - adds an element to the end
std::queue
The std::queue template has the same properties as std::vector in that it is a dynamically resizing array, but implements the First-In First-Out (FIFO) approach. This means that the first element to be added into the std::queue will be the first element to be removed from the queue. It also implies that the last element to be added will be the last element to be removed.
Member functions:
- front - accesses the first element
- back - accesses the last element
- empty - checks whether the container is empty
- size - returns the number of elements
- push - inserts an element at the front
- emplace - constructs and inserts an element at the front
- push - inserts an element at the front
- pop - removes the first element
std::unordered_map
The std::unordered_map template has an underlying data structure of a hash map (or hash table). A hash map is an unsorted table of key-value pairs that have unique keys. In other words, there cannot be two or more pairs in the table that have the same key. In a hash table, the keys of the pairs are hashed by using a hash function.
Member functions:
- at - accesses the specified element but throws an exception if it is out of bounds
- operator[] - accesses or inserts a specified element
- find - finds an element with a specific key
- empty - checks whether the container is empty
- size - returns the number of elements
- clear - deletes all elements
- insert - inserts elements
- emplace - constructs and inserts an element
- erase - deletes an element
