C++ Standard Library Containers Flashcards
Why do we want containers?
To avoid consuming time and effort when writing memory efficient and performant data structures.
What is OOP about?
Producing reusable code, that encapsulates data implementation and abstraction of inner workings ( as well as inheritance and polymorphism)
What are built-in containers an example of?
Template metaprogramming
What do containers provide?
Well-tested code with guaranteed time and memory complexities.
What are some advantages of using containers?
- Provides a common and consistent interface for accessing data in different container types
- Allows for easy swapping between containers without having to change too much code
-Makes code more readable - Generalises passing data to standard algorithms.
- Once behaviour is encoded once it can be easily reused.
What are derived containers?
Containers that are built upon existing container classes, inheriting their functionality and extending it to provide additional features of customization.
What is template metaprogramming?
A technique that leverages compile-time computation using templates to perform complex tasks and computations, allowing for efficient and flexible code generation.
What are the advantages of derived containers?
- Code reusability
- Customisation
- Abstraction
- Efficiency
- Consistency
What order do associative containers store items in?
Order or unordered variants.
How do we order containers for our own types/classes?
Using operator overload.
When should we use the std::array container?
Fixed size array small enough to go on the stack.
When should we use std::vector container?
- When dealing with small data elements with mostly push/pop_back modification
- Large elements where the number of elements is constant.
When should we use std::deque?
Front and back modifications are needed. Less memory efficient but fast front modifications.
When should we use std::list or std::foward_list?
When adding, removing or randomly inserting elements. (Forward list if only integrating forward). But not specific search for one element, as list works as a linked list.
When should we use std::set?
For ordering unique elements and fast look/insertion.
When should we use std::map?
- Mapping non-sequential integers or hashable type to some other value.
When should we use std::onordered_set and std::onordered_map?
When fast access/insertion is required and order of traversal is not important
What does std::set do?
Only allows unique elements. It internally orders the elements so they are iterated in a sorted order.
What are std::lists?
Double-linked list, each elements points to the previous and next item in the list. Meaning we don’t have to store things contiguously in memory. Can be iterated backwards of forwards
What is an example of a derived container?
Stack
std::stack<T, Container = std::Dequeue<T>></T>
What are the time complexities of derived containers?
The time complexity of the underlying structure.
What are associate containers?
Containers that map keys of “some” type to another type. Examples are sets and maps.
What must associate keys be?
Hashable
What is the time complexity of accessing a set?
O(log n)
How do we find elements in a set?
Using the find operator
auto it = set.find(4)
If it isn’t null value or != set.end has been found
What are maps?
Maps store the value along with a key to uniquely identify the value.
