Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

C++ Programming > Standard Template Library > Flashcards

Standard Template Library Flashcards

1
Q

What kind of iterators are available?

A
  • Input
  • Output
  • Forward
  • Bidirectional
  • Random access
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a priority queue?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Are keys in unordered sets unique?

A

Unordered sets are containers that store unique elements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a heap?

What can it retrieve?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Unordered Maps. How are the elements organized in memory?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What can I add to a map?

A

{key, value}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Do list provide random access?

A

No, since they are not contiguous in memory

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the time complexity of insert to priority queue?

A

Logarithmic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a bidirectional iterator?

A

They can move in both directions (forward and backward)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How much time does it take to remove the last element in a vector?

A

Removing the last element takes only constant time because no resizing happens.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the time complexity of access to priority queue?

A

Constant O(1) to largest element

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a pair? How do I create one?

What is contained in a pair?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How can I move an iterator forward or backward by a given amount?

A

advance(pointer, quantity). Quantity can be positive or negative

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the time complexity of insert into stack?

A

Inserting into a stack can only happen at the top, so insertion is O(1).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the erase time complexity of vector?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How can I sum all the elements in a container?

A

accumulate(first_iterator, last_iterator, initial value of sum)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the access time complexity of list?

A

O(1) if you already have the iterator to the element, O(N) if not

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Where can I add elements to a vector?

A

In the back, with push_back()

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Are key values unique in a map?

A

Yes, a map has unique keys

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Are lists faster or slower to traverse than vectors?

A

As compared to vector, list has slow traversal, but once a position has been found, insertion and deletion are quick.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

How can I implement a deque?

A

1) Doubly-linked list, allowing add/remove from both ends.

2) Dynamic array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the time complexity of access in a map?

A

Logarithmic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is the time complexity of erasing from stack?

A

Deleting from a stack only happens at the to, so deletion is O(1).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the time complexity of access to queue?

A

O(N)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is a deque? What is the policy?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

How are elements internally sorted in unordered set?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is un unordered set?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What is the time complexity of finding in stack?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is the syntax to create a map?

A

std::map mapOfWords;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What the STL?

Which are the main components of the STL?

A 
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Is an unordered map faster than a map in retrieval?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is an iterator?

How can I move through the content of a container?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What is the time complexity of erase to deque?

A

Constant O(1) at begin/end, linear O(n) in the middle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Are values unique in a map?

A

No, a map allows multiple elements to have the same value, as long as they have different keys.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What is a stack?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What is the time complexity of erase in a map?

A

Logarithmic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Is there a sorting algorithm in the STL?

What is the std::sort() computational complexity?

A
  • Yes, std::sort()

- O(N * log(N)) since it is quick sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

What is the time complexity of erase to queue?

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What does make_pair() do?

A

It allows to create a value pair without writing the types explicitly.
pair my_pair = make_pair(0, 2.0);

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

What is a constant iterator?

A

const_iterators don’t allow you to change the values that they point to

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

What’s the syntax of bsearch()? What does it return?

A

The syntax is std::binary_search(startaddress, endaddress, valuetofind). It returns true if the element is found, false otherwise.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

heap::make_heap()

A

This function is used to convert a range in a container to a heap.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

How can I know how many times an element is in a container?

A

count(first_iterator, last_iterator,x) – To count the occurrences of x in vector.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

What is a vector?
What’s the difference with arrays?
How are vectors stored in memory?

A

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.

45
Q

What does the inserter() function do? What’s its syntax?

A

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.

46
Q

What can I add to a set?

A

{value}

47
Q

Do unordered maps provide direct access?

A

Unordered maps implement the direct access operator (operator[]) which allows for direct access of the mapped value using its key value as argument.

48
Q

What is the insert time complexity of vector?

A

O(1) if no reallocation is necessary, O(N) if it is necessary to increase the capacity and therefore copy elements over.

49
Q

What is the time complexity of insert to queue?

A

O(1)

50
Q

What is the time complexity of insert in a map?

A

Logarithmic

51
Q

What is an unordered map?

A

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.

52
Q

Are elements of a set unique?

A

Yes

53
Q

What is the time complexity of erase in a set?

A

O(log N), since it is implemented as a binary search tree

54
Q

Are unordered sets faster than set containsers?

A

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.

55
Q

Do maps provide direct access?

A

Yes

56
Q

What is a map?

A

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare.

57
Q

How can I go the the first and last elements of a container?

A

begin() and end()

58
Q

What is a set?

A

A set is an abstract data type that can store unique values, without any particular order.

59
Q

Are values unique in a set?

A

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.

60
Q

What’s the advantage of unordered sets over sets?

A

Faster retrieval

61
Q

What is the time complexity of access to deque?

A

O(1) since it has random access

62
Q

How can I get the contiguous elements to the one pointed by an iterator?

A

next() and prev()

63
Q

Why is it better to use iterators rather than the [ ] operator?

A

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.

64
Q

heap: :sort_heap()
heap: :is_heap()
heap: :is_heap_until()

A

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.

65
Q

What is the time complexity of insert in a set?

A

O(log N), since it is implemented as a binary search tree

66
Q

Can I sort according to my own ordering? What is the syntax to use my own ordering?

A

Yes, you can use sort(start, end, ordering_function).

bool compareInterval(int i1, int i2) 
{ 
    return (i1 < i2); 
}

sort(arr, arr+n, compareInterval);

67
Q

What is a list?
Are the elements of a list continuous in memory?
What’s the policy?

A

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.

68
Q

How much time does it take to add and remove elements at the beginning or in the middle of a vector?

A

Inserting and erasing at the beginning or in the middle is linear in time.

69
Q

What does reverse() do? What’s the sintax?

A

It reverses the container. The syntax is reverse(first_iterator, last_iterator)

70
Q

What is the time complexity of insert to deque?

A

Constant O(1) at begin/end, linear O(n) in the middle

71
Q

Where can I remove elements to a stack?

A

Top

72
Q

Differences between queue and deque

A

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.

73
Q

What is the time complexity of access in a set?

A

O(log N), since it is implemented as a binary search tree

74
Q

How can I know how far apart two pointers are?

A

distance(first_iterator,desired_position)

75
Q

Difference between at() and []

A

at() provides checks on range, the operator [ ] does not and can cause access outside the bounds

76
Q

Can I modify the value of an element in a set?

A

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.

77
Q

Which logical operators can I use on a pair?

A

operators(=, ==, !=, >=, <=)

78
Q

What is the time complexity of access to stack?

A

O(N)

79
Q

What is a queue? What’s the policy?

A

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.

80
Q

Can I change the elements of an unordered set?

A

No

81
Q

How are elements ordered in a set?

A

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).

82
Q

What is the erase time complexity of list?

A

O(1) if you already have the iterator to the element, O(N) if not

83
Q

What is the insert time complexity of list?

A

O(1) if you already have the iterator to the element, O(N) if not

84
Q

What is the key of an element in an unoredered set?

A

In an unordered_set, the value of an element is at the same time its key

85
Q

What do max_element()/min_element() do?
What’s the sintax?
What doe they return?

A
  • 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.
86
Q

What is a multimap?
Can I have multiple elements with the same key?
Can I have multiple elements with the same key and value?

A

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.

87
Q

How can I get the bounds of a container?

A

lower_bound(first_iterator, last_iterator, x)

upper_bound(first_iterator, last_iterator, x)

88
Q

Are deques faster or slower than vectors? Why?

A

Deques are more efficient for operti

89
Q

What is the time complexity of erase to priority queue?

A

Logarithmic

90
Q

Difference between set and map?

A

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.

91
Q

Do deque provide random access?

A

Yes

92
Q

What is the access time complexity of vector?

A

O(1)

93
Q

Does the STL provide a binary search function?

A

Yes, binary search and assumes that the container is sorted.

94
Q

Are deque always stored in contiguous locations in memory?

A

No

95
Q

How much time does it take to add elements at the end of a vector? Why?

A

O(1) if no reallocation is necessary, O(N) if it is necessary to increase the capacity and therefore copy elements over.

96
Q

How is std::sort() implemented?

A

Quick sort

97
Q

Do vectors provide random access?

A

Yes, because they are implemented as dynamic arrays, therefore are contiguous in memory.

98
Q

Does STL provide a hash set?

A

Yes, unordered set is a hash set.

99
Q

How can I swap two pairs?

A

pair1.swap(pair2);

100
Q

Are elements in unordered sets unique?

A

Unordered sets are containers that store unique elements

101
Q

What is contained in a map?

A

Pairs {key, value} of the kind pair

102
Q

Where can I add elements to a stack?

A

Top

103
Q

What is a multiset?

A

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.

104
Q

How can I search in a container?

A

find(first_iterator, last_iterator, x)

105
Q

Can I remove an element from a set?

A

Yes

106
Q

Do queue allow random access?

A

No

107
Q

Unordered Maps. Are key values unique?

Are the elements sorted?

A

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

108
Q

What is a random-access iterator?

A

It is an iterator that allows you to access any element in the container with the same time complexity.

109
Q

heap: :push_heap()
heap: :pop_heap()

A

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.

C++ Programming (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions