Standard Template Library Flashcards
What kind of iterators are available?
- Input
- Output
- Forward
- Bidirectional
- Random access
What is a priority queue?
Priority queues are a type of container adapters, specifically designed such that the first element of the queue is the greatest of all elements in the queue and elements are in non decreasing order
Are keys in unordered sets unique?
Unordered sets are containers that store unique elements
What is a heap?
What can it retrieve?
Heap data structure can be implemented in a range using STL which allows faster input into heap and retrieval of a number always results in the largest number i.e. largest number of the remaining numbers is popped out each time.
Unordered Maps. How are the elements organized in memory?
They are not organized based on the key, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values
What can I add to a map?
{key, value}
Do list provide random access?
No, since they are not contiguous in memory
What is the time complexity of insert to priority queue?
Logarithmic
What is a bidirectional iterator?
They can move in both directions (forward and backward)
How much time does it take to remove the last element in a vector?
Removing the last element takes only constant time because no resizing happens.
What is the time complexity of access to priority queue?
Constant O(1) to largest element
What is a pair? How do I create one?
What is contained in a pair?
The pair container is a simple container defined in header consisting of two data elements or objects.
The first element is referenced as ‘first’ and the second element as ‘second’ and the order is fixed (first, second).
Pair is used to combine together two values which may be different in type. Pair provides a way to store two heterogeneous objects as a single unit.
How can I move an iterator forward or backward by a given amount?
advance(pointer, quantity). Quantity can be positive or negative
What is the time complexity of insert into stack?
Inserting into a stack can only happen at the top, so insertion is O(1).
What is the erase time complexity of vector?
Removing the last element takes only constant time because no resizing happens. Inserting and erasing at the beginning or in the middle is linear in time.
How can I sum all the elements in a container?
accumulate(first_iterator, last_iterator, initial value of sum)
What is the access time complexity of list?
O(1) if you already have the iterator to the element, O(N) if not
Where can I add elements to a vector?
In the back, with push_back()
Are key values unique in a map?
Yes, a map has unique keys
Are lists faster or slower to traverse than vectors?
As compared to vector, list has slow traversal, but once a position has been found, insertion and deletion are quick.
How can I implement a deque?
1) Doubly-linked list, allowing add/remove from both ends.
2) Dynamic array
What is the time complexity of access in a map?
Logarithmic
What is the time complexity of erasing from stack?
Deleting from a stack only happens at the to, so deletion is O(1).
What is the time complexity of access to queue?
O(N)
What is a deque? What is the policy?
Double ended queues are sequence containers with the feature of expansion and contraction on both the ends. They are similar to vectors, but are more efficient in case of insertion and deletion of elements at the end, and also the beginning. Unlike vectors, contiguous storage allocation may not be guaranteed.
How are elements internally sorted in unordered set?
Internally, the elements in the unordered_set are not sorted in any particular order, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their values
What is un unordered set?
Unordered sets are containers that store unique elements in no particular order, and which allow for fast retrieval of individual elements based on their value. It is basically a hash set.
What is the time complexity of finding in stack?
Searching for a given value in the stack requires repeatedly popping elements off the top of the stack until you find the value you seek. So search is O(n)
What is the syntax to create a map?
std::map mapOfWords;
What the STL?
Which are the main components of the STL?
The Standard Template Library (STL) is a set of C++ template classes to provide common programming data structures and functions such as lists, stacks, arrays, etc. It is a library of container classes, algorithms and iterators. STL has the following components - Algorithms - Containers - Functions - Iterators
Is an unordered map faster than a map in retrieval?
unordered_map containers are faster than map containers to access individual elements by their key, although they are generally less efficient for range iteration through a subset of their elements.
What is an iterator?
How can I move through the content of a container?
An iterator is an object (like a pointer) that points to an element inside the container.
We can use iterators to move through the contents of the container.
What is the time complexity of erase to deque?
Constant O(1) at begin/end, linear O(n) in the middle
Are values unique in a map?
No, a map allows multiple elements to have the same value, as long as they have different keys.
What is a stack?
Stacks are a type of container adaptors with LIFO(Last In First Out) type of working, where a new element is added at one end and (top) an element is removed from that end only.
What is the time complexity of erase in a map?
Logarithmic
Is there a sorting algorithm in the STL?
What is the std::sort() computational complexity?
- Yes, std::sort()
- O(N * log(N)) since it is quick sort
What is the time complexity of erase to queue?
O(1)
What does make_pair() do?
It allows to create a value pair without writing the types explicitly.
pair my_pair = make_pair(0, 2.0);
What is a constant iterator?
const_iterators don’t allow you to change the values that they point to
What’s the syntax of bsearch()? What does it return?
The syntax is std::binary_search(startaddress, endaddress, valuetofind). It returns true if the element is found, false otherwise.
heap::make_heap()
This function is used to convert a range in a container to a heap.
How can I know how many times an element is in a container?
count(first_iterator, last_iterator,x) – To count the occurrences of x in vector.
What is a vector?
What’s the difference with arrays?
How are vectors stored in memory?
Vectors are same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container.
Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators.
What does the inserter() function do? What’s its syntax?
It can be used to insert the elements at any position in the container. It accepts 2 arguments, the container and iterator to position where the elements have to be inserted.
What can I add to a set?
{value}
Do unordered maps provide direct access?
Unordered maps implement the direct access operator (operator[]) which allows for direct access of the mapped value using its key value as argument.
What is the insert time complexity of vector?
O(1) if no reallocation is necessary, O(N) if it is necessary to increase the capacity and therefore copy elements over.
What is the time complexity of insert to queue?
O(1)
What is the time complexity of insert in a map?
Logarithmic
What is an unordered map?
Unordered maps are associative containers that store elements formed by the combination of a key value and a mapped value, and which allows for fast retrieval of individual elements based on their keys.
Are elements of a set unique?
Yes
What is the time complexity of erase in a set?
O(log N), since it is implemented as a binary search tree
Are unordered sets faster than set containsers?
unordered_set containers are faster than set containers to access individual elements by their key, although they are generally less efficient for range iteration through a subset of their elements.
Do maps provide direct access?
Yes
What is a map?
std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare.
How can I go the the first and last elements of a container?
begin() and end()
What is a set?
A set is an abstract data type that can store unique values, without any particular order.
Are values unique in a set?
Yes, since the value of each element also identifies the element itself. This is different from maps, where each element is identified by its key.
What’s the advantage of unordered sets over sets?
Faster retrieval
What is the time complexity of access to deque?
O(1) since it has random access
How can I get the contiguous elements to the one pointed by an iterator?
next() and prev()
Why is it better to use iterators rather than the [ ] operator?
If you use the [ ] operator, you can try to access elements out of bounds. Instead, with iterators, you know exactly where to start and where to stop with the begin() and end() functions.
heap: :sort_heap()
heap: :is_heap()
heap: :is_heap_until()
sort_heap(begin_iterator, end_iterator) :- This function is used to sort the heap. After this operation, the container is no longer a heap
is_heap(begin_iterator, end_iterator) :- This function is used to check whether the container is heap or not. Generally, in most implementations, the reverse sorted container is considered as heap. Returns true if container is heap else returns false.
is_heap_until(begin_iterator, end_iterator) :- This function returns the iterator to the position till the container is the heap. Generally, in most implementations, the reverse sorted container is considered as heap.
What is the time complexity of insert in a set?
O(log N), since it is implemented as a binary search tree
Can I sort according to my own ordering? What is the syntax to use my own ordering?
Yes, you can use sort(start, end, ordering_function).
bool compareInterval(int i1, int i2)
{
return (i1 < i2);
}
sort(arr, arr+n, compareInterval);
What is a list?
Are the elements of a list continuous in memory?
What’s the policy?
Lists are sequence containers that allow non-contiguous memory allocation. A list is a doubly linked list. Elements can be added and removed from both the front and the back.
How much time does it take to add and remove elements at the beginning or in the middle of a vector?
Inserting and erasing at the beginning or in the middle is linear in time.
What does reverse() do? What’s the sintax?
It reverses the container. The syntax is reverse(first_iterator, last_iterator)
What is the time complexity of insert to deque?
Constant O(1) at begin/end, linear O(n) in the middle
Where can I remove elements to a stack?
Top
Differences between queue and deque
They are similar to vectors, but are more efficient in case of insertion and deletion of elements at the end, and also the beginning. Inserting in the middle of a deque is faster than with a vector since we can check it the position in which we want to insert is closer to the end or to the beginning, and use either one or the either to iterate until the desired position.
What is the time complexity of access in a set?
O(log N), since it is implemented as a binary search tree
How can I know how far apart two pointers are?
distance(first_iterator,desired_position)
Difference between at() and []
at() provides checks on range, the operator [ ] does not and can cause access outside the bounds
Can I modify the value of an element in a set?
The value of the element cannot be modified once it is added to the set, though it is possible to remove and add the modified value of that element.
Which logical operators can I use on a pair?
operators(=, ==, !=, >=, <=)
What is the time complexity of access to stack?
O(N)
What is a queue? What’s the policy?
Queues are a type of container adaptors which operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front. They do not allow random access.
Can I change the elements of an unordered set?
No
How are elements ordered in a set?
Internally, the elements in a set are always sorted following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).
What is the erase time complexity of list?
O(1) if you already have the iterator to the element, O(N) if not
What is the insert time complexity of list?
O(1) if you already have the iterator to the element, O(N) if not
What is the key of an element in an unoredered set?
In an unordered_set, the value of an element is at the same time its key
What do max_element()/min_element() do?
What’s the sintax?
What doe they return?
- max_element (first_iterator, last_iterator) – To find the maximum element of a vector.
- min_element (first_iterator, last_iterator) – To find the minimum element of a vector.
What is a multimap?
Can I have multiple elements with the same key?
Can I have multiple elements with the same key and value?
Multimap is an associative container that contains a sorted list of key-value pairs, while permitting multiple entries with the same key. Sorting is done according to the comparison function Compare, applied to the keys. Search, insertion, and removal operations have logarithmic complexity.
How can I get the bounds of a container?
lower_bound(first_iterator, last_iterator, x)
upper_bound(first_iterator, last_iterator, x)
Are deques faster or slower than vectors? Why?
Deques are more efficient for operti
What is the time complexity of erase to priority queue?
Logarithmic
Difference between set and map?
I. Duplicate Elements: A Set does not allow inserting duplicate elements. A Map does not allow using duplicate keys, but it allows inserting duplicate values for unique keys.
II. Null values: A Set allows inserting maximum one null value. In a Map we can have single null key at most and any number of null values.
III. Ordering: A Set does not maintain any order of elements. Some of sub-classes of a Set can sort the elements in an order like LinkedHashSet. A Map does not maintain any order of its elements. Some of its sub-classes like TreeMap store elements of the map in ascending order of keys.
Do deque provide random access?
Yes
What is the access time complexity of vector?
O(1)
Does the STL provide a binary search function?
Yes, binary search and assumes that the container is sorted.
Are deque always stored in contiguous locations in memory?
No
How much time does it take to add elements at the end of a vector? Why?
O(1) if no reallocation is necessary, O(N) if it is necessary to increase the capacity and therefore copy elements over.
How is std::sort() implemented?
Quick sort
Do vectors provide random access?
Yes, because they are implemented as dynamic arrays, therefore are contiguous in memory.
Does STL provide a hash set?
Yes, unordered set is a hash set.
How can I swap two pairs?
pair1.swap(pair2);
Are elements in unordered sets unique?
Unordered sets are containers that store unique elements
What is contained in a map?
Pairs {key, value} of the kind pair
Where can I add elements to a stack?
Top
What is a multiset?
Multisets are a type of associative containers similar to set, with an exception that multiple elements can have same values. In other words, the same value can appear multiple times.
How can I search in a container?
find(first_iterator, last_iterator, x)
Can I remove an element from a set?
Yes
Do queue allow random access?
No
Unordered Maps. Are key values unique?
Are the elements sorted?
Keys are unique. Internally, the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values
What is a random-access iterator?
It is an iterator that allows you to access any element in the container with the same time complexity.
heap: :push_heap()
heap: :pop_heap()
push_heap(elem) :- This function is used to insert element elem into heap. The size of the heap is increased by 1. New element is placed appropriately in the heap.
pop_heap():- This function is used to delete the maximum element of the heap. The size of heap is decreased by 1. The heap elements are reorganised accordingly after this operation.
