GPU621/Braindead

GPU621/DPS921 | Participants | Groups and Projects | Resources | Glossary

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