STL C++ Flashcards
1
Q
What is a STL made of?
A
- Container
- Iterator
- Algorithm
- functions
2
Q
std::array
A
array arr;
- encapsulates a fixed size array.
- arraysize is needed at the compile time.
- Assign by value is actually by value.
- access elements: i) at() ii) [] iii) front() iv) back() v) data()
3
Q
std::vector
A
vector v(5, 0)
- sequence container
- dynamic array or ArrayList
- Its size can grow and diminish dynamically.
- access elements by i)at() ii) [] iii) front() iv) back() v) datat()
- modifiers: i) insert() ii) emplace() iii) push_back() iv) emplace_back() iv) pop_back() v) resize() vi)swap() vii) erase() viii) clear()
4
Q
std::set
A
- set is an associative container and contains a sorted set of unique objects of type key.
- usually implemented using red-black tree.
- Insertion, retrieval and deletion is O(log N)
- if we want to store user defined data types in some order we need to provide with a compare function.
- We can pass the order of sorting while constructing the set object.
5
Q
std::multiset
A
- multiset is an associative container and contains a sorted set of duplicate objects of type key.
- usually implemented using red-black tree.
- Insertion, retrieval and deletion is O(log N)
- if we want to store user defined data types in some order we need to provide with a compare function.
- We can pass the order of sorting while constructing the set object.
- Multiset is similar to set except it can contain multiple values with same value.
6
Q
std::map
A
- map obj; //T1 is one type T2 is of another type
- std::map is an associative container that store elements in key value combination where key should be unique otherwise it overrides the previous value.
- It is implemented using self-balancing trees (AVL/BST)
- It stores key value pairs in an order.
- Generally used in dictionary type problems.
7
Q
std::multimap
A
- multimap obj; //T1 is one type T2 is of another type
- std::multimap is an associative container that store elements in key value combination where key could be duplicate.
- Data structure for multimap is not specified but most people assume It is implemented using self-balancing trees (AVL/BST).
- It stores key value pairs in an order.
- Lookup: count, find, contains, equal_range, lower_bound, upper_bound.
- We don’t have at() or [] like we had in map.
8
Q
std::forward_list
A
- forward_list list1;
- This is a single linked list.
- Available operations: =, assign, front, empty, max_size, clear, insert_after, emplace_after, reverse, sort, merge, splice_after, unique, remove, remove_if, resize.
9
Q
std::list
A
- List is a doubly linked list.
- List is a sequence container that allow non-contagious memory allocation.
- List is faster than other sequence containers in terms of insertion,retrieval or deletion if we have an iterator.
- Used as DLL in C++.
- Operations: =, assign, front, back, empty, size, max_size, clear, insert, emplace, push_back, pop_back, push_front, pop_front, reverse, sort, merge, splice, unique, remove, remove_if, resize.
10
Q
std::deque
A
- Double ended queue
- is an indexed sequence container.
- Allows fast insertion at both beginning and end,
- Unlike vectors elements are not stored in contagious manner.
- uses individual allocated fixed size array, with additional bookkeeping, meaning indexed based access to deque must perform two pointer derefence as opposed to one pointer derefernce in vector.
- Storage is automatically expanded and contracted as needed.
- Expansion is cheaper than that of vector.
- A deque holding one element has to allocate its full internal array.
- Time complexity: Random access O(1), Insertion/Removal at beginning O(1), Insertion/Deletion O(N).
11
Q
std::unordered_set
A
- unordered_set is an associative container that contains set of unique elements.
- Search, insertion and removal have average time constant time complexity.
- Internally the elements are organized into buckets.
- It uses hashing to insert elements into the buckets.
- Allows fast access.
12
Q
std::unordered_map
A
- std::unordered_map is an associative container that store elements in key value combination where key should be unique otherwise it overrides the previous value.
- Search, insertion and removal have average time constant time complexity.
- . Internally the elements are organized into buckets.
- It uses hashing to insert elements into the buckets.
- Allows fast access.
13
Q
std::pair
A
- std::pair is a struct template that provides a way to store two heterogeneous objects as a single unit.
- map, multimap, unordered_map, unordered_multimap can use pair to insert data into their structures.
14
Q
std::priority_queue
A
- std::priority_queue is a container adaptor that provides constant time lookup of the largest or the smallest element.
- By default std::vector is the container used inside.
- Cost of insertion and extraction is logarathmic.
- std::priority_queue is implemented using std::make_heap, std::push_heap, std::pop_heap functions.
15
Q
std::queue
A
- a container adaptor that gives the programmer the the functionality of a queue.
- queue is a FIFO DS.
- provides only specific set of functions.
- allows to push(insert) at front and pop(remove) at back.
- gives front,back, push, pop, empty, size.
- The standard container classes deque and list fulfill the requirements of queue. By default, if no container class is specified for a particular queue class instantiation, the standard container deque is used.
